Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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:

example polygons

share|improve this question
    
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
1  
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
add comment

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
1  
This will return false positives when the outer polygon is concave. –  Sam Hocevar Jun 13 '12 at 14:10
2  
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
add comment

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.

share|improve this answer
1  
Line intersections won't be enough to spot fully-contained polygons. –  Kylotan Jun 13 '12 at 12:23
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.