# How do I determine if one polygon completely contains another?

I have 2 polygons. I know the vertex coordinates of both polygons. What's the best way to check if one is completely inside the other? For example, the algorithm should only recognize the black trapezoid below as being contained: • I can't give a detailed answer right now (might do that later), but you should take a look at an implementation for the separating axis theorem for collision detection. The algorithm can be slightly modified to easily check what you want. e.g. codezealot.org/archives/55 – TravisG Jun 13 '12 at 12:51
• You are not exactly clear what you understand of a polygon inside polygon. What if all points of the smaller polygon are in the bigger one, but each of them have side on one line, are they in each other ? i47.tinypic.com/4i0sgg.jpg – speedyGonzales Jun 13 '12 at 12:51
• @speedyGonzales, this is alos called inside. – user960567 Jun 14 '12 at 3:49

There are tons of source snippets for a method that performs a test for "point inside polygon". The principle comes from Jordan's curve theorem for polygons (http://www-cgrl.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Octavian/compgeom.html).

The naive way would be: having that method, call it PointInsidePolygon(Point p, Polygon poly):

  bool isInside = true;
for each (Point p in innerPoly)
{
if (!PointInsidePolygon(p, outerPoly))
{
isInside = false; // at least one point of the innerPoly is outside the outerPoly
break;
}
}
if (!isInside) return false;
// COMPULSORY EDGE INTERSECTION CHECK
for each (innerEdge in innerPoly)
for each (outerEdge in outerPoly)
{
if (EdgesIntersect(innerEdge, outerEdge))
{
isInside = false;
break;
}
}

return isInside;


Theoretically, it shouldn't miss any scenario for your polygons, but it's not the optimal solution.

"Edge" case remarks

• PointInsidePolygon(..) must return true if the point is on the border of the polygon (either lies on an edge or is a vertex)

• EdgesIntersect(..) must return false if the innerEdge is a subset (geometrically-wise) of the outerEdge. In this case, the edges obviously intersect, but for the purpose of the algorithm, we need to indicate that the intersection is not breaking the semantics behind the isInside variable

General Remakrs:

• without edge vs edge intersection checks, as pointed out in the comments, the approach might return false positives for some concave polygons (e.g. a V shaped quad and a rectangle - the rectangle might have all of its vertices inside the V shape, but intersect it, thus having at least some areas outside).

• after one checks for at least one of the vertices of the inner polygon to be inside the outer one, and if there are no intersecting edges, it means the sought after condition is satisfied.

• This will return false positives when the outer polygon is concave. – sam hocevar Jun 13 '12 at 14:10
• Funny enough, while teodron's and knight666's are wrong individually, when combined, they should give a right answer. If all points of a polygon are inside another, and if their lines don't intersect, then the first poly is completely inside the other. – Hackworth Jun 13 '12 at 14:19
• True, it does return false positives, it needs to take into account edge intersections as well. – teodron Jun 13 '12 at 14:33
• This seems to be correct answer. I think don't needed to check the second loop condition. – user960567 Jun 14 '12 at 3:54
• This doesn't work for endpoint intersections or if the edges overlap. – Brandon Kohn Mar 10 '16 at 22:25

Try doing a line intersection with each red line. In pseudocode:

// loop over polygons
for (int i = 0; i < m_PolygonCount; i++)
{
bool contained = false;

for (int j = 0; j < m_Polygon[i].GetLineCount(); j++)
{
for (int k = 0; k < m_PolygonContainer.GetLineCount(); k++)
{
// if a line of the container polygon intersects with a line of the polygon
// we know it's not fully contained
if (m_PolygonContainer.GetLine(k).Intersects(m_Polygon[i].GetLine(j)))
{
contained = false;
break;
}
}

// it only takes one intersection to invalidate the polygon
if (!contained) { break; }
}

// here contained is true if the polygon is fully inside the container
// and false if it's not
}


However, as you can see, this solution will get slower as you add more polygons to check. A different solution could be:

• Render the container polygon to a pixel buffer with a white color.
• Render a child polygon to a different pixel buffer with a white color.
• Mask the container buffer over the polygon buffer with a XOR mask.
• Count the number of white pixels; if it's greater than 0 the child polygon is not fully contained by the container.

This solution is very fast, but it depends on your implementation (and what you want to do with the result of your check) what solution works best for you.

• Line intersections won't be enough to spot fully-contained polygons. – Kylotan Jun 13 '12 at 12:23
• Question: if the polygons are completely disjoint, no edges will intersect. Will it work in this case? The second, graphics based approach should work indeed! – teodron Jun 13 '12 at 12:36