# Scan Converting Concave Polygons

## Problems

1. The scan line may intersect more than 2 times and therefore
we must sort the x intersections

2. Vertices: we want to fill from 1 to 2 and from 3 to 4, so
have vertex count as 2 intersections then each pair of lines is
in polygon interior.

But what about this case ? An odd number of of intersections
and not all pairs are in interior, e.g., (3 - 4).

Solution: generate 2 intersections only when at a local min or
max, else generate only 1 intersection.

How to generate only 1 intersection at some vertices?

Case 1: Check to see if the y coordinate is monotonically
decreasing, if yes, then increase y by 1.

Case 2: Check to see if the y coordinate is monotonically
increasing, if yes, then decrease y by 1.

In both of the above cases, the vertices will still be plotted
but will only be counted once.

Solid Polygon menu

HyperGraph
Table of Contents.

HyperGraph Home
page.

Last changed May 13, 1998, G. Scott Owen, owen@siggraph.org