decomposing an intersecting polygon?

[Guido van Rossum]

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.

I'm not sure if it uses the odd-even rule, nor how easily it can be
converted to what you're looking for, but there's code in Grail that
checks whether a point is inside or outside a polygon.  I'll copy it
here:

    def poly_pointin(self, x, y):
        """Is point (x,y) inside polygon with vertices coords?

        From C code by Paul Bourke at
        <http://www.auckland.ac.nz/arch/pdbourke/geometry/insidepoly.html>
        Determining whether or not a point lies on the interior of a polygon.

        The algorithm is a little pesky because a point on an edge of the
        polygon doesn't appear to be treated as *in* the polygon. Not doing
        anything about this at the moment.
        """

        counter = 0
        p1 = self.coords[0]
        for i in range(1,len(self.coords)):
            p2 = self.coords[i]
            if y > min(p1[1], p2[1]):
                if y <= max(p1[1], p2[1]):
                    if x <= max (p1[0], p2[0]):
                        if p1[1] != p2[1]:
                            xintersect = \
                              (y-p1[1])*(p2[0]-p1[0])/(p2[1]-p1[1])+p1[0]
                            if p1[0] == p2[0] or x <= xintersect:
                                counter = counter + 1
            p1 = p2
    
        return counter % 2

--Guido van Rossum (home page: http://www.python.org/~guido/)