Scribd
Upload
15 views10 pages

Line Drawing Algorithms Explained

The document discusses and compares several algorithms for drawing lines on a raster (pixel-based) display: 1. A simple line drawing algorithm that works well for slopes less than 1 but gives unsatisfactory results for slopes greater than 1. 2. The DDA (Digital Differential Analyzer) line drawing algorithm, which improves upon the simple algorithm by using integer calculations. 3. Bresenham's line drawing algorithm, which is accurate and efficient using only integer calculations. It determines the next sample position along the line based on comparing the distance of two potential pixel positions to the actual path. 4. The midpoint line drawing algorithm, which uses the implicit definition of a line to determine if the next

Uploaded by

Ayushi Tewari
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
15 views10 pages

Line Drawing Algorithms Explained

The document discusses and compares several algorithms for drawing lines on a raster (pixel-based) display: 1. A simple line drawing algorithm that works well for slopes less than 1 but gives unsatisfactory results for slopes greater than 1. 2. The DDA (Digital Differential Analyzer) line drawing algorithm, which improves upon the simple algorithm by using integer calculations. 3. Bresenham's line drawing algorithm, which is accurate and efficient using only integer calculations. It determines the next sample position along the line based on comparing the distance of two potential pixel positions to the actual path. 4. The midpoint line drawing algorithm, which uses the implicit definition of a line to determine if the next

Uploaded by

Ayushi Tewari
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd

Simple line drawing algorithm

Draw line(int x1,int y1,int x2,int y2)


{ float y; int x; for( x=x1;x<=x2;x++) //slope < 1. { y=y1+(x-x1)*(y2-y1) / (x2-x1); putpixel(x, round(y)); }

line drawing algorithms

For slope >1 this algorithm gives unsatisfactory results. The solution: symmetry. The assigning of one coordinate axis the name x and other y was an arbitrary choice. slope>1 under one assignment result in slope< 1when the names are reversed.

DDA line drawing algorithm #define ROUND(a) ( (int) (a + 0.5) ) Void lineDDA (int x1,int y1,int x2,int y2) { int dx=x2-x1,dy=y2-y1,steps,k; float xinc,yinc ,x=x1,y=y1; if (abs(dx)>abs(dy)) steps=abs(dx); else

steps=abs(dy);
xinc= dx/(float)steps;

DDA line drawing algorithm cont. yinc= dy/(float)steps; Putpixel(ROUND(x),ROUND(y)); For( k=0;k<steps;k++){

x+= xinc;
y+=yinc;

Putpixel(ROUND(x),ROUND(y)); }
}

Bresenhams line drawing algorithm


An accurate and efficient raster line algorithm.
Only integer calculations are required.

yk+2 13 yk+1 12 yk 11 10 10 xk 11 xk+1 12 13

Next sample position should be (11,11) or (11,12)?

Test the sign of an integer parameter whose value is proportional to the distance between the separation of the two pixel positions from the actual path.

Bresenhams line drawing algorithm

yk+1 y yk

d2 d1

Distance of the true point from the scan line.

Bresenhams line drawing algorithm


1) Input two endpoints.x1,y1,x2,y2. 2) x=x1,y=y1. 3) Calculate constants x, y,2y and 2y- 2x. 4) Now initial decision parameter p0 = 2y- x. 5) At each scan line ,starting at k=0 check: If pk <0 next point is(xk + 1, yk )

Else

pk+1 = pk +2y
next point is(xk + 1, yk+1) pk+1 = pk +2y -2x

6) Repeat step 5 x times.

Midpoint line drawing algorithm


makes use of the the implicit definition of the line, F(x,y) = 0.

NE Q M P(x1,y1) E

P(x1,y1) is selected point, now next is E or NE? Q is the intersection point of a line with column xk+1 . Which side of the line the mid point M lies ? The distance between chosen pixel and actual line is always less than .

Midpoint line drawing algorithm


Drawline( int x1,int y1,int x2,int y2)
int dx, dy,d, ince, incne, x, y; dx= x2-x1; dy = y2-y1; d = 2*dy dx;

ince = 2*dy; incne = 2*(dy-dx);


for( x=x1;x<=x2;x++) { putpixel(x, y, 15); if( d>0) { d = d+ incne;

y= y1;

y = y + 1;
else

d = d+ ince; }

} }

You might also like