Line drawing algorithm
|
|
A line drawing algorithm is a graphical algorithm for approximating a line segment on discrete graphical media. On discrete media, such as pixel-based displays and printers, line drawing requires such an approximation (in nontrivial cases).
On continuous media, by contrast, no algorithm is necessary to draw a line. For example, oscilloscopes use natural phenomena to draw lines and curves.
A naïve line-drawing algorithm
dx = x2 - x1
dy = y2 - y1
for x from x1 to x2 {
y = y1 + (y2 - y1) * (x - x1)/(x2 - x1)
plot(x, y)
}
It is assumed here that the points have already been ordered so that <math>x_2 > x_1<math>. This algorithm works just fine when <math>dx >= dy<math>, but it is quite slow on a digital computer, as it requires floating-point calculations. If <math>dx < dy<math>, the line becomes quite sparse, and in the limiting case of <math>dx = 0<math>, only a single point is plotted!
List of line drawing algorithms
The following is a partial list of line drawing algorithms:
- Bresenham's line algorithm — optimized to use only additions (i.e. no divisions or multiplications); it also avoids floating-point computations.
- Xiaolin Wu's line algorithm — can perform anti-aliasing