Bagaimana cara saya menguji jika sebuah lingkaran dan cekung poligon berpotongan?

19

Saya memiliki poligon (kadang-kadang cembung, tetapi sering cekung), dan sekelompok lingkaran dengan jari-jari berbeda. Bagaimana saya bisa mengetahui jika lingkaran berpotongan / tumpang tindih dengan poligon?

Saya bisa membagi polong cekung saya menjadi potongan cembung. Apakah itu membantu?

collision-detection Adam Harte
sumber

Jawaban:

26

ada dua kasus masalah ini. Pertama adalah persimpangan dan kedua yang tumpang tindih (mengandung).

Pertama (persimpangan / poligon di dalam lingkaran):

Temukan titik terdekat di setiap tepi poligon ke pusat lingkaran. Jika jarak antara titik terdekat ke pusat kurang dari jari-jari, Anda mendapat persimpangan atau tumpang tindih.

Kedua (lingkaran adalah poligon utuh): Tembak sinar dari pusat lingkaran ke kanan (atau kiri / atas / bawah) dan hitung persimpangan ray / ruas (tepi poligon). Jika hitung simpang genap, lingkaran berada di luar poligon. Jika lingkaran aneh ada di dalam.

Saya akan membagikan foto dari ceramah untuk kasus ini:

masukkan deskripsi gambar di sini

Dan mengurus kasus-kasus tunggal.

Semoga ini bisa membantu.

sunting: Saya pikir adil untuk menambahkan kredit pada gambar. Penulis adalah Petr Felkel, Asisten Profesor di Universitas Teknik Ceko di Praha

Notabene
sumber
Saya tidak berpikir ini akan berhasil dengan hanya "menembak" sinar ke kanan. Mungkin saya salah membaca pendekatan Anda, tetapi dari apa yang saya pahami itu akan gagal dengan setup seperti yang digambarkan di sini: imgur.com/Whg2u
bummzack
2
Ya tapi ini dijelaskan dalam kasus pertama. Sinar pemotretan hanya akan menyelesaikan lingkaran yang mengandung Poligon (huruf kedua dalam uraian saya). Anda harus menguji kedua kasus. Cepat, mudah diimplementasikan, dan tidak memerlukan memori apa pun.
Notabene
1
Maaf saya bingung "edge" dengan "vertex" dan karena itu salah mengartikan cek pertama Anda. Saat membacanya dengan benar, ia bekerja :)
bummzack
7

Langkah pertama, seperti yang Anda duga, adalah untuk membagi poligon cekung menjadi beberapa yang cembung. Alasannya adalah Anda akan menggunakan teorema sumbu pemisah , yang hanya berfungsi pada poligon cembung.

SAT per se hanya bekerja pada dua poligon cembung. "Sumbu pemisah" pada namanya mengacu pada sumbu yang tegak lurus terhadap tepi poligon. Sayangnya, lingkaran memiliki jumlah yang tak terbatas. Namun, ternyata ada cara yang cukup mudah untuk mengetahui kapak mana yang relevan, dengan melihat ini yang memproyeksikan ke luar untuk memotong simpul poligon.

Daripada membahas seluruh algoritma di sini, Metanet Software (pembuat N / N +) memiliki tutorial yang baik tentang deteksi tabrakan menggunakan SAT , bagian ketiga yang mencakup SAT ketika salah satu objek adalah lingkaran .


sumber
Apakah Anda memiliki referensi untuk memisahkan poligon cekung menjadi poligon cembung? Tautan SAT yang Anda berikan tidak menyebutkan hal semacam itu.
ehsanul
Ini sebenarnya adalah masalah yang sangat kompleks tergantung pada geometri poligon, tetapi semua mesin 3D melakukan ini, karena perangkat keras umumnya hanya dapat membuat quads dan segitiga coplanar, bukan poligon.
SplinterReality
1
@ehsanul: en.wikipedia.org/wiki/Polygon_triangulation menjelaskan beberapa pendekatan populer.
0

Inilah yang saya lakukan.

  1. Gunakan tes garis horizontal untuk mendeteksi jika pusat lingkaran ada di dalam poligon. Jika ya, maka mereka berpotongan.
  2. Jika tidak, periksa kasus berikut. Untuk setiap sisi poligon
    1. Temukan kemiringan sisi poligon
    2. Hitung Kemiringan Lurus
    3. (BACA DENGAN HATI-HATI) Temukan titik potong antara garis dengan kemiringan sisi poligon yang bersinggungan dengan kedua simpul yang membentuk sisi, dan garis lereng yang tegak lurus dengan sisi yang memotong pusat lingkaran.
    4. Jika titik persimpangan yang ditetapkan terletak di dalam lingkaran, ini berarti lingkaran di beberapa titik melewati sisi yang dimaksud, dan karenanya memotong poligon
  3. Terakhir, jika tidak ada yang konklusif, periksa apakah ada simpul poligon terletak di dalam lingkaran (karena tes sebelumnya, Anda hanya perlu memeriksa sekali) Jika demikian, mereka berpotongan. Jika tidak, Anda dapat dengan yakin mengatakan bahwa mereka tidak melakukannya.
Chiraag Chakravarthy
sumber