Find if one Polygon is inside another

Question

I want to find out if one polygon is inside another by giving an array of points of each vertex. Is there any simple way to do that? Edit: it's not enough to check whether minimum point of inner is greater than outer and maximum point for outer is less then inner. It's not the sufficient condition. Proof:

Answer 1

Once you've checked that the minimum bounding box for polygon A lies inside that for polygon B I think you're going to have to check each edge of A for non-intersection with all the edges of B.

This is, I think, a simple approach, but I suspect you really want a clever approach which is more efficient.

Answer 2

I have done something very similar using Java2D particularly the Area class. The code for that class is freely available if you want to replicate the functionality. An easier option might be to look at this library: http://www.cs.man.ac.uk/~toby/alan/software/ It should allow you to do what you want or give you starting points anyway.

Answer 3

1. some point of polygon1 lies inside of polygon2

   you can use ray casting here

2. there are no edge-edge intersection between polygons

   for large numbers of edges space-partition trees may increase speed, for small number of edges N*M enumeration is OK

Answer 4

First, use axis-aligned boundary boxes to see if they're anywhere near one another. (Essentially, draw an X-Y aligned box around each one and see if they are intersecting. This is MUCH easier than the case for polygons and generally saves a lot of time.)

If the boxes intersect, you should now perform detailed intersection testing. You'll want to draw a line perpendicular to each side of the "outside" polygon and project all of the points from both of them onto the line. Then, check that the resulting points for the inside polygon are between the points projected from the outside polygon.

I understand that example is difficult to visualize at first- I recommend this tutorial about collision detection to people interested in this area:

http://www.wildbunny.co.uk/blog/2011/04/20/collision-detection-for-dummies/

However, your task is slightly different as mentioned because you are projecting onto the perpendicular line for each side and you need ALL of them to contain the segment. I also suggest boning up a bit on the notion of a projection and your linear algebra if you want to do a lot of this.

Answer 5

Your question is underdetermined - just giving the coordinates of each vertex is not enough to specify a polygon. Example: draw a square and fill in the diagonals. Your five vertices are the square's corners and the point at the diagonals' intersection. From these vertices, it is possible to construct four different polygons: each one is constructed by using the edges of the original drawing, while removing one single edge from the square and limiting the diagonals (I hope this is clear enough).

EDIT: Apparently it wasn't clear enough. Let a1, a2, a3, a4 be vertices corresponding to the four points of a square (say, clockwise from top left), and let a5 be a vertex corresponding to the intersection of the square's diagonals. Just for the sake of the example, here are two polygons which fit the above vertices: 1. (a1,a2),(a2,a5),(a5,a3),(a3,a4),(a4,a1). This should look like a right-facing pacman. 2. (a1,a2),(a2,a3),(a3,a4),(a4,a5),(a5,a1). This should look like a left-facing pacman.