# 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)

## 7 thoughts on “Bresenham算法”

1. GilBert

写的很好很详细，学习了，谢谢。
另外，可能有个地方写的不对：
就是：
3) e2 = e1 + 2 * deltaY – 2 * deltaX * (y2 – y1)
4) 当e2 + 2 * deltaY > deltaX时y2 = y1 + 1, 否则y2 = y1
中的4）应该是e1不是e2吧，呵呵

2. dd

很感谢共享，我测试了你的代码，发现代码在大于零时可用，但小于零就无法绘出，是不是这时候要做些修改呢