How to determine whether a polygon is inside other one?

Question

I have a simple example (SVG source) looks like you can see below. The path with id "rect2816" described in d attribute:

m 140.53571,188.625 0,148.1875 273.9375,0 0,-148.1875 -273.9375,0 z 
m 132.25,42.03125 c 3.64586,0.0236 7.47296,0.12361 11.5,0.28125 36.65941,1.43507 57.84375,15.88072 57.84375,32.84375 0,7.41614 -1.94981,21.58652 -13.28125,24.09375 -14.58711,3.2276 -40.46224,-5.35276 -53.125,6.625 -26.65285,25.21104 -48.00843,-19.04537 -57.875,-32.84375 -12.16196,-17.00847 0.24962,-31.35357 54.9375,-31 z

Here, the first line describes parent polygon, the second - the hole (as you can see). But How can I find this hole program way? I'm using Python. Maybe there is some library for easy solution?

Answer 1

Transform the paths into (x,y) pairs and apply this function for each point of the second polygon.

# determine if a point is inside a given polygon or not
# Polygon is a list of (x,y) pairs.

def point_inside_polygon(x,y,poly):

n = len(poly)
inside =False

p1x,p1y = poly[0]
for i in range(n+1):
    p2x,p2y = poly[i % n]
    if y > min(p1y,p2y):
        if y <= max(p1y,p2y):
            if x <= max(p1x,p2x):
                if p1y != p2y:
                    xinters = (y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x
                if p1x == p2x or x <= xinters:
                    inside = not inside
    p1x,p1y = p2x,p2y

return inside

Source: https://web.archive.org/web/20140301111830/http://www.ariel.com.au/a/python-point-int-poly.html