Schnittpunkt zwischen zwei konkaven Polygone in vorgegebener Richtung

Input: Zwei 3D konkave Polygone A und B , Einheitsvektor d. Keine Polygone schneiden sich zum Zeitpunkt t = 0. Es wird erwartet, dass die Richtung d sich nicht sehr oft ändert, daher ist eine Vorverarbeitungsphase erforderlich.Schnittpunkt zwischen zwei konkaven Polygone in vorgegebener Richtung

Problem: fest, ob zwei konkave Polygone A und B können in Richtung d, zu einem bestimmten Zeitpunkt t schnitten werden. Mit anderen Worten: Wenn wir ein Polygon in die gegebene Richtung d bewegen, würde es ein anderes Polygon schneiden?

Ausgabe: 1 - Schnittpunkt existiert, 0 - otheswise.

Quelle

2012-03-28 innochenti

Zuerst sollten Sie die Ebene finden, die senkrecht zum Vektor ist d.

Plane

Für beide 3D-Polygone Sie Projektion auf dieser Ebene berechnen soll. Wenn sich dann die Projektionen überlappen, werden sich die 3D-Polygone zu einem bestimmten Zeitpunkt t schneiden.

Jetzt haben Sie ein einfacheres Problem: Überprüfen, ob zwei 2d nicht-konvexe Polygone schneiden. Sie können es tun, indem Sie einfach über jedes Kantenpaar iterieren und prüfen, ob sie sich schneiden.

Quelle

2012-03-28 08:53:43

soweit ich verstehe, gilt es nur für konvexe Polygone. siehe SAT-Satz. korrigiere mich wenn ich falsch liege. – innochenti

In meiner Lösung gehe ich nie davon aus, dass es eine Trennachse gibt. Ich denke, dass meine Lösung für nicht konvexe 3D-Polygone funktionieren wird. –

Schnittpunkt zwischen zwei konkaven Polygone in vorgegebener Richtung

Antwort

Verwandte Themen