Pengujian apakah tetrahedron terletak di dalam Polyhedron

15

Saya memiliki tetrahedron dan polyhedron . dibatasi sedemikian rupa sehingga selalu berbagi semua simpulnya dengan . Saya ingin menentukan apakah terletak di dalam .t ptpt p

Saya ingin menambahkan satu detail untuk masalah jika itu dapat berkontribusi pada solusi: t adalah tetrahedron Delaunay dan wajah p adalah segitiga dan sangat Delaunay keduanya sehubungan dengan simpul p . Tetrahedron adalah Delaunay jika sirkus bulunya tidak mengandung simpul lain di dalamnya. Sebuah wajah sangat Delaunay jika ada circumsphere yang mengandung simpul wajah itu di permukaannya tetapi tidak ada simpul lain di atau di dalamnya.

Gambar berikut menunjukkan masalah yang sama dalam ruang 2D :

Poligon p :

masukkan deskripsi gambar di sini

Delaunay triangulasi simpul p :

masukkan deskripsi gambar di sini

Hasil tes dalam / luar di atas segitiga t (Segitiga teduh di dalam dan sisanya di luar ):p

masukkan deskripsi gambar di sini

Hasil yang diinginkan (memangkas segitiga luar ) :

masukkan deskripsi gambar di sini


Masalah asli saya adalah dalam ruang 3D sehingga segitiga pada gambar di atas diterjemahkan menjadi tetrahedron dan poligon p diterjemahkan menjadi polyhedron p yang sewenang - wenang . Saya telah menemukan beberapa rumusan masalah ini:tpp

Formulasi 1
Satu-satunya bagian yang dapat berada di luar p adalah ujung-ujungnya dan muka segitiga tetapi secara umum mungkin ada p yang memiliki tepi semua t di luar pada permukaannya, sehingga sebagai alternatif, masalah ini juga dapat diformulasikan untuk menguji apakah untuk tetrahedron t ada wajah yang terletak di luar p ?tpp tt p

Formulasi 2
Saya memiliki perspektif lain yang mungkin terhadap masalah ini tetapi tidak memiliki ide formal:
Secara geometris, jika berada di luar maka ia akan selalu menempel pada permukaan luar hal . Jadi jika kita dapat menghitung kontur (secara informal, batas luar) C V dan C V p sehingga V = V tV p dan V t , V p adalah himpunan simpul dalam t , p masing-masing, kemudian CtpCVCVpV=VtVpVt,Vpt,p ifftterletak di dalamp. CV=CVp tp

Saya ingin tahu:

  • Bagaimana saya bisa menyelesaikan Formulasi 1 atau Formulasi 2 ?
  • Atau, adakah pendekatan yang sama sekali berbeda untuk menyelesaikan ini?

Pembaruan:
Saya sekarang menyadari bahwa masalah ini dapat dikurangi menjadi Point in polyhedron problem. Karena tetrahedron luar akan memiliki setidaknya satu wajah yang terletak di luar p , sehingga titik sembarang pada wajah itu (kecuali simpulnya, secara umum) akan selalu berada di luar p . Oleh karena itu, untuk setiap wajah t , saya perlu mengambil titik sembarang dan menguji apakah titik itu berada di luar hal .tp pt p

Dari titik dalam artikel poligon saya jadi tahu tentang algoritma pengecoran Ray dan algoritma bilangan Winding . Ray casting tidak stabil secara numerik untuk kasus-kasus di mana titik terletak pada permukaan . Tetapi kekokohan numerik dari algoritma Winding number belum dibahas di sana. p

Berdasarkan di atas, masalah inti saya sekarang tampaknya (tolong sarankan jika harus ditanyakan sebagai pertanyaan terpisah):
Apakah ada algoritma numerik yang kuat untuk titik dalam masalah poligon ?

Pranav
sumber
Hanya untuk memperjelas: 1) Dapatkah polyhedron menjadi non-cembung, dan 2) jika t dan p berbagi wajah atau tepi (atau bagian dari satu), apakah itu mendiskualifikasi t dari menjadi "bagian dalam" dari p ? (Jelas, berdasarkan kebutuhan Anda, t dan p harus diizinkan untuk berbagi simpul.)ptptptp
Ilmari Karonen
@IlmariKaronen 1) Ya 2). Tidak, sejauh yang dapat saya bayangkan, satu-satunya perbedaan antara tetrahedron di dalam dan di luar adalah bahwa wajah / tepi yang tidak dibagi akan terletak di luar jika berada di luar p dan di dalam jika t berada di dalam p (seperti yang telah saya sebutkan di bawah Formulasi 1 ). BTW, apa yang Anda maksud dengan "... atau bagian dari satu ..."? tptp
Pranav
1
Dua wajah coplanar atau tepi collinear mungkin tumpang tindih hanya sebagian. Ini bisa terjadi bahkan jika itu sendiri tidak memiliki wajah atau tepi yang bertepatan, selama ia memiliki lebih dari dua collinear atau lebih dari tiga simpul coplanar. p
Ilmari Karonen
1
non-convexity memiliki keanehan bahwa semua simpul dapat berada di dalam polyhedron dan tetrahedron dapat berada di luar (karena tepi tidak perlu berada di dalam secara keseluruhan). Algoritma yang memungkinkan, lihat apakah tepian (antara polyhedron dan tetrahedron) dapat memiliki persimpangan => prob bahwa tetrahedron terletak di luar sangat bagus
Nikos M.
1
Pernahkah Anda melihat algoritma jarak Gilbert – Johnson – Keerthi? Anda harus menguraikan poligon / polihedron menjadi bentuk cembung terlebih dahulu (seperti yang Anda catat, kompleks sederhana akan melakukan pekerjaan). GJK dikenal sangat stabil dan sangat cepat.
Nama samaran

Jawaban:

2

Saya baru-baru ini menemukan satu solusi untuk masalah ini dalam sebuah makalah 'Segmentasi yang kuat di dalam dan di luar menggunakan nomor belitan umum' oleh Alec Jacobson et.al., di sini . Ini memecahkan masalah penempatan jika suatu titik berada di dalam (atau di luar) yang sewenang-wenang (satu dengan persimpangan-sendiri, non-manifold, permukaan-terbuka, dll.) Jala poligonal menggunakan gagasan bilangan belitan umum .

Masalah dapat diselesaikan jika saya menghitung bilangan sentroid umum dari sentroid terhadap permukaan p .tp

Pranav
sumber
ptpptppttp