decomposing an intersecting polygon?
Jeff Erickson
jeffe at cs.uiuc.edu
Fri Sep 24 14:38:17 EDT 1999
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
More information about the Python-list
mailing list