Bagaimana cara menentukan apakah satu poligon sepenuhnya mengandung poligon lain?

9

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:

contoh poligon

pengguna960567
sumber
Saya tidak dapat memberikan jawaban terperinci sekarang (mungkin melakukannya nanti), tetapi Anda harus melihat implementasi untuk teorema sumbu pemisah untuk deteksi tabrakan. Algoritme dapat sedikit dimodifikasi untuk dengan mudah memeriksa apa yang Anda inginkan. misalnya codezealot.org/archives/55
TravisG
1
Anda tidak begitu jelas apa yang Anda pahami tentang poligon di dalam poligon. Bagaimana jika semua titik poligon yang lebih kecil berada di yang lebih besar, tetapi masing-masing memiliki sisi pada satu baris, apakah mereka berada di satu sama lain? i47.tinypic.com/4i0sgg.jpg
speedyGonzales
@ speedyGonzales, ini juga disebut di dalam.
user960567

Jawaban:

5

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.

teko teh
sumber
1
Ini akan mengembalikan positif palsu ketika poligon luar cekung.
sam hocevar
2
Cukup lucu, sementara teodron dan knight666 salah secara individual, ketika digabungkan, mereka harus memberikan jawaban yang benar. Jika semua titik poligon berada di dalam yang lain, dan jika garis-garisnya tidak berpotongan, maka poli pertama benar-benar di dalam yang lain.
Hackworth
Benar, ia mengembalikan false positive, perlu memperhitungkan persimpangan tepi akun juga.
teodron
Ini sepertinya jawaban yang benar. Saya pikir tidak perlu memeriksa kondisi loop kedua.
user960567
Ini tidak berfungsi untuk persimpangan titik akhir atau jika tepinya tumpang tindih.
Brandon Kohn
2

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.

knight666
sumber
1
Persimpangan garis tidak akan cukup untuk melihat poligon yang berisi penuh.
Kylotan
1
Pertanyaan: jika poligon benar-benar terpisah, tidak ada ujung yang akan bersilangan. Apakah akan berhasil dalam kasus ini? Yang kedua, pendekatan berbasis grafis memang harus bekerja!
teodron