Pengujian apakah tetrahedron terletak di dalam Polyhedron

Saya memiliki tetrahedron dan polyhedron . dibatasi sedemikian rupa sehingga selalu berbagi semua simpulnya dengan . Saya ingin menentukan apakah terletak di dalam .$t$ $p$$t$$p$$t$ $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$ :

Delaunay triangulasi simpul $p$ :

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

Hasil yang diinginkan (memangkas segitiga luar ) :

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:$t$$p$$p$

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 ?$t$$p$$p$ $t$$t$ $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 t ∪ V p dan V t , V p adalah himpunan simpul dalam t , p masing-masing, kemudian $t$$p$$C_{V}$$C_{V_{p}}$$V=V_{t}\cup V_{p}$$V_t,V_p$$t,p$ ifftterletak di dalamp. $C_{V}=C_{V_p}$ $t$$p$

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 .$t$$p$ $p$$t$ $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 ?

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 .$t$$p$