Testen, ob ein Tetraeder in einem Polyeder liegt

15

Ich habe ein Tetraeder und ein Polyeder p . t ist so eingeschränkt, dass es immer alle seine Eckpunkte mit p teilt . Ich möchte feststellen, ob t in p liegt .t ptpt p

Ich möchte dem Problem ein Detail hinzufügen, falls es zur Lösung beitragen könnte: ist ein Delaunay- Tetraeder und die Flächen von p sind dreieckig und sowohl in Bezug auf die Ecken von p stark delaunay . Ein Tetraeder ist Delaunay, wenn sich in der Umgebung seiner Scheitelpunkte kein anderer Scheitelpunkt befindet. Ein Gesicht ist stark verzögert, wenn es eine Umgebung gibt, die Scheitelpunkte dieses Gesichts auf seiner Oberfläche, aber keinen anderen Scheitelpunkt auf oder in ihm enthält.tpp

Folgende Zahlen zeigen das gleiche Problem in Raum: 2D

Das ursprüngliche Polygon p :

Bildbeschreibung hier eingeben

Delaunay-Triangulation von Eckpunkten von p :

Bildbeschreibung hier eingeben

Ergebnis des Innen- / Außentests über Dreiecken t (Schattierte Dreiecke sind innerhalb und Rest sind außerhalb ):p

Bildbeschreibung hier eingeben

Gewünschtes Ergebnis (Beschneiden außerhalb der Dreiecke) :

Bildbeschreibung hier eingeben


Mein ursprüngliches Problem liegt im 3D-Raum, also werden die Dreiecke in den obigen Abbildungen in Tetraeder und das Polygon p in ein beliebiges Polyeder p übersetzt . Ich habe einige Formulierungen dieses Problems herausgefunden:tpp

Formulierung 1
Die einzigen Teile von die außerhalb von p liegen können, sind seine Kanten und dreieckigen Flächen, aber im Allgemeinen kann es ein p geben, das Kanten aller außerhalb von ts auf seiner Oberfläche hat, so dass alternativ auch dieses Problem formuliert werden kann teste, ob für ein Tetraeder t eine Fläche existiert, die außerhalb von p liegt ?tpp tt p

Formulierung 2
Ich habe eine andere mögliche Perspektive in Bezug auf dieses Problem, aber es fehlt mir eine formale Idee:
Wenn geometrisch außerhalb liegt, bleibt es immer auf der äußeren Oberfläche von p haften . Wenn wir also die Konturen (informell die äußere Grenze) C V und C V p berechnen könnentpCVCVp , so dass und V t , V p sind Sätze von Scheitelpunkten in t , p bzw. dann CV=VtVpVt,Vpt,p wenntinnerhalb vonpliegt. CV=CVp tp

Ich würde gerne wissen:

  • Wie kann ich Formulierung 1 oder Formulierung 2 lösen ?
  • Oder gibt es einen völlig anderen Ansatz, um dies zu lösen?

Update:
Mir ist jetzt klar, dass dieses Problem auf das Punkt-in-Polyeder- Problem reduziert werden kann . Da ein außerhalb Tetraeders haben mindestens eine Seite , die außerhalb liegt , p , so dass jeder beliebige Punkt auf dieser Fläche ( mit Ausnahme seiner Ecken, im allgemeinen) liegen immer wird außerhalb p . Daher muss ich für jede Fläche von t einen beliebigen Punkt nehmen und prüfen, ob dieser Punkt außerhalb von p liegt .tp pt p

Aus einem Punkt in einem Polygonartikel lernte ich den Raycasting-Algorithmus und den Wicklungszahl-Algorithmus kennen . Ray Casting ist für Fälle, in denen der Punkt auf der Oberfläche von p liegt, numerisch nicht stabil . Die numerische Robustheit des Wicklungszahlalgorithmus wurde dort jedoch nicht angesprochen. p

Basierend auf dem oben Gesagten scheint mein Kernproblem nun zu sein (bitte schlagen Sie vor, ob es als separate Frage gestellt werden sollte):
Gibt es einen numerisch robusten Algorithmus für das Punkt-in-Polygon- Problem?

Pranav
quelle
Nur um zu verdeutlichen: 1) Kann das Polyeder nicht konvex sein, und 2) wenn t und p eine Fläche oder eine Kante (oder einen Teil von einer) teilen, disqualifiziert dies t davon, "innerhalb" von p zu sein ? (Natürlich, basierend auf Ihren Anforderungen, tptptpt und Scheitelpunkte gemeinsam haben dürfen.)p
Ilmari Karonen,
tptp
1
p
1
Nicht-Konvexität hat die Seltsamkeit, dass sich alle Eckpunkte innerhalb des Polyeders befinden können und dass sich das Tetraeder dennoch außerhalb befinden kann (da eine Kante nicht innerhalb als Ganzes liegen muss). Möglicher Algorithmus, ob Kanten (zwischen Polyeder und Tetraeder) Schnittpunkte haben können => wahrscheinlich, dass Tetraeder außerhalb liegt, ist großartig
Nikos M.
1
Haben Sie den Gilbert-Johnson-Keerthi-Entfernungsalgorithmus gesehen? Sie müssten zuerst das Polygon / Polyeder in konvexe Formen zerlegen (wie Sie bereits bemerkt haben, würde ein einfacher Komplex die Arbeit erledigen). GJK ist bekanntermaßen sehr stabil und sehr schnell.
Pseudonym

Antworten:

2

Ich habe kürzlich eine Lösung für dieses Problem in einem Artikel 'Robuste Innen-Außen-Segmentierung unter Verwendung verallgemeinerter Wicklungszahlen' von Alec Jacobson et al. Hier gefunden . Es löst das Problem des Lokalisierens, ob ein Punkt innerhalb (oder außerhalb) eines beliebigen (mit Selbstschnittpunkten, Nicht-Verteiler, offenen Flächen usw.) Polygonnetzes liegt, wobei der Begriff der verallgemeinerten Wicklungszahl verwendet wird .

Das Problem kann gelöst werden, wenn ich die verallgemeinerte Wicklungszahl des Schwerpunkts von berechne tp

Pranav
quelle
ptpptppttp