
Algorithm to determine if one polygon is inside another polygon 
Steve Terry
Member #1,989
March 2002

Ok, I have a series of connected lines and arcs and I need to determine if one connected set is inside another connected set. Here is what I mean: How do I algorithmically determine the smaller shape is contained by the larger shape? Here is the information I have, endpoints of each line/arc, midpoints and angle of each arc, angle between two lines, minimum distance between two lines, angle between midpoint and line, minimum distance between midpoint of arc and line. I have several "shapes" and some can have shapes contained in them and I need to group the shapes as separate objects. ___________________________________ 
Arthur Kalliokoski
Second in Command
February 2005

My first thought was the point in polygon test, but it's easy to imagine a rectangle in another polygon with a notch in it that would fail. The other way is to algorithmically determine where the lines intersect, (and they surely do), but then see if the point of intersection is between the points of the vertices. If a line is vertical, test the y's, else test the x's. http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/ [EDIT] “Throughout history, poverty is the normal condition of man. Advances which permit this norm to be exceeded — here and there, now and then — are the work of an extremely small minority, frequently despised, often condemned, and almost always opposed by all rightthinking people. Whenever this tiny minority is kept from creating, or (as sometimes happens) is driven out of a society, the people then slip back into abject poverty. This is known as "bad luck.” ― Robert A. Heinlein 
Steve Terry
Member #1,989
March 2002

I'm not sure I follow your second suggestion though I can get the intersection point of two lines as well. ___________________________________ 
Arthur Kalliokoski
Second in Command
February 2005

I meant that if the intersection point for a line of one polygon and a line of the other polygon is at x,y, then see if (x1 < x < x2) where x1 and x2 are the x's for a line segments endpoints. If the line is vertical, obviously x1 and x2 will be the same, so test for the y values instead. “Throughout history, poverty is the normal condition of man. Advances which permit this norm to be exceeded — here and there, now and then — are the work of an extremely small minority, frequently despised, often condemned, and almost always opposed by all rightthinking people. Whenever this tiny minority is kept from creating, or (as sometimes happens) is driven out of a society, the people then slip back into abject poverty. This is known as "bad luck.” ― Robert A. Heinlein 
Onewing
Member #6,152
August 2005

According to my Introduction to Algorithms book from college: Quote: One way to determine whether a point p0 is in the interior of a simple, but not necessarily convex, polygon P is to look at any ray from p0 and check that the ray intersects the boundary of P an odd number of times but that p0 itself is not on the boundary of P. Here's kind of pseudocode I would do: You have polygons P1 and P2. 1. See if the first point in P1 is in P2. If it is, go to step 2, if not, go to step 4  
SiegeLord
Member #7,827
October 2006

Without thinking too much, I would first check if the two boundaries intersect. If they don't, I check a single point of each polygon to see if it is inside the other polygon. If they don't intersect, and one point is inside the other polygon, the polygon which owns that point is completely inside the other polygon. "For in much wisdom is much grief: and he that increases knowledge increases sorrow."Ecclesiastes 1:18 
23yrold3yrold
Member #1,134
March 2001

I don't think there's any easy way unless you're dealing with exclusively convex polygons. And the best method I've heard of for dealing with that is checking to see if any one side in either polygon can act as a separating plane. If one can, they're not touching. If none can, it's a collision.  
Albin Engström
Member #8,110
December 2006

Long ago I didn't finish a game that used line collision detection in the editor for that kind of problem, It seemed to work well, I would imagine it would be demanding after a while so there's a few things you can do to speed it up: 1: Subdivide the lines into boxes and only check agains relevant lines. Maybe you need something else, but this should do the trick. EDIT: This is only usefull for polygons on the same plane.. 
Arthur Kalliokoski
Second in Command
February 2005

23yrold3yrold said: I don't think there's any easy way unless you're dealing with exclusively convex polygons I don't see a problem with nonconvex polygons (his example image shows both polygons as what I would call nonconvex, i.e. not pass the rubberband test) but there would be a problem with complex polygons (some of the lines in the same polygon intersect). Perhaps there's a problem with terminology here. [EDIT] Steve Terry said: I have a series of connected lines and arcs "Arcs" as a section of a circle or ellipse would be much harder indeed. [EDIT2] “Throughout history, poverty is the normal condition of man. Advances which permit this norm to be exceeded — here and there, now and then — are the work of an extremely small minority, frequently despised, often condemned, and almost always opposed by all rightthinking people. Whenever this tiny minority is kept from creating, or (as sometimes happens) is driven out of a society, the people then slip back into abject poverty. This is known as "bad luck.” ― Robert A. Heinlein 
Kibiz0r
Member #6,203
September 2005

If you weren't using concave shapes, you could use the dot product.  
jhuuskon
Member #302
April 2000

What SiegeLord said. Split the the large shape into convex shapes to make it easier to check the points as 23 implied. You don't deserve my sig. 
Steve Terry
Member #1,989
March 2002

Well this is not for a game style application but rather a CAD style application so accuracy is important but we are not shooting for 60fps here. I would be happy if the algorithm finished with a relatively complex set in under 60s. The arcs do complicate things even more but I think I can subdivide the arcs into points and "fake" some lines for boundary checking. I think for now I can do the point in polygon check since I do have algorithms for intersecting lines with lines and arcs to determine the intersection point. ___________________________________ 
Thomas Harte
Member #33
April 2000

I second SiegeLord and jhukkson, but would add that the GLU tesselator is really useful if you need to break a polygon into a convex set. If you want a really quick and easy test and have either a tesselator (set to in/out tesselation — the GLU tesselator can do that) or a CSG module to hand, maybe you could just compare the sum of the areas of the two polygons separately to the area of the two tesselated together? If the two totals are the same then they don't overlap. Area of a simple polygon is trivial regardless of whether the polygon is convex, I refer you to question 2.01 of the comp.graphics.algorithms FAQ. [My site] [Tetrominoes] 
alethiophile
Member #9,349
December 2007

Perhaps: Check if all points of either are inside the other. If true, check if any points of the other are inside the first. If the first gives true and the second false, then it's inside.  
Johan Halmén
Member #1,550
September 2001

So do you just want a function that returns bool? First test would be checking if any of the inner set vertices (or arc points) lie outside the outer set. Second test would check for intersecting segments, like check every segment against every segment. The second test is needed for this: Well, can't think of a third needed test. Anyway, it's probably more clever to only test a against b and not also vice versa. Simpler logic. As I asked in the beginning, do you only want a bool return value? Like: Then you do. polygon a(...), b(...); ... if (a.inside(&b)  b.inside(&a)) ....
<edit /> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Years of thorough research have revealed that what people find beautiful about the Mandelbrot set is not the set itself, but all the rest. 
GameCreator
Member #2,541
July 2002

I would use pmask, but that's because I'm allergic to math.

Dennis
Member #1,090
July 2003

{"name":"598619","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/a\/2\/a2a26dda6c35feed3d8a72eda72c41ff.png","w":1151,"h":296,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/a\/2\/a2a26dda6c35feed3d8a72eda72c41ff"} Arthur Kalliokoski said: My first thought was the point in polygon test, but it's easy to imagine a rectangle in another polygon with a notch in it that would fail. Wouldn't it be sufficient to just do two checks then? edit: Ah, just saw Johans image with the orange and green polygon, so no, that would not be sufficient. SiegeLord said: Without thinking too much, I would first check if the two boundaries intersect. If they don't, I check a single point of each polygon to see if it is inside the other polygon. If they don't intersect, and one point is inside the other polygon, the polygon which owns that point is completely inside the other polygon. For C and D in the image above, their bounding boxes do not intersect (their areas do though) and there is at least one point of each lying in the other polygon, yet neither of them is fully inside of the other one. edit2:Ah, sorry, misread what you said. You're not saying anything about bounding rectangles, which is what I automatically read when I read boundaries. 
Paul whoknows
Member #5,081
September 2004

Use pointpolygon collision detection. If all points of polygon A collided with polygon B then polygon A is inside polygon B. For special cases like the one Johan posted, calculate all the points of polygon A and add to them the point of the center of polygon A and calculate if all of them collided against polygon B. This algorithm will fail in some very particular cases, but it will work for most cases. ____ "The unlimited potential has been replaced by the concrete reality of what I programmed today."  Jordan Mechner. 
