decomposing an intersecting polygon?
Guido van Rossum
guido at cnri.reston.va.us
Fri Sep 24 15:06:56 EDT 1999
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/)
More information about the Python-list
mailing list