Finden Sie alle Punkte mit ganzzahligen Koordinaten im Tetraeder

Question

Ich versuche, alle Punkte mit ganzzahligen Koordinaten zu finden, die innerhalb eines Tetraeders liegen (ich möchte irgendwie in der Lage sein, sie zu durchlaufen). Ich kenne die Koordinaten der vier Punkte (A, B, C, D), die das Tetraeder definieren.

Was ich gerade mache ist, finde ich die Bounding Box des Tetraeders (minimale und maximale x, y, z Koordinaten von A, B, C, D) und dann eine Schleife durch alle Punkte innerhalb der Begrenzungsbox. Für jeden solchen Punkt berechne ich die baryzentrischen Koordinaten (unter Verwendung von the equations from Wikipedia) und überprüfe, ob der Punkt innerhalb des Tetraeders liegt (falls eine der baryzentrischen Koordinaten negativ oder größer als 1 ist, liegt der Punkt nicht innerhalb).

Gibt es einen besseren Weg, dies zu tun? Momentan liegt die Chance bei 1/6, dass der Punkt, den ich gerade teste (aus der Bounding Box), wirklich im Tetraeder liegt, also denke ich, dass ich zu viele unnötige Berechnungen mache.

Ich arbeite mit einer Liste von Tetraedern, die ich erzeugt habe, indem ich ein größeres Volumen triangulierte (ich erweitere das Volumen und möchte die fehlenden Werte mit Hilfe der Tetraederinterpolation interpolieren). Ich verwende keine externen Bibliotheken.

Answer 1

Eine weitere Idee zur Verbesserung:

Prüfen, ob ein "rod" parrallel zur z-Achse (das heißt x = 4, y = 6), um das Tetraeders verläuft. Wenn nicht, können keine Werte mit (x = 4, y = 5, z) drin sein.

Finden Sie stattdessen, wo der Stab die Kante des Tetraeders schneidet (indem Sie herausfinden, wo die Ebenen, die die Kante des Tetraeders bilden, ihn schneiden).

Angenommen, diese Ebenen schneiden sich bei z = 1,3 und z = 10,04. Dann weißt du, dass alle Punkte (4,5, 2) bis (4,5,10) innen sind.

Wiederholen Sie für alle Werte von x und y.

Dies sollte in der Praxis schneller sein, weil es Ihnen 1 Schleife spart.

Answer 2

Ihr Ansatz ist der richtige. Es gibt einige mögliche Optimierungen, die sich je nach Bedarf lohnen oder nicht. Zum Beispiel:

Es gibt eine einfachere Möglichkeit zu überprüfen, ob ein bestimmter Punkt innerhalb oder außerhalb des Tetraeders liegt. Es wird geprüft, zu welchem ​​Halbraum der Punkt bezüglich jeder der 4 Seiten des Tetraeders gehört:

Jede Seite wird durch 3 Punkte definiert (sagen wir A, B, C). Dann ist eine Ebenennormale ein (C-A) x (B-A) (das ist ein Kreuzprodukt von Vektoren in der Ebene). Wenn diese Koordinaten (a, b, c) sind, dann ist die Ebenengleichung F(x,y,z) = ax+by+cz = 0. Für einen gegebenen Punkt (x0, y0, z0) bestimmt das Vorzeichen von F (x0, y0, z0), zu welcher Halbebene die Punkte gehören.

Der Punkt ist, dass Sie für jede Seite des Tetraeders ebensogut Planquotierungen berechnen können wie für das Vorzeichen, das "außerhalb" entspricht und dann die Prüfung für einen bestimmten Punkt höchstens 4 Auswertungen (eine für jede Seite) ergibt), die jeweils 3 Multiplikationen und 2 Additionen nehmen.