Wie bestimme ich, ob ein Polygon ein anderes vollständig enthält?

Ich habe 2 Polygone. Ich kenne die Scheitelpunktkoordinaten beider Polygone. Was ist der beste Weg, um zu überprüfen, ob sich einer vollständig im anderen befindet? Zum Beispiel sollte der Algorithmus nur das schwarze Trapez unten als enthalten erkennen:

Es gibt Unmengen von Quellausschnitten für eine Methode, die einen Test für " Punkt innerhalb des Polygons " durchführt. Das Prinzip stammt aus dem jordanischen Kurvensatz für Polygone ( http://www-cgrl.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Octavian/compgeom.html ).

Der naive Weg wäre: Wenn Sie diese Methode haben, nennen Sie sie 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;

Theoretisch sollte kein Szenario für Ihre Polygone fehlen, aber es ist nicht die optimale Lösung.

Bemerkungen zum Fall "Edge"

• PointInsidePolygon(..) muss true zurückgeben, wenn sich der Punkt am Rand des Polygons befindet (entweder auf einer Kante liegt oder ein Scheitelpunkt ist)

• EdgesIntersect(..)muss false zurückgeben, wenn das innerEdgeeine Teilmenge (geometrisch) der ist outerEdge. In diesem Fall schneiden sich die Kanten offensichtlich, aber für den Zweck des Algorithmus müssen wir angeben, dass der Schnittpunkt die Semantik hinter der isInsideVariablen nicht bricht

General Remakrs :

• Ohne Kanten-Kanten-Schnittpunktprüfungen, wie in den Kommentaren ausgeführt, kann der Ansatz für einige konkave Polygone (z. B. ein V-förmiges Quad und ein Rechteck) falsch positive Ergebnisse zurückgeben - das Rechteck hat möglicherweise alle seine Eckpunkte innerhalb der V-Form, schneidet sie jedoch , also zumindest einige Bereiche außerhalb).

• Nachdem überprüft wurde, ob mindestens einer der Eckpunkte des inneren Polygons innerhalb des äußeren liegt, und wenn sich keine Schnittkanten befinden, bedeutet dies, dass die gesuchte Bedingung erfüllt ist.

Versuchen Sie, mit jeder roten Linie einen Linienschnitt zu machen. Im 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
}

Wie Sie sehen, wird diese Lösung jedoch langsamer, wenn Sie weitere zu überprüfende Polygone hinzufügen. Eine andere Lösung könnte sein:

• Rendern Sie das Containerpolygon in einen Pixelpuffer mit weißer Farbe.
• Rendern Sie ein untergeordnetes Polygon in einen anderen Pixelpuffer mit weißer Farbe.
• Maskieren Sie den Containerpuffer mit einer XOR-Maske über dem Polygonpuffer.
• Zählen Sie die Anzahl der weißen Pixel. Wenn es größer als 0 ist, ist das untergeordnete Polygon nicht vollständig im Container enthalten.

Diese Lösung ist sehr schnell, hängt jedoch von Ihrer Implementierung ab (und davon, was Sie mit dem Ergebnis Ihrer Prüfung tun möchten), welche Lösung für Sie am besten geeignet ist.