decomposing an intersecting polygon?

[tarka at SPAMLESS-zip.com.au]

Joe Strout <joe at strout.net> writes:

> 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.
> 
> The purpose is to implement this odd-even filling on systems that have
> no native support for it, for a cross-platform drawing library in
> Python.

If it's purely filling that you're interested in then XFree86 has some
fairly optimal filling routines implementing both the odd-even and
winding-number rules.  These could be translated into Python without
too much pain.

The routines are buried quite deep in the XFree86 sources, but I have
some trimmed down C++ versions of them which I could mail to you.

Cheers,
Steve