Bagaimana cara menentukan apakah satu poligon sepenuhnya mengandung poligon lain?

Saya punya 2 poligon. Saya tahu koordinat titik kedua poligon. Apa cara terbaik untuk memeriksa apakah ada yang benar-benar di dalam yang lain? Misalnya, algoritme seharusnya hanya mengenali trapesium hitam di bawah ini sebagai yang terkandung:

Ada ton cuplikan sumber untuk metode yang melakukan tes untuk " titik di dalam poligon ". Prinsipnya berasal dari teorema kurva Jordan untuk poligon ( http://www-cgrl.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Octavian/compgeom.html ).

Cara naif adalah: memiliki metode itu, sebut saja 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;

Secara teoritis, seharusnya tidak melewatkan skenario apa pun untuk poligon Anda, tetapi itu bukan solusi optimal.

Keterangan kasus "Tepi"

• PointInsidePolygon(..) harus mengembalikan true jika titik berada di perbatasan poligon (baik terletak di tepi atau merupakan titik)

• EdgesIntersect(..)harus mengembalikan false jika innerEdgesubset (bijaksana secara geometris) dari outerEdge. Dalam hal ini, tepinya jelas berpotongan, tetapi untuk tujuan algoritma, kita perlu menunjukkan bahwa persimpangan tidak melanggar semantik di belakang isInsidevariabel

Remakr Umum :

• tanpa pemeriksaan tepi vs tepi, seperti yang ditunjukkan dalam komentar, pendekatan tersebut mungkin mengembalikan positif palsu untuk beberapa poligon cekung (misalnya quad berbentuk V dan persegi panjang - persegi panjang mungkin memiliki semua simpulnya di dalam bentuk V, tetapi memotongnya , sehingga memiliki setidaknya beberapa area di luar).

• setelah satu memeriksa setidaknya satu dari simpul poligon dalam berada di dalam yang luar, dan jika tidak ada tepi berpotongan, itu berarti kondisi yang dicari terpenuhi.

Coba lakukan persimpangan garis dengan setiap garis merah. Dalam 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
}

Namun, seperti yang Anda lihat, solusi ini akan lebih lambat saat Anda menambahkan lebih banyak poligon untuk diperiksa. Solusi yang berbeda dapat berupa:

• Render poligon wadah ke penyangga piksel dengan warna putih.
• Render poligon anak ke buffer piksel yang berbeda dengan warna putih.
• Tutup penyangga wadah di atas penyangga poligon dengan masker XOR.
• Hitung jumlah piksel putih; jika lebih besar dari 0 poligon anak tidak sepenuhnya terkandung oleh wadah.

Solusi ini sangat cepat, tetapi tergantung pada implementasi Anda (dan apa yang ingin Anda lakukan dengan hasil pemeriksaan Anda) solusi apa yang paling cocok untuk Anda.