From an outline to samples
A polygon outline says where a shape ends, but a rasterizer must decide which sample positions lie inside it. For a convex polygon a horizontal line cuts the interior in at most one interval. A nonconvex polygon can have several intervals, and joining only the leftmost and rightmost intersections can fill a gap that belongs to the background. We need a rule that describes every interval and continues to work when the scanline passes through a vertex.
Here a polygon is simple: its finitely many straight edges form one closed non-self-intersecting boundary, with consecutive edges meeting only at their shared endpoint. Assume nonzero edges and that no nonconsecutive edges meet. Vertices and sample coordinates are exact real numbers. A polygon may be concave and may have horizontal edges. We classify one point at a time; the resulting binary sample mask is not the area of the polygon in a pixel. The boundary convention below is explicitly chosen for this note, not a claim about a particular graphics API.
Definition 2.6.1
(Interior, boundary, and the even-odd sample rule)
The Jordan curve theorem says that a simple closed polygonal curve separates the plane into one bounded interior and one unbounded exterior. We call a sample covered if it is in the interior or on the boundary. For a sample not on the boundary, the even-odd rule starts outside at the far right and toggles its state on each boundary crossing of a horizontal ray. An odd number of crossings means interior.
The boundary test comes first. This choice makes a standalone polygon closed, but drawing two adjacent polygons independently can write a common-edge sample twice. A mesh rasterizer needs a separate, consistent ownership convention if it requires precisely one writer. Neither convention changes areas, because a finite union of line segments has area zero.
Events on a scanline
Let a nonhorizontal edge have endpoints and . Reorder the endpoints as and so that . For a scanline height , include the edge exactly when
Its event coordinate is obtained by linear interpolation:
Horizontal edges generate no crossing event. They still participate in the separate boundary test. Collect the event coordinates in a multiset, preserving equal values and their multiplicities, then sort them as . Do not discard duplicate coordinates: two equal events represent two toggles, which cancel away from that coordinate.
Theorem 2.6.2
(Exact parity with the half-open endpoint convention)
For any simple polygon and real height , the event multiset above has even cardinality. For any point not on its boundary, the point lies in the interior exactly when the number of events strictly to the right of is odd. Equivalently, after sorting, it lies in one of the open intervals , with empty intervals allowed. If the point is on the boundary, return covered before applying this statement.
Proof
(Even parity from small upward perturbations)
First suppose is different from every vertex height. Each intersection is in the interior of a nonhorizontal edge. At an intersection the horizontal line crosses the boundary locally, so it switches between interior and exterior. Far to either side it is exterior because the polygon is bounded. The switches therefore occur an even number of times, and counting them from the right gives the stated parity. This uses the separation property in the definition, not convexity.
Now allow to equal vertex heights and fix a point off the boundary. The boundary is compact, so the point has a positive distance from it. Choose a sufficiently small such that is not a vertex height and the vertical segment from to misses the boundary. The two points have the same interior/exterior state. For each nonhorizontal edge, its intersection at height exists for all sufficiently small positive precisely when , and then its coordinate tends to . Horizontal edges have no such intersection. No limiting event can equal , since that would put on the boundary. Consequently the number of events to the right of eventually agrees with the number of intersections to the right at height . The first case proves the parity. Taking sufficiently far to the left also proves that the total number of events is even. Sorting gives the paired-interval formulation; if adjacent events coincide, the corresponding open interval is empty.
Proof X-ray
Why one endpoint is included and the other excluded
Think of the scanline at height as the limit of scanlines just above it. At a local minimum two edges begin and produce two coincident events; at a local maximum neither edge continues above. At a non-extremal vertex one edge continues above. These counts are two, zero and one respectively. A horizontal edge is handled by the same limiting argument, while points on that edge are classified separately. Counting both endpoints of every edge would count an ordinary vertex twice and can reverse the answer.
The theorem's open intervals are a statement only about points off the boundary. An event coordinate may itself be a boundary point; do not infer its status from an open interval. Likewise, a sample on a horizontal edge may lie strictly between events, yet it is a boundary point, not an interior point. The boundary-first convention settles both cases.
Counterexample mode
Counting both endpoints of every edge
The claim: include an edge whenever , so that no vertex is missed. Take the convex pentagon and . The vertex is an ordinary pass-through vertex, yet both edges at it are active and give the events . The interior point then has two events to its right and would be called exterior. With the half-open rule the events are , and has one event to its right, so it is interior.
A complete trace
Worked example 2.6.3
(A U-shaped polygon)
Take the vertices in order
At , only four vertical edges cross the scanline. Their sorted events are . The interior intervals are and . Thus and are inside, whereas lies in the open notch and is outside. The boundary points and are covered by the stated boundary rule.
At , the same four events occur because the lower endpoints at and are included. However, lies on the horizontal notch edge and is covered by the boundary test, even though its even-odd crossing count is even. At the upper endpoints are excluded, so there are no events; the top horizontal edges are still boundary and hence covered. This distinction is exactly why horizontal edges cannot simply be deleted from the polygon itself.
Worked example 2.6.4
(A scanline through a notch vertex)
Take the vertices in order
The edges to and to give the events and for . The edge from to has , so its event is ; the edge from to has event ; both are active for . The bottom edge is horizontal and gives no event.
At the events are , so and are interior and lies in the notch. At the vertex is a local minimum of the upper outline, so both of its edges are included and both events equal : the list is . The point has the three events to its right, an odd number, so it is interior; has one event to its right and is interior; the tip is on the boundary and covered. The whole row from to is therefore covered. Dropping one of the two equal events would give an even count and classify it as exterior. At every upper endpoint is excluded, so there are no events: and are covered as boundary points, while is not on the boundary and is exterior.
Worked example 2.6.5
(A horizontal edge between a falling and a rising edge)
Take the vertices in order
The nonhorizontal edges are for , for , and for . At the events are , so is interior. At the edge is excluded at its upper endpoint, the edge is included at its lower endpoint, and the horizontal edge from to gives nothing, so the events are . The chain of falling edge, horizontal edge and rising edge contributes one event, exactly as an ordinary vertex would.
The point has one event to its right and is interior. The point has none and is exterior. The point also has no event to its right, so parity alone would call it exterior, but it lies on the horizontal edge and the boundary test returns covered. This is the case the preliminary boundary test exists for.
Counterexample mode
Why two extreme intersections do not suffice
At height the extremes of the U are and . Filling everything between them incorrectly covers . The mistake is to assume that a horizontal section of every polygon is connected. Convexity would justify that assumption; simplicity alone does not.
Common mistake
(Merging equal events)
At a local minimum two edges start at the same coordinate, so the list contains that value twice. Deleting duplicates to tidy the list turns from the notch example into , which has odd length and no final pair. The interior point then has the two events to its right and is wrongly called exterior. Keep the multiplicities: the two equal toggles cancel to the right of , and sees .
Common mistake
(Letting parity override the boundary)
The parity statement classifies only points off the boundary. On the row of the U-shaped polygon there are no events, so every count is even, yet lies on the top edge from to and is covered. Likewise has an even count but lies on the notch edge. Always run the boundary test first.
A precise algorithm and rational arithmetic
For each sample :
- Test whether the sample lies on any closed polygon edge. If so, return covered.
- For every nonhorizontal edge whose lower and upper endpoint heights satisfy , compute its event coordinate.
- Count events with , retaining duplicates. Return covered exactly when the count is odd.
Proposition 2.6.6
(Correctness of the sample test)
The three-step procedure returns covered for a sample exactly when the sample lies in the closed polygon, that is, in the interior or on the boundary.
Proof
(Boundary first, then parity)
If the sample lies on an edge, step 1 returns covered, which agrees with the definition. Otherwise step 1 passes, and steps 2 and 3 compute exactly the event multiset and the number of events to the right of used in the theorem. By the theorem, an odd count means interior and an even count means exterior. An exterior point is neither interior nor on the boundary, so it is correctly not covered.
For many sample positions on the same row, compute and sort the events once, then walk the sorted samples and events together.
Proposition 2.6.7
(Cost of classifying one row)
Fix the row at height of a polygon with edges, and let samples lie on that row. Leaving out the boundary test of step 1, computing the events takes arithmetic operations, sorting them takes comparisons, and sorting the samples takes comparisons. Once both lists are sorted, one simultaneous pass classifies all samples with further comparisons.
Proof
(One monotone pass over two sorted lists)
Each edge needs one test and at most one interpolation, so there are operations and at most events. Sort events and samples in decreasing order, and keep a pointer into the event list together with the number of events strictly greater than the current sample. For the next sample , advance the pointer while the current event exceeds , adding one to each time. Then is interior exactly when is odd. Because the samples decrease, the pointer never moves backwards, so it makes at most moves in total, and each sample is handled once.
If the samples arrive already sorted, the term disappears. A naive boundary test for every sample costs additional segment tests. An active-edge table may avoid rescanning every edge on each row, but its maintenance and boundary costs must be accounted for separately.
Concept lensAlgorithmic
Edges as a sweep with a constant increment
Write for the inverse slope of a nonhorizontal edge. The event formula is affine in , so , and whenever the edge is active at both and we have . The edge is active on the half-open height interval , so a sweep keeps a list of active edges that changes only at vertex heights and moves each event by one addition per row. For the edge from to we have , and the events at and are and . With exact rational arithmetic is a fixed rational and the update is exact; accumulating a rounded in floating point drifts away from the interpolation formula.
For integer vertex coordinates and a rational sample height, event coordinates are rational. One can compare rational values by cross multiplication after arranging positive denominators, avoiding a rounding choice in event order. A point lies on a segment from to exactly when its two-dimensional cross product with vanishes and both its coordinates lie between the corresponding endpoint coordinates. These exact comparisons require unbounded integers, or a proven sufficient integer width; fixed-width overflow can change parity. Floating-point equality, nearly coincident intersections and API-specific tie rules require additional numerical design.
Practice
Quick check
(For the U-shaped polygon, classify , and under the boundary-first convention.)
Compute the events at height first.
Solution · Answer
The events at height are . The first point is in the notch and exterior; the second is on the boundary and covered; the third lies in and is interior.
Quick check
(A triangle has vertices . List the scanline events at and . Classify .)
Remember which endpoint of each edge is excluded.
Solution · Answer
At the sloping edges give . At both upper endpoints are excluded, so the event list is empty. Nevertheless is the top vertex and is covered by the preliminary boundary test.
Quick check
(A nonhorizontal edge runs from to . Find its event at and determine whether it is active at .)
Use the interpolation formula with and .
Solution · Answer
Interpolation gives . The upper endpoint height is excluded, so the edge is inactive there.
Quick check
(Two coincident events occur at and no others lie between and . Does moving a sample from to change parity? Can one conclude that is exterior?)
Count the toggles between the two samples, then ask what kind of point is.
Solution · Answer
Two toggles leave the parity unchanged. The event point itself is on the polygon boundary, so under our convention it is covered; parity away from the event does not classify it.
Quick check
(Explain why two adjacent polygons each using the boundary-first rule can both cover the same sample, and give one way to avoid duplicate writes without changing polygon areas.)
Consider a sample on the common edge.
Solution · Answer
A sample on their common edge belongs to both closed boundaries. A mesh-wide half-open ownership rule can assign that edge to only one polygon, with a consistent vertex policy. Boundary segments have area zero, so changing their ownership does not change the geometric area of either polygon.