line | |
circle |
line | |
circle |
line | |
circle |
Drawing lines on a raster grid implicitly involves approximation. The general process is called rasterization or scan-conversion. What is the best way to draw a line from the pixel (x1,y1) to (x2,y2)? Such a line should ideally have the following properties.
DrawLine(x1,y1,x2,y2) int x1,y1,x2,y2; { float y; int x; for (x=x1; x<=x2; x++) { y = y1 + (x-x1)*(y2-y1)/(x2-x1) SetPixel(x, Round(y) ); } }
DrawLine(x1,y1,x2,y2) int x1,y1,x2,y2; { float m,y; int dx,dy,x; dx = x2 - x1; dy = y2 - y1; m = dy/dx; y = y1 + 0.5; for (x=x1; x<=x2; x++) { SetPixel(x, Floor(y) ); y = y + m; } }
The midpoint algorithm makes use of the the implicit definition of the line, F(x,y) = 0. The N/NE decisions are made as follows.
Now we would like an integer-only algorithm.
Define
drawline(x1, y1, x2, y2, colour) int x1, y1, x2, y2, colour; { 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); y = y1; for (x=x1; x<=x2; x++) { setpixel(x, y, colour); if (d>0) { d = d + incNE; y = y + 1; } else { d = d + incE; } } }