How do I determine if one polygon completely contains another?

Question

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:

Answer 1

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 = false;
  for each (Point p in innerPoly)
  {
    if (PointInsidePolygon(p, outerPoly))
    {
      isInside = true; // at least one point of the innerPoly is inside 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.

LATER EDIT: 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).

UPDATE: 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.

Answer 2

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.