decomposing an intersecting polygon?

[Jeff Erickson]

Joe Strout wrote:
> 
> I'm looking for an algorithm to decompose a self-intersecting 2D
> polygon into a set of non-intersecting polygons, according to the
> "odd-even" winding rule.  That is, if the polygon defines a
> five-pointed star by five lines, the center of the star should not be
> filled.
 
You can find all the intersections between edges using a sweepline
algorithm.  The algorithm runs in O((n+k)log n) time, where n is the
original number of edges and k is the number of pairwise intersections. 
See Joe O'Rourke's _Computational Geometry in C" for details.

Once you have the intersection points, decomposing the self-intersecting
polygon into simple components is, er, "easy".  Whenever you see an
intersection point, turn instead of going straight.

Actually, the sweepline algorithm could be used to fill the polygon
directly, instead of decomposing it first.  Just follow the
inside-outside rule on each one-dimensional slice.  Same running time,
but fewer data structures -- all you need is a balanced binary tree to
store the cross-section and a priority queue to find the next place to
stop the sweep line.

-- 
Jeff Erickson                                 mailto:jeffe at cs.uiuc.edu
Computer Science Department                 http://www.uiuc.edu/~jeffe
University of Illinois, Urbana-Champaign