Jak ustalić, czy jeden wielokąt całkowicie zawiera inny?

Mam 2 wielokąty. Znam współrzędne wierzchołków obu wielokątów. Jaki jest najlepszy sposób, aby sprawdzić, czy jedno jest całkowicie wewnątrz drugiego? Na przykład algorytm powinien rozpoznać tylko czarny trapez poniżej jako zawarty:

Istnieje mnóstwo fragmentów kodu źródłowego dla metody, która wykonuje test „ punktu wewnątrz wielokąta ”. Zasada ta pochodzi z twierdzenia Jordana o wielobokach ( http://www-cgrl.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Octavian/compgeom.html ).

Naiwnym sposobem byłoby: mając tę ​​metodę, nazwij ją 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;

Teoretycznie nie powinno zabraknąć żadnego scenariusza dla twoich wielokątów, ale nie jest to optymalne rozwiązanie.

Uwagi „Edge”

• PointInsidePolygon(..) musi zwracać wartość true, jeśli punkt znajduje się na granicy wielokąta (albo leży na krawędzi, albo jest wierzchołkiem)

• EdgesIntersect(..)musi zwrócić false, jeśli innerEdgejest podzbiorem (geometrycznie) z outerEdge. W tym przypadku krawędzie oczywiście przecinają się, ale dla celów algorytmu musimy wskazać, że przecięcie nie łamie semantyki za isInsidezmienną

Ogólne Remakrs :

• bez sprawdzania przecięcia krawędzi względem krawędzi, jak wskazano w komentarzach, podejście może zwrócić fałszywie dodatnie wyniki dla niektórych wklęsłych wielokątów (np. kwadratu w kształcie litery V i prostokąta - prostokąt może mieć wszystkie wierzchołki wewnątrz kształtu V, ale przeciąć go , mając w ten sposób przynajmniej niektóre obszary na zewnątrz).

• po sprawdzeniu, czy przynajmniej jeden z wierzchołków wielokąta wewnętrznego znajduje się wewnątrz zewnętrznego, a jeśli nie ma przecinających się krawędzi, oznacza to, że poszukiwany warunek jest spełniony.

Spróbuj wykonać przecięcie linii z każdą czerwoną linią. W pseudokodzie:

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

Jednak, jak widać, to rozwiązanie będzie działać wolniej, gdy dodasz więcej wielokątów do sprawdzenia. Innym rozwiązaniem może być:

• Renderuj wielokąt pojemnika do bufora pikseli z białym kolorem.
• Renderuj wielokąt potomny do innego bufora pikseli z białym kolorem.
• Zamaskuj bufor kontenera nad buforem wielokąta za pomocą maski XOR.
• Policz liczbę białych pikseli; jeśli jest większy niż 0, wielokąt potomny nie jest w pełni zawarty w kontenerze.

To rozwiązanie jest bardzo szybkie, ale zależy od Twojej implementacji (i tego, co chcesz zrobić z wynikiem sprawdzenia), które rozwiązanie będzie dla Ciebie najlepsze.