Simplest Line Drawing Algorithm

One method of drawing line segment is to solve the differential equation describing this process. For a straight line, we have

(4.1)

The solution is represented as:

(4.2)

where x₁, y₁, x₂, y₂ are the ends of the drawing segment and y_i is the initial value for the next step along the segment. Here is the simplest algorithm that runs in the first quadrant:

dx = x2 - x1

dy = y2 - y1

for x from x1 to x2 {

y = y1 + (dy)*(x - x1)/(dx)

plot(x, round(y))

}

It is assumed here that the points have already been ordered so that x2 > x1. This algorithm works just fine when dx > = dy (i.e., slope is less than or equal to 1), but if dx < dy (i.e., slope greater than 1), the line becomes quite sparse with lots of gaps, and in the limiting case of dx = 0, only a single point is plotted.

The simplest line drawing algorithm is inefficient and thus, slows on a digital computer. Its inefficiency stems from the number of operations and the use of floating-point calculations.

Поиск по сайту: