Allegro.cc - Online Community

Allegro.cc Forums » Off-Topic Ordeals » Algorithm to determine if one polygon is inside another polygon

This thread is locked; no one can reply to it. rss feed Print
Algorithm to determine if one polygon is inside another polygon
Steve Terry
Member #1,989
March 2002
avatar

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:
{"name":"598600","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/9\/b\/9b9b66f2414a68a371789e002b2c4be0.jpg","w":551,"h":296,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/9\/b\/9b9b66f2414a68a371789e002b2c4be0"}598600

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.

___________________________________
[ Facebook ]
Microsoft is not the Borg collective. The Borg collective has got proper networking. - planetspace.de
Bill Gates is in fact Shawn Hargreaves' ßî+çh. - Gideon Weems

Arthur Kalliokoski
Second in Command
February 2005
avatar

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]
Found my latest sig there!

“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 right-thinking 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
avatar

I'm not sure I follow your second suggestion though I can get the intersection point of two lines as well.

___________________________________
[ Facebook ]
Microsoft is not the Borg collective. The Borg collective has got proper networking. - planetspace.de
Bill Gates is in fact Shawn Hargreaves' ßî+çh. - Gideon Weems

Arthur Kalliokoski
Second in Command
February 2005
avatar

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 right-thinking 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
avatar

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
2. Take the next point in P1 and see if it is inside P2. If it is, go to step 3, if not, neither polygon is completely inside the other.
3. Take the line segment from the point in step 1 and the point in step 2 and see if it interesects with any segment in P2. If it doesn't, go to step 2 (until all points in P1 are done), otherwise the test fails.
4. Try to see if P2 is in P1. Essentially, go back to step one and switch P1 with P2 in the order of testing.

------------
Solo-Games.org | My Tech Blog: The Digital Helm

SiegeLord
Member #7,827
October 2006
avatar

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
[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]

23yrold3yrold
Member #1,134
March 2001
avatar

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.

--
Software Development == Church Development
Step 1. Build it.
Step 2. Pray.

Albin Engström
Member #8,110
December 2006
avatar

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.
2: Only check lines that have been changed (update).

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
avatar

I don't think there's any easy way unless you're dealing with exclusively convex polygons

I don't see a problem with non-convex polygons (his example image shows both polygons as what I would call non-convex, 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]

I have a series of connected lines and arcs

"Arcs" as a section of a circle or ellipse would be much harder indeed.

[EDIT2]
While playing with a new Firefox extension, I decided to Google the problem.

http://www.google.com/#hl=en&q=how+to+determine+if+one+polygon+is+entirely+within+another+polygon&btnG=Google+Search&aq=f&oq=how+to+determine+if+one+polygon+is+entirely+within+another+polygon&fp=jdOYMfF-0fs

“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 right-thinking 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
avatar

If you weren't using concave shapes, you could use the dot product.

jhuuskon
Member #302
April 2000
avatar

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
avatar

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.

___________________________________
[ Facebook ]
Microsoft is not the Borg collective. The Borg collective has got proper networking. - planetspace.de
Bill Gates is in fact Shawn Hargreaves' ßî+çh. - Gideon Weems

Thomas Harte
Member #33
April 2000
avatar

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.

alethiophile
Member #9,349
December 2007
avatar

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.

--
Do not meddle in the affairs of dragons, for you are crunchy and taste good with ketchup.
C++: An octopus made by nailing extra legs onto a dog.
I am the Lightning-Struck Penguin of Doom.

Johan Halmén
Member #1,550
September 2001

So do you just want a function that returns bool?
I'd imagine a function that first checks some simple thing and returns false (isn't inside) or continues with next check and returns false or continues with next more complicated test. And so on. Until you are sure to return true.

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:
{"name":"598618","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/a\/d\/ad6a792312c90c2603c0963b605cd440.png","w":794,"h":1123,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/a\/d\/ad6a792312c90c2603c0963b605cd440"}598618

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:

class polygon
{
    ...
    bool inside(polygon *another);
    ...
};

Then you do.

    polygon a(...), b(...);
    ...
    if (a.inside(&b) || b.inside(&a))
        ....

<edit />
Don't name it polygon, though :P

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Years of thorough research have revealed that the red "x" that closes a window, really isn't red, but white on red background.

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
avatar

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

Dennis
Member #1,090
July 2003
avatar

{"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"}598619

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?
First, check if all points of polygon B are inside of polygon A. Then checks if all points of polygon A are NOT inside of polygon B (or respectively for D and C, see image above). In any case, the first check should always be a boundary box collision check and all the other checks should only be made if the boundary box areas collide.

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
avatar

Use point-polygon 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.

Go to: