¿Cómo determino si un polígono contiene completamente otro?

9

Tengo 2 polígonos Sé las coordenadas de vértice de ambos polígonos. ¿Cuál es la mejor manera de verificar si uno está completamente dentro del otro? Por ejemplo, el algoritmo solo debe reconocer el trapecio negro a continuación como contenido:

polígonos de ejemplo

usuario960567
fuente
No puedo dar una respuesta detallada en este momento (podría hacerlo más adelante), pero debería echar un vistazo a una implementación para el teorema del eje de separación para la detección de colisiones. El algoritmo puede modificarse ligeramente para verificar fácilmente lo que desea. Por ejemplo, codezealot.org/archives/55
TravisG
1
No tiene exactamente claro qué entiende de un polígono dentro de un polígono. ¿Qué pasa si todos los puntos del polígono más pequeño están en el más grande, pero cada uno de ellos tiene un lado en una línea, están en el otro? i47.tinypic.com/4i0sgg.jpg
speedyGonzales
@speedyGonzales, esto también se llama dentro.
user960567

Respuestas:

5

Hay toneladas de fragmentos de código fuente para un método que realiza una prueba de " punto dentro del polígono ". El principio proviene del teorema de la curva de Jordan para polígonos ( http://www-cgrl.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Octavian/compgeom.html ).

La forma ingenua sería: teniendo ese método, llámelo 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;

Teóricamente, no debería perderse ningún escenario para sus polígonos, pero no es la solución óptima.

Observaciones del caso "Edge"

  • PointInsidePolygon(..) debe devolver verdadero si el punto está en el borde del polígono (ya sea en un borde o es un vértice)

  • EdgesIntersect(..)debe devolver falso si el innerEdgees un subconjunto (geométricamente sabio) del outerEdge. En este caso, los bordes obviamente se cruzan, pero para el propósito del algoritmo, debemos indicar que la intersección no está rompiendo la semántica detrás de la isInsidevariable

Remakrs generales :

  • sin controles de intersección de borde frente a borde, como se señala en los comentarios, el enfoque podría devolver falsos positivos para algunos polígonos cóncavos (por ejemplo, un quad en forma de V y un rectángulo; el rectángulo podría tener todos sus vértices dentro de la forma de V, pero intersecarlo , teniendo así al menos algunas áreas afuera).

  • después de que uno verifique que al menos uno de los vértices del polígono interno esté dentro del externo, y si no hay bordes de intersección, significa que se cumple la condición buscada.

teodron
fuente
1
Esto devolverá falsos positivos cuando el polígono externo sea cóncavo.
sam hocevar
2
Curiosamente, mientras que los teodron y knight666 están equivocados individualmente, cuando se combinan, deberían dar una respuesta correcta. Si todos los puntos de un polígono están dentro de otro, y si sus líneas no se cruzan, entonces el primer poli está completamente dentro del otro.
Hackworth
Es cierto que devuelve falsos positivos, también debe tener en cuenta las intersecciones de los bordes.
teodron
Esta parece ser la respuesta correcta. Creo que no es necesario verificar la condición del segundo bucle.
user960567
Esto no funciona para las intersecciones de punto final o si los bordes se superponen.
Brandon Kohn
2

Intenta hacer una intersección de línea con cada línea roja. En pseudocódigo:

// 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
}

Sin embargo, como puede ver, esta solución será más lenta a medida que agregue más polígonos para verificar. Una solución diferente podría ser:

  • Representa el polígono contenedor en un búfer de píxeles con un color blanco.
  • Representa un polígono secundario en un búfer de píxeles diferente con un color blanco.
  • Enmascare el búfer del contenedor sobre el búfer del polígono con una máscara XOR.
  • Cuenta la cantidad de píxeles blancos; si es mayor que 0, el polígono hijo no está completamente contenido por el contenedor.

Esta solución es muy rápida, pero depende de su implementación (y de lo que quiera hacer con el resultado de su verificación) qué solución funciona mejor para usted.

caballero666
fuente
1
Las intersecciones de línea no serán suficientes para detectar polígonos completamente contenidos.
Kylotan
1
Pregunta: si los polígonos son completamente disjuntos, no se cruzarán bordes. ¿Funcionará en este caso? ¡El segundo enfoque basado en gráficos debería funcionar!
teodron