Introduction
In the raster graphics, a Scan-converting Line Segments algorithm is: to determine the optimal approximation to a group of pixels for a line-segment. It can be expressed as the following relations:
Input: line (starting point and end point, the requirement is integral coordinates)
Output: a group of integral point (pixel), the group can best represent the input line.
For example:
Given: line-segment, starting point(0, 0), end point(5, 2).
Find: points set {(0, 0), (1, 0), (2, 1), (3, 1), (4, 2), (5, 2)}
In this article, I will introduce 3 kinds of algorithms. They are Digital Differential Analyzer (DDA), Middle Point Algorithm and Bresenham’s Algorithm.
1. The Digital Differential Analyzer(DDA)
1.1 Basic idea
Given: line segment L connecting (x0, y0) to (x1, y1), the equation of L is: y = kx + b
where k is the slope and b is the y intercept.
k = (y1-y0) / (x1-x0)
Algorithm: Let's start from x0, the left end of the x, step to right. Step length = 1 (pixel), calculating the corresponding y = kx + b; and take pixel (x, Round (y)) for the current point coordinate.
Round (a) is a rounded integer operation.
1.2 Incremental Algorithm
Compute: 
When ,
That is, y increase k (slope of the line) when x increase 1.
1.3 pseudo-code
void DDALine (int x0,int y0,int x1,int y1,int color)
{
int x;
float dx, dy, y, k;
dx, = x1-x0, dy=y1-y0;
k=dy/dx, y=y0;
for (x=x0; x£x1, x++)
{
drawpixel (x, int(y+0.5), color);
y=y+k;
}
}
2. Middle Point Algorithm
2.1 Basic idea
If the current pixel is P(xp, yp), then the next pixel is P1 (xp + 1, yp) or P2 (xp + 1, yp + 1).
Let's set:
M = (xp + 1, yp + 0.5) is the middle point between p1 and p2.
And point Q is the intersection of the line segment L and the vertical line x = xp + 1.
Let's compare the y coordinate of Q and the y coordinate of M
- if M is in the bottom of Q, then P2 (xp + 1, yp + 1) should be the next pixel;
- else if M is in the upper of Q, then P1 (xp + 1, yp) should be the next pixel;
Tectonic discriminent: d = F (M) = F (xp + 1, yp + 0.5) = a (xp + 1) + b (yp + 0.5) + c
Where a = y0-y1, b = x1-x0, c = x0*y1-x1*y0
If d < 0, then M is below Q. We take the upper right pixel(P2) for the next pixel;
Else if d > 0, then M is above Q. We take the right pixel(P1) for the next pixel;
Else if d = 0, then M and Q are coincident points. we can choose either P1 or P2, let's promise to take P1 for the next pixel;
2.2 Incremental Algorithm
l If d>= 0, we take the right pixel P1(xp + 1, yp) as the current pixel. How to found the next pixel? we should calculate:
d1 = F (xp + 2, yp + 0.5) = a (xp + 2) + b (yp + 0.5) = d + a; the incrementation is a
l If d < 0, then we take the upper right pixel P2 (xp + 1, yp + 1) as the current pixel. To find the next pixel, we should calculate:
d2 = F (xp + 2, yp + 1.5) = a (xp + 2) + b (yp + 1.5) + c = d + a + b; the incrementation is a + b
l The beginning pixel is (x0, y0), the initial value of d is:
d0 = F (x0 + 1, y0 + 0.5) = F (x0, y0) + a + 0.5*b = a + 0.5*b.
We can use 2*d instead of d to transfer the number from decimal to integer, and to improve algorithm efficiency.
We make d0 = 2*a + b, d1 = 2*a, d2 = 2*a + 2*b
2.3 pseudo-code
void Midpoint Line (int x0,int y0,int x1, int y1,int color)
{
int a, b, d1, d2, d, x, y;
a=y0-y1, b=x1-x0, d=2*a+b;
d1=2*a, d2=2* (a+b);
x=x0, y=y0;
drawpixel(x, y, color);
while (x<x1)
{
if (d<0)
{
x++, y++, d+=d2;
}
else
{
x++, d+=d1;
}
drawpixel (x, y, color);
}
}
3. Bresenham’s Algorithm
3.1 Basic idea
3.1.1 Priciples:
1. Draw a group of virtual grid lines crossing the center of every pixel.
2. Calculate the intersection between the line segment L and the virtual grid lines according the ascending order from the start point of L to the end point.
3. Determine the nearest pixel to the intersection according to the sign of a differential value which is described in the next section.
3.1.2 Detailed Information:
Line equation:, in which k = dy/dx. Because the starting point of the line is in the center of a pixel , the initial value of d is d0 = 0.
Whenever the coordnate x increase 1, the value of d increase k, namely d = d + k. If d=1, we minus 1 from d. So we make the value of d between 0 and 1.
-when d=0.5, the closest pixel is the upper right pixels ()
-when d < 0.5, the closest pixel is the right pixels ()
For the convenience of calculation, Let's set e = d-0.5,
The initial value of e is -0.5, the incrementation is k.
-when e =0, we take the upper right pixel of the current pixel ();
-when e < 0, we take the right pixel of the current pixel ();
We can convert decimal to integer to avoid division operation. Because the algorithm only use the sign of the differential value d, it can be replaced as follows:
3.2 Pseudo-code
void InterBresenhamline (int x0,int y0,int x1, int y1,int color)
{
dx = x1-x0,;dy = y1- y0,;e=-dx;
x=x0; y=y0;
for (i=0; i<dx; i++)
{
drawpixel (x, y, color);
x++; e=e+2*dy;
if (e>=0)
{ y++; e=e-2*dx;}
}
}Using the code
1.1 DDALine
private void DDALine(int x0, int y0, int x1, int y1)
{
float dx, dy, x, y, k;
MyPoint pt;
int tmp;
if (x0 > x1)
{
tmp = x0; x0 = x1; x1 = tmp;
tmp = y0; y0 = y1; y1 = tmp;
}
dx = x1 - x0;
dy = y1 - y0;
if (dx == 0)
{
if (dy >= 0)
{
for (y = y0; y <= y1; ++y)
{
pt = new MyPoint();
pt.m_x = x0;
pt.m_y = y;
pl.RltData.Add(pt);
}
}
else
{
for (y = y1; y <= y0; ++y)
{
pt = new MyPoint();
pt.m_x = x0;
pt.m_y = y;
pl.RltData.Add(pt);
}
}
}
else if (Math.Abs(dy) <= dx)
{
k = dy / dx;
y = y0;
for (x = x0; x <= x1; x++)
{
pt = new MyPoint();
pt.m_x = x;
pt.m_y = Math.Floor(Convert.ToDouble(y + 0.5));
pl.RltData.Add(pt);
y += k;
}
}
else if (dy != 0)
{
k = dx / dy;
if (dy > 0)
{
x = x0;
for (y = y0; y <= y1; y++)
{
pt = new MyPoint();
pt.m_y = y;
pt.m_x = Math.Floor(Convert.ToDouble(x + 0.5));
pl.RltData.Add(pt);
x += k;
}
}
else
{
x = x1;
for (y = y1; y <= y0; y++)
{
pt = new MyPoint();
pt.m_y = y;
pt.m_x = Math.Floor(Convert.ToDouble(x + 0.5));
pl.RltData.Add(pt);
x += k;
}
}
}
else
{
for (x = x0; x <= x1; ++x)
{
pt = new MyPoint();
pt.m_y = y0;
pt.m_x = x;
pl.RltData.Add(pt);
}
}
}
1.2 Mid-Point Line
private void MidpointLine(int x0, int y0, int x1, int y1)
{
int a, b, d1, d2, d, x, y;
a = y0 - y1; b = x1 - x0;
int tmp;
if (Math.Abs(a) <= Math.Abs(b))
{
if (x1 < x0)
{
tmp = x0; x0 = x1; x1 = tmp;
tmp = y0; y0 = y1; y1 = tmp;
}
a = y0 - y1; b = x1 - x0;
if (y0<=y1)
{
d = 2 * a + b;
d1 = 2 * a;
d2 = 2 * (a + b);
x = x0; y = y0;
drawpixel(x, y);
while (x < x1)
{
if (d < 0)
{ x++; y++; d += d2; }
else
{ x++; d += d1; }
drawpixel(x, y);
}
}
else
{
d = 2 * a - b;
d1 = 2 * a;
d2 = 2 * (a - b);
x = x0; y = y0;
drawpixel(x, y);
while (x < x1)
{
if (d > 0)
{ x++; --y; d += d2; }
else
{ x++; d += d1; }
drawpixel(x, y);
}
}
}
else
{
if (y1 < y0)
{
tmp = x0; x0 = x1; x1 = tmp;
tmp = y0; y0 = y1; y1 = tmp;
}
a = x0 - x1; b = y1 - y0;
if (x0 <= x1)
{
d = 2 * a + b;
d1 = 2 * a;
d2 = 2 * (a + b);
x = x0; y = y0;
drawpixel(x, y);
while (y < y1)
{
if (d < 0)
{ x++; y++; d += d2; }
else
{ y++; d += d1; }
drawpixel(x, y);
}
}
else
{
d = 2 * a - b;
d1 = 2 * a;
d2 = 2 * (a - b);
x = x0; y = y0;
drawpixel(x, y);
while (y < y1)
{
if (d > 0)
{ y++; --x; d += d2; }
else
{ y++; d += d1; }
drawpixel(x, y);
}
}
}
}
1.3 Bresenham's Line
private void InterBresenhamline(int x0, int y0, int x1, int y1)
{
int x, y, dx, dy, e;
dx = x1 - x0; dy = y1 - y0;
int tmp;
if (Math.Abs(dy) <= Math.Abs(dx))
{
if (x1 < x0)
{
tmp = x0; x0 = x1; x1 = tmp;
tmp = y0; y0 = y1; y1 = tmp;
}
dx = x1 - x0; dy = y1 - y0;
if (y0<=y1)
{
e = -dx;
x = x0; y = y0;
for (int i = 0; i <= dx; i++)
{
drawpixel(x, y);
x++; e = e + 2 * dy;
if (e >= 0)
{
y++;
e = e - 2 * dx;
}
}
}
else
{
e = dx;
x = x0; y = y0;
for (int i = 0; i <= dx; i++)
{
drawpixel(x, y);
x++; e = e + 2 * dy;
if (e <= 0)
{
--y;
e = e + 2 * dx;
}
}
}
}
else
{
if (y1 < y0)
{
tmp = x0; x0 = x1; x1 = tmp;
tmp = y0; y0 = y1; y1 = tmp;
}
dx = x1 - x0; dy = y1 - y0;
if (x0 <= x1)
{
e = -dy;
x = x0; y = y0;
for (int i = 0; i <= dy; i++)
{
drawpixel(x, y);
y++; e = e + 2 * dx;
if (e >= 0)
{
x++;
e = e - 2 * dy;
}
}
}
else
{
e = dy;
x = x0; y = y0;
for (int i = 0; i <= dy; i++)
{
drawpixel(x, y);
y++; e = e + 2 * dx;
if (e <= 0)
{
--x;
e = e + 2 * dy;
}
}
}
}
}
Points of Interest
In my code, I used the DataPlotter control source code provided by Hans-Jürgen Schmidt, and I made some change, adding the implementation code of the three Scan-converting Line Segments algorithm mentioned above.
http://www.codeproject.com/Articles/5207/DataPlotter-linear-or-logarithmic-display-of-2D-da
History
- V1.0 initial version 2012-4-5.
- V1.0.1 fixed some format error 2012-4-6.
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.
Submit an article or tip
