Implementation of Midpoint Line algorithm with source code in C/C++.

Description

Given a line segment from leftmost (x_o,y_o) to rightmost (x₁,y₁):

y = mx + b
m = ∆y / ∆x = (y₁ - y_o) / (x₁ - x_o)
assuming x_o,x₁,y_o,y₁ are integers

Assuming 0 <= m <= 1 we start at the leftmost edge of the line, and move right one pixel-column at a time illuminating the pixel either in the current row (the pixel to the PΒ) or the next higher row (the pixel to the PΒ.) as shown in figure.

Can we rewrite the line equation in the form: F(x, y) = ax + by + c = 0

y= (∆y / ∆x) * x + b
0 = (∆y / ∆x) * x - y + b
0 = ∆y * x - ∆x * y + ∆x * b

so a = ∆y b= -∆x c= ∆x*b

F(x,y) = ∆y * x - ∆x * y + ∆x * b will be

F(x,y)=ax + by + c

so for any point (xi,yi) we can plug xi,yi into the above equation and

F(xi,yi) = 0 -> (xi,yi) is on the line
F(xi,yi) > 0 -> (xi,yi) is below the line
F(xi,yi) < 0 -> (xi,yi) is above the line

Given that we have illuminated the pixel at (x_k,y_k) we will next either illuminate

the pixel to the P_α (x_k + 1,y_k)
or the pixel to the P_β (x_k + 1,y_k+ 1)


 
To decide we look at the Midpoint between the P_α and P_β pixel and see which side of the midpoint the line falls on.

line above the midpoint -> illuminate the P_α pixel
line below the midpoint -> illuminate the P_β pixel
line exactly on the midpoint -> CHOOSE TO illuminate the P_α pixel

We create a decision variable called d
We plug the Midpoint into the above function for the line and see where the midpoint falls in relation to the line.
d = F(x_p +1,y_p+1/2)

d > 0 -> pick P_β pixel
d < 0 -> pick P_α pixel
d = 0 -> ***CHOOSE*** to pick P_α pixel

That tells us which pixel to illuminate next. Now we need to compute what Midpoint is for the next iteration.

If we pick the P_α pixel


 

Midpoint is incremented by 1 in X and 0 in Y

We want to compute the new d without recomputing d from the new Midpoint
We want to compute the new d only using current d
dcurrent= F(x_p + 1,y_p + 1/2)
using the function F(x,y) = a * x + b * y + c we can expand this out ...
dcurrent= a * (x_p + 1) + b * (y_p + 1/2) + c

dnew = F(x_p + 2, yp + 1/2)
dnew = a * (x_p + 2) + b * (y_p + 1/2) + c
when you simplify it you end up with: dnew = dcurrent + a
so we create a new variable called deltaE where deltaE = a

If we pick the P_β pixel

Midpoint is incremented by 1 in x and 1 in y

We want to compute the new d without recomputing d from the new Midpoint, only using current d
We want to compute the new d only using current d
dcurrent= F(x_p + 1,y_p + 1/2)
using the function F(x,y) = a * x + b * y + c we can expand this out ...
dcurrent= a * (x_p + 1) + b * (y_p + 1/2) + c
dnew = F(x_p + 2, y_p + 3/2)

dnew = a * (x_p + 2) + b * (y_p + 3/2) + c
when you simplify it you end up with: dnew = dcurrent + a + b

initial point (x_oy_o) is known
so initial M is at (x_o + 1, y_o + 1/2)

so initial d = F(x_o + 1, y_o + 1/2)
using the function F(x,y) = a * x + b * y + c we can expand this out ...

= a * (x_o + 1) + b * (y_o + 1/2) + c

= (a * x_o + b * y_o + c) + a + 1/2 * b
= F(x_o,y_o) + a + 1/2 * b

since (x_o,y_o) is on the line -> F(x_o,y_o) = 0
so initial d = a + b / 2

the divion by 2 is still annoying, but we can remove it by being clever
we can avoid the division by 2 by multiplying function by 2
this also multiplies d, deltaE, deltaNE by 2
but since d is only concerned with =0,< 0, or > 0 multiplication does not affect it

So now we can finally show the Midpoint Line algorithm

Assuming integral endpoints for the line segment (if not then make them integral)
starting at the leftmost edge of the line (Algorithm):

∆x = x₁ - x_o
∆y = y₁ - y_o
d = ∆y * 2 - ∆x
deltaE = ∆y * 2
deltaNE = (∆y - ∆x) * 2
x = x_o
y = y_o
illuminate x, y

while (X < X1) repeatedly

if ( d <= 0)

add deltaE to d
add 1 to X

else

add deltaNE to d
add 1 to X
add 1 to Y

illuminate X, Y

 

 
Advantages:

    This is faster method then DDA because here we have to do only integer calculation.


 
Disadvantages:

Accumulation of error every time due to rounding in equation.


 
Source Code in C.


 

#include<stdio.h>

#include<graphics.h>

#include<stdlib.h>

#include<conio.h>

#define MAX 20

 

void swap(int* a,int* b)

{

    int t=*a;

    *a=*b;

    *b=t;

}

 

void midpointline(int x1,int y1,int x2,int y2)

{

    int dx,dy,d,incry,incre,incrne,slopegt1=0;

    dx=abs(x1-x2);dy=abs(y1-y2);

    if(dy>dx)

    {

        swap(&x1,&y1);

        swap(&x2,&y2);

        swap(&dx,&dy);

        slopegt1=1;

    }

    if(x1>x2)

    {

        swap(&x1,&x2);

        swap(&y1,&y2);

    }

    if(y1>y2)

        incry=-1;

    else

        incry=1;

    d=2*dy-dx;

    incre=2*dy;

    incrne=2*(dy-dx);

    while(x1<x2)

    {

        if(d<=0)

            d+=incre;

        else

        {

            d+=incrne;

            y1+=incry;

        }

        x1++;

        if(slopegt1)

            putpixel(y1,x1,15);

        else

            putpixel(x1,y1,15);

    }

}

void dot(int x1,int y1,int x2,int y2)

{

    int dx,dy,d,incry,incre,incrne,slopegt1=0,k=0;

    dx=abs(x1-x2);dy=abs(y1-y2);

    if(dy>dx)

    {

            swap(&x1,&y1);

        swap(&x2,&y2);

        swap(&dx,&dy);

        slopegt1=1;

    }

    if(x1>x2)

    {

        swap(&x1,&x2);

        swap(&y1,&y2);

    }

    if(y1>y2)

        incry=-1;

    else

        incry=1;

    d=2*dy-dx;

    incre=2*dy;

    incrne=2*(dy-dx);

    while(x1<x2)

    {

        if(d<=0)

            d+=incre;

        else

        {

            d+=incrne;

            y1+=incry;

        }

        x1++,k++;

 

        if(k%2==0)

        {

        if(slopegt1)

 

 

            putpixel(y1,x1,15);

 

        else

 

 

            putpixel(x1,y1,15);

            }

 

    }

}

 

void das(int x1,int y1,int x2,int y2)

{

    int dx,dy,d,incry,incre,incrne,slopegt1=0,k=0;

    dx=abs(x1-x2);dy=abs(y1-y2);

    if(dy>dx)

    {

            swap(&x1,&y1);

        swap(&x2,&y2);

        swap(&dx,&dy);

        slopegt1=1;

    }

    if(x1>x2)

    {

        swap(&x1,&x2);

        swap(&y1,&y2);

    }

    if(y1>y2)

        incry=-1;

    else

        incry=1;

    d=2*dy-dx;

    incre=2*dy;

    incrne=2*(dy-dx);

    while(x1<x2)

    {

        if(d<=0)

            d+=incre;

        else

        {

            d+=incrne;

            y1+=incry;

        }

        x1++,k++;

 

           if((k%5)!=0)

          {

        if(slopegt1)

 

 

            putpixel(y1,x1,15);

 

        else

 

 

            putpixel(x1,y1,15);

        }

    }

}

void dasdot(int x1,int y1,int x2,int y2)

{

    int dx,dy,d,incry,incre,incrne,slopegt1=0,k=0,y=0;

    dx=abs(x1-x2);dy=abs(y1-y2);

    if(dy>dx)

    {

            swap(&x1,&y1);

        swap(&x2,&y2);

        swap(&dx,&dy);

        slopegt1=1;

    }

    if(x1>x2)

    {

        swap(&x1,&x2);

        swap(&y1,&y2);

    }

    if(y1>y2)

        incry=-1;

    else

        incry=1;

    d=2*dy-dx;

    incre=2*dy;

    incrne=2*(dy-dx);

    while(x1<x2)

    {

        if(d<=0)

            d+=incre;

        else

        {

            d+=incrne;

            y1+=incry;

        }

        x1++,k++,y++;

 

           if((k%7)!=0&&(y%7)!=0)

          {

        if(((y-1)%7)!=0)

        {

        if(slopegt1)

 

 

            putpixel(y1,x1,15);

 

        else

 

 

            putpixel(x1,y1,15);

        }

        else

        {

         if(slopegt1)

 

 

            putpixel(y1,x1,10);

 

        else

 

 

            putpixel(x1,y1,10);

        }

        }

    }

}

void main()

{

//Request autodetection

    int gdriver = DETECT,gmode,errorcode;

    int xmax,ymax,x1,y1,x2,y2,l;

//Initialize graphics and local variables

    A:

    initgraph(&gdriver,&gmode,"C:\\TC\\BGI");

//Read result of initialization

    errorcode=graphresult();

    if(errorcode!=grOk) //Error occured

    {

        printf("Graphics error : %s\n",grapherrormsg(errorcode));

        printf("Press any key to halt.");

        getch();

        exit(1);

    }

    setcolor(2);

    xmax=getmaxx();

    ymax=getmaxy();

    line((xmax/2)+1,0,(xmax/2)+1,ymax);

    line(0,(ymax/2),xmax,(ymax/2));

    gotoxy(1,1);

    printf("0:Exit 1:Solid 2:Dot 3:Dash 4:DashDot ");

    gotoxy(1,3);

    printf("Enter value for first point (x1,y1) : ");

    gotoxy(1,4);

    printf("Enter value for second point (x2,y2) : ");

    gotoxy(1,2);

    printf("Which line you want : ");

    gotoxy(23,2);

    scanf("%d",&l);

    if(l==0)

        exit(0);

    if(l!=1&&l!=2&&l!=3&&l!=4&&l!=5)

    {

        gotoxy(45,2);

        printf("Enter valid choice");

        getch();

        clrscr();

        goto A;

    }

    gotoxy(40,3);

    printf("(");

    gotoxy(45,3);

    printf(",");

    gotoxy(50,3);

    printf(")");

    gotoxy(40,4);

    printf("(");

    gotoxy(45,4);

    printf(",");

    gotoxy(50,4);

    printf(")");

    gotoxy(41,3);

    scanf("%d",&x1);

    gotoxy(46,3);

    scanf("%d",&y1);

    gotoxy(41,4);

    scanf("%d",&x2);

    gotoxy(46,4);

    scanf("%d",&y2);

 

    if(l==1) midpointline((xmax/2)+x1,(ymax/2)+y1,(xmax/2)+x2,(ymax/2)+y2);

    if(l==2) dot((xmax/2)+x1,(ymax/2)+y1,(xmax/2)+x2,(ymax/2)+y2);

    if(l==3) das((xmax/2)+x1,(ymax/2)+y1,(xmax/2)+x2,(ymax/2)+y2);

    if(l==4) dasdot((xmax/2)+x1,(ymax/2)+y1,(xmax/2)+x2,(ymax/2)+y2);

    getch();

    goto A;

}