12,549,449 members (45,311 online)
Article
alternative version

8.2K views
6 bookmarked
Posted

# Using DataPlotter implementing three kinds of Scan-converting Line Segments algorithm

, 7 May 2012 CPOL
 Rate this:
Using DataPlotter implements three kind of Scan-converting Line Segments algorithm

## 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);
} /* while */
} /* mid PointLine */```

## 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)
{
//int x;
float dx, dy, x, y, k;
MyPoint pt;

//dx = x1 - x0;
//dy = y1 - y0;

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)
{
//pt.m_x = x0;
if (dy >= 0)
{
for (y = y0; y <= y1; ++y)
{
pt = new MyPoint();
pt.m_x = x0;
pt.m_y = y;
}
}
else
{
for (y = y1; y <= y0; ++y)
{
pt = new MyPoint();
pt.m_x = x0;
pt.m_y = y;
}
}
}
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));

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

x += k;
}
}
}
else
{
//pt.m_y = y0;
for (x = x0; x <= x1; ++x)
{
pt = new MyPoint();
pt.m_y = y0;
pt.m_x = x;
}
}
}```

### 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);
} /* while */
}
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);
} /* while */
}
}
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);
} /* while */
}
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);
} /* while */
}
}
} /* mid PointLine */```

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

## About the Author

 China
No Biography provided

## You may also be interested in...

 Pro Pro

## Comments and Discussions

 -- There are no messages in this forum --