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

 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:{"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"}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.deBill Gates is in fact Shawn Hargreaves' ßî+çh. - Gideon Weems
 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]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 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.deBill Gates is in fact Shawn Hargreaves' ßî+çh. - Gideon Weems
 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 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 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 42. 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 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 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 DevelopmentStep 1. Build it.Step 2. Pray.
 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.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 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 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] 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]While playing with a new Firefox extension, I decided to Google the problem. “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 If you weren't using concave shapes, you could use the dot product. ---https://www.allegro.cc/account/agreement <-- Read it, newbies.
 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. ___________________________________[ Facebook ]Microsoft is not the Borg collective. The Borg collective has got proper networking. - planetspace.deBill Gates is in fact Shawn Hargreaves' ßî+çh. - Gideon Weems
 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. --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"}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)) .... ``` Don't name it polygon, though ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~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 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? 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 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: Allegro Development Installation, Setup & Configuration Allegro.cc Comments Off-Topic Ordeals The Depot Game Design & Concepts Programming Questions Recent Threads