CODEWITHSUNDEEP
pythonsvgpolygon
art.zhitnik
art.zhitnik

Reputation: 624

How to determine whether a polygon is inside other one?

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?

A polygon inside other polygon

Upvotes: 4

Views: 2614

Answers (2)

mihai
mihai

Reputation: 38543

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

Upvotes: 4

Alfe
Alfe

Reputation: 59436

Not so much of a Pythonic answer, but a geometrical-algorithmical:

Polygon B is inside of polygon A iff each corner of B and each edge of B is completely inside polygon A.

To find whether a corner (a point) is inside a polygon, a simple approach is to bite off so-called "ears" off the polygon. An "ear" is a convex corner, and biting it off means to simply remove this corner. With each biting act, check whether the point is inside the ear (the triangle you bit off). (There's mathematical proof that for each loopless polygon you can find at least two such ears (convex corners).)

To find whether an edge of B is completely inside A means you have to find out whether the edge is cutting any edge of polygon A.

Of course, if both polygons are completely convex, you don't have to check the edges at all.

That's a straight-forward approach without the details on the basic geometric checks you will have to perform. But maybe it helps you.

Upvotes: 1

Related Questions