Thus by performing one addition, we can incrementally compute the value of *y*
for each value of *x*. Note that we need real valued arithmetic as `m` is a
rational number.
To compute the pixel number we need to turn on, we just round the value `y + m`.

Let us start with the implicit form of the line equation:
F(*x,y*) = `A`*x* + `B`*y* + `C` = 0.
For consistency, assume `A` > 0 (if `A` < 0, negate all coefficients).

Suppose we the current pixel on the line = (`x _{p}, y_{p}`).
We next need to choose between pixels (

If `d _{p}` > 0, we must choose the upper pixel otherwise we choose the
lower pixel. Note that to compute

Assume we know `d _{p}`. We can then compute

**Case I**:
We choose (`x _{p}+1, y_{p}`) at the current step.

Thus, if `B` is an even number, `d _{1}` is an integer.
If

For example, if the first pixel is (`x _{p}, y_{p}`), the
decision variable

Assume ` x _{p} = x_{1} + i_{x} ` and

Now,

If the line extends beyond a horizontal boundary, the problem is more acute. Suppose the line intersects the lower boundary of the window. Check to see what happens for lines with slope close to zero, if we start at the rounded value of the intersection point. A number of pixels that are closer to the boundary than the scan-line beyond it do not get drawn. To account for this short-sightedness (no pun intended), we find the intersection with the line corresponding to half a pixel lower than the actual boundary. Now, if we round of this intersection, we start at exactly the pixel that we would have started at if the window was not truncated below this boundary.

Remember that it is not wise to change the order of drawing to, say, an always increasing primary axis. This can result in "patterned" poly-lines looking wrong.

- Compute all intersections of the polygon edges with the current scan line
- Sort all intersections
- Use Odd-Even parity rule to compute the spans of pixels that need to be turned on:
- Start with even parity.
- At each intersection flip the parity
- If the current parity is odd, draw each pixel until the next intersection (this is a span).

We use coherence in computing the intersections with the current scan-line. If the intersection of the segment with the previous scan-line is known, we can use a line drawing algorithm to compute the current intersection. Using a DDA-like algorithm (remember, now

Again, with a little manipulation we can get away with integer arithmetic. We break
`1/m` into an integer part `i` and a fractional part `r`.
Remember, we need to keep adding `1/m` to the current value of *x*.
This can be done by adding `i` each time and updating `r = N/D, N < D`.
We need to add `N/D`, `2N/D`, `3N/D`, and so on.
We keep adding `N` to the numerator until it exceeds `D`,
each time adding `i` to `x`. Once the numerator exceeds `D`,
we add 1 more to `x`, and subtract 1 from the fractional part, which is achieved
by subtracting `D` from numerator.

Remember, we must set only pixels lying in the *interior* of the polygon. Hence
on the left edges of the span, we round up, and on the right edges of a span we round
down. If the point of intersection lies exactly on a pixel, using our length convention,
on the lower end, we include the pixel, and on the upper end we exclude the pixel
from being drawn.

** Step 2 **

We use coherence in sorting again. If no new edges start at the new scan-line (i.e.,
no vertices lie at the scan line) the sorted order remains the same (remember, we are
assuming no self-intersections). If a new vertex does start, we can easily insert it
in the current list of sorted intersections, by using insertion sort.

The intersection list can easily be managed by starting with a *y* sorted list
of edges (usually a bucket sort) and maintaining the currently active list of
intersections. Once we reach a scan line at which an edge starts (by looking at the
bucket corresponding to the current scan line), we insert it into the active list.

** Step 3 **

We need to consider the special case of when a vertex of the polygon lies on the
scan line. For closed polygons, such vertices would normally be repeated as they
lie on two edges. Always counting them twice (or even once) for the odd-even parity
results in inconsistencies. However, using the following rule eliminates any such
problems:

- If the vertex is the lower of the two vertices of an edge, count it.
- Otherwise, do not count it.
- Do not count vertices of horizontal edges.