Click here to Skip to main content
Click here to Skip to main content

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

By , 7 May 2012
Rate this:
Please Sign up or sign in to vote.

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;
                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
    {
        //pt.m_y = y0;
        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);
            } /* 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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

buyong

China China
No Biography provided

Comments and Discussions

 
-- There are no messages in this forum --
| Advertise | Privacy | Mobile
Web02 | 2.8.140415.2 | Last Updated 7 May 2012
Article Copyright 2012 by buyong
Everything else Copyright © CodeProject, 1999-2014
Terms of Use
Layout: fixed | fluid