Testowanie, czy czworościan leży w wielościanie

Mam czworościanu oraz graniastosłupa . jest tak ograniczony, że zawsze dzieli wszystkie swoje wierzchołki z . Chcę ustalić, czy leży wewnątrz .$t$ t p $p$$t$$p$$t$ $p$

Chciałbym dodać jeden szczegół do problemu, w przypadku gdy może on przyczynić się do rozwiązania: jest czworościanem Delaunaya, a ściany są trójkątne i silnie są Delaunay zarówno pod względem wierzchołków . Czworościan to Delaunay, jeśli otoczenie jego wierzchołków nie zawiera w sobie żadnego innego wierzchołka. Twarz jest silnie Delaunay jeśli istnieje circumsphere zawierającą wierzchołki tej twarzy na jej powierzchni, ale żaden inny wierzchołek na lub wewnątrz niego.$t$$p$$p$

Poniższe rysunki pokazują ten sam problem w przestrzeni : $2D$

Pierwotny wielokąt$p$ :

Delaunay triangulacja wierzchołków$p$ :

Wynik testu wewnątrz / na zewnątrz trójkątów$t$ (trójkąty zacieniowane znajdują się wewnątrz a reszta na zewnątrz ):$p$

Pożądany wynik (przycinanie poza trójkątami) :

Mój pierwotny problem dotyczy przestrzeni 3D, więc trójkąty na powyższych figurach tłumaczą się na czworościany, a wielokąt przekłada się na dowolny wielościan . Opracowałem kilka sformułowań tego problemu:$t$$p$$p$

Formulacja 1
Jedynymi częściami które mogą znajdować się na zewnątrz są jego krawędzie i trójkątne powierzchnie, ale ogólnie może istnieć które ma krawędzie wszystkich zewnętrznych na swojej powierzchni, więc alternatywnie, problem ten można również sformułować tak, aby sprawdzić, czy dla czworościanu istnieje twarz, która leży na zewnątrz ?p p t t $t$$p$$p$ $t$$t$ $p$

Formuła 2
Mam inną możliwą perspektywę na ten problem, ale brakuje mi formalnego pomysłu:
geometrycznie, jeśli jest na zewnątrz, to zawsze będzie przyczepiał się do zewnętrznej powierzchni . Jeśli więc możemy obliczyć kontury (nieformalnie, zewnętrzna granica) i taki sposób, że i są zestawami wierzchołków odpowiednio, a następnie iff leży wewnątrz . p C V C V p V = V t ∪ V p V t , V p t , p C V = C V p t $t$$p$$C_{V}$$C_{V_{p}}$$V=V_{t}\cup V_{p}$$V_t,V_p$$t,p$$C_{V}=C_{V_p}$ $t$$p$

Chciałbym wiedzieć:

• Jak mogę rozwiązać formułę 1 lub formułę 2 ?
• Czy jest jakieś inne podejście do rozwiązania tego problemu?

Aktualizacja:
Teraz zdaję sobie sprawę, że ten problem można sprowadzić do problemu Punkt w wielościanie . Ponieważ zewnętrzny czworościan będzie miał co najmniej jedną powierzchnię, która leży na zewnątrz , więc dowolny dowolny punkt na tej powierzchni (z wyjątkiem jej wierzchołków, ogólnie) zawsze będzie znajdować się na zewnątrz . Dlatego dla każdej powierzchni muszę wziąć dowolny punkt i sprawdzić, czy ten punkt leży poza .p p t $t$$p$ $p$$t$ $p$

Z punktu w artykule o wielokątach dowiedziałem się o algorytmie odlewania promieniami i algorytmie liczby uzwojenia . Odlewanie promieniowe nie jest stabilne numerycznie w przypadkach, w których punkt leży na powierzchni . Jednak nie rozwiązano w tym kwestii niezawodności numerycznej algorytmu liczby uzwojenia. $p$

Na podstawie powyższego wydaje się, że moim głównym problemem jest (proszę zasugerować, czy należy go zadać jako osobne pytanie):
Czy istnieje jakiś odporny numerycznie algorytm dotyczący problemu z punktem w wielokącie ?

Niedawno znalazłem jedno rozwiązanie tego problemu w artykule „Solidna segmentacja wewnętrzna i zewnętrzna za pomocą uogólnionych liczb uzwojenia” autorstwa Alec Jacobson i in., Tutaj . Rozwiązuje to problem lokalizacji, jeśli punkt znajduje się wewnątrz (lub na zewnątrz) dowolnej siatki wielokątnej (takiej z samo-przecięciem, bez rozmaitości, z otwartymi powierzchniami itp.) Przy użyciu uogólnionej liczby uzwojenia .

Problem można rozwiązać, jeśli obliczę uogólnioną liczbę uzwojenia środka ciężkości na powierzchni .$t$$p$