Bresenham算法

line_bresenham(startX, startY, endX, endY)
{
deltaX = endX - startX;
deltaY = endY - startY;
k = deltaY / deltaX;

<span style="color: #0000ff">for</span> (x = startX, y = startY; x &lt;= endX; ++x)
{
<span style="color: #0000ff">if</span> (满足一定条件)
{
++y;
}
drawPixel(x, y);
}
}

<span style="color: #008000">// 算法1: 用斜率判断</span>
<span style="color: #0000ff">void</span> line_bresenham_k(startX, startY, endX, endY)
{
deltaX = endX - startX;
deltaY = endY - startY;
k = deltaY / deltaX;

<span style="color: #0000ff">for</span> (x = startX, y = startY; x &lt;= endX; ++x)
{
<span style="color: #0000ff">if</span> (x - startX != 0)
{
<span style="color: #008000">// 计算当前斜率</span>
currentK = (y - startY) / (x - startX);

<span style="color: #008000">// 如果当前斜率 &lt; k, 则增加y坐标</span>
<span style="color: #0000ff">if</span> (currentK &lt; k)
{
++y
}
}
drawPixel(x, y);
}
}

<span style="color: #008000">// 算法2: 用距离判断. 计算直线与光栅线交点y坐标我们需要用到</span>
<span style="color: #008000">// 直线方程 y = k (x - startX) + startY</span>
line_bresenham_dist(startX, startY, endX, endY)
{
deltaX = endX - startX;
deltaY = endY - startY;
k = deltaY / deltaX;

<span style="color: #0000ff">for</span> (x = startX, y = startY; x &lt;= endX; ++x)
{
<span style="color: #008000">// 计算直线与光栅线交点的y坐标, 以及与光栅点的距离</span>
ptY = k * (x - startX) + startY;
dist = ptY - y;

<span style="color: #008000">// 如果距离 &gt; 0.5或者 &lt; -0.5, 说明我们需要增加y以</span>
<span style="color: #008000">// 将距离的绝对值控制在0.5之类</span>
<span style="color: #0000ff">if</span> (dist &gt; 0.5 || dist &lt; -0.5)
{
++y;
}
drawPixel(x, y);
}
}

<span style="color: #008000">// 算法3: 在算法2的基础上消灭浮点数!</span>
line_bresenham_dist(startX, startY, endX, endY)
{
deltaX = endX - startX;
deltaY = endY - startY;

<span style="color: #0000ff">for</span> (x = startX, y = startY; x &lt;= endX; ++x)
{
<span style="color: #008000">// 计算直线与光栅线交点的y坐标, 以及与光栅点的距离</span>
ptY1 = deltaY * (x - startX) + startY * deltaX;
dist1 = ptY1 - y * deltaX;
dist1 = dist1 &lt;&lt; 1; <span style="color: #008000">// dist1 = dist1 * 2</span>

<span style="color: #008000">// 如果距离 &gt; 0.5或者 &lt; -0.5, 说明我们需要增加y以</span>
<span style="color: #008000">// 将距离的绝对值控制在0.5之类</span>
<span style="color: #0000ff">if</span> (dist1 &gt; deltaX || dist &lt; -deltaX)
{
++y;
}
drawPixel(x, y);
}
}

1) d2 = d1 + k –  (y2 – y1)
2) 当d1 + k > 0.5时y2 = y1 + 1, 否则y2 = y1

3) e2 =  e1 + 2 * deltaY – 2 * deltaX * (y2 – y1)
4) 当e1 + 2 * deltaY > deltaX时y2 = y1 + 1, 否则y2 = y1

<span style="color: #008000">// 算法4: 在算法2, 3的基础上利用递推消灭乘法和浮点数!</span>
line_bresenham(startX, startY, endX, endY)
{
deltaX = endX - startX;
deltaY = endY - startY;
e = 0;
deltaX2 = deltaX &lt;&lt; 1;
deltaY2 = deltaY &lt;&lt; 1;

drawPixel(startX, startY);

<span style="color: #0000ff">for</span> (x = startX + 1, y = startY; x &lt;= endX; ++x)
{
<span style="color: #008000">// 关系式3) e2 =  e1 + 2 * deltaY – 2 * deltaX * (y2 – y1)</span>
<span style="color: #008000">// 关系式4) 当e2 + 2 * deltaY &gt; deltaX时y2 = y1 + 1, 否则y2 = y1</span>
e += deltaY2;
<span style="color: #0000ff">if</span> (e &gt; deltaX)
{
e -= deltaX2;
++y;
}
drawPixel(x, y);
}
}

dist1 = 2 * deltaY * (x – startX) + 2 * startY * deltaX – 2 * y * deltaX, 则
e2 – e1
= 2 * deltaY * (x – startX) + 2 * startY * deltaX – 2 * y2 * deltaX – [2 * deltaY * (x – 1 – startX) + 2 * startY * deltaX – 2 * y1 * deltaX ]
=  – 2 * y2 * deltaX + 2 * deltaY + 2 * y1 * deltaX
= 2 * deltaY – 2 * deltaX * (y2 – y1)

1) e2 = e1 + 2 * deltaY – 2 * deltaX * (y2 – y1)
2) –deltaX <  e1 < deltaX
3) –deltaX < e2 < deltaX
4)  y2 – y1 = 0 或者 1

2 * deltaY – deltaX < e1 + 2 * deltaY < 2 * deltaY + deltaX

2 * deltaY – deltaX – 2 * deltaX * (y2 – y1) < e2 < deltaX– 2 * deltaX * (y2 – y1)

deltaX – 2 * deltaX * (y2 – y1) < e2 < 2 * deltaY + deltaX – 2 * deltaX * (y2 – y1)