Hilfe gesucht: Punkt im Tetraeder

Giacomo_S

Ehrenmitglied
Registriert
13. August 2003
Beiträge
2.834
sorry Leute, aber vielleicht kann mir jemand da weiterhelfen, ich benötige einen Alghoritmus für ein Programm, an dem ich gerade schreibe.

Nehmen wir an, es gibt einen Tetraeder, der in einem 3-dimensionalen Koordinatensystem durch vier (beliebige) Punkte aufgespannt wird.
Die vier Punkte P1 bis P4 sind durch ihre Koordinaten x,y, und z definiert.

Desweiteren gibt es einen (beliebigen) Punkt PX, auch durch seine drei Koordinaten x,y, und z definiert, für den entschieden werden soll, ob er innerhalb oder außerhalb des von den drei Punkten P1,P2,P3 und P4 gebildeten Tetraeders liegt.

Wie müßte ein solches Entscheidungskriterium aussehen ?

Danke,
Giacomo.
 

Suleiman

Geselle
Registriert
13. Juni 2002
Beiträge
52
Konkretes habe ich nichts vorzuweisen, aber immerhin einen Ansatz :):

Schritt 1: Die Ebenen, die durch die Seitenflächen bestimmt werden, festlegen. Vier Stück.
Schritt 2: Ebene 1 liege "unten" am Tetraeder. Jetzt für den Punkt prüfen, ob er unter oder über der Ebene liegt. Liegt er drunter, ist der Algorithmus beendet - er liegt nicht im Tetraeder. Liegt er drüber, gehts weiter mit Schritt 3.
Schritt 3,4,5: Analog wie Schritt 2, nur mit den Ebenen 2, 3, und 4.
 

cadaei

Meister
Registriert
30. November 2002
Beiträge
251
Alle Möglichkeiten durchgehen, um mit 3 von den 4 Punkten eine Ebene zu erstellen, und prüfen, ob PX auf der gleichen Seite des 4. Punktes liegt oder nicht. Liegt er nicht auf der gleichen --> außerhalb. Erst wenn er von allen Ebenen auf der Seite des 4. Punktes liegt --> innerhalb.
 

Misterbluedevil

Neuling
Registriert
9. August 2002
Beiträge
3
Damit sich ein Punkt Px in dem Tetraeder (P1,P2,P3,P4) befindet muss folgendes erfüllt sein:
p1=Vektor zu P1
usw.

|p4-(Lotfußpunkt von px auf Ebene(durch die Punkte P1,P2,P3))|>|p4-px|
|p3-(Lotfußpunkt von px auf Ebene(durch die Punkte P1,P2,P4))|>|p3-px|
|p2-(Lotfußpunkt von px auf Ebene(durch die Punkte P1,P4,P3))|>|p2-px|
|p1-(Lotfußpunkt von px auf Ebene(durch die Punkte P4,P2,P3))|>|p1-px|

Die Fähigkeit zur Berechnung des Lotfußpunktes setze ich vorraus.

Gruß Misterbluedevil
 

Giacomo_S

Ehrenmitglied
Registriert
13. August 2003
Beiträge
2.834
Misterbluedevil schrieb:
Damit sich ein Punkt Px in dem Tetraeder (P1,P2,P3,P4) befindet muss folgendes erfüllt sein:
p1=Vektor zu P1
usw.

|p4-(Lotfußpunkt von px auf Ebene(durch die Punkte P1,P2,P3))|>|p4-px|
|p3-(Lotfußpunkt von px auf Ebene(durch die Punkte P1,P2,P4))|>|p3-px|
|p2-(Lotfußpunkt von px auf Ebene(durch die Punkte P1,P4,P3))|>|p2-px|
|p1-(Lotfußpunkt von px auf Ebene(durch die Punkte P4,P2,P3))|>|p1-px|

Die Fähigkeit zur Berechnung des Lotfußpunktes setze ich vorraus.

Gruß Misterbluedevil

Erst mal vielen Dank an alle.
Dieser Ansatz scheint mir der vielversprechendste zu sein.
Ich nehme an, der Lotfußpunkt, ist der Punkt, in dem sich die Höhe, die von einem Punkt ausgehend auf der gegenüberligenden Fläche senkrecht steht, schneidet.
Aber bis Du Dir sicher, oder ist das eine vermutete Lösung ?

Ich gebe folgendes zu bedenken: Befindet sich z.B. PX in unmittelbarer Nähe z.B. von Punkt P3 (aber innerhalb des Tetraeders) oder gar auf P3, dann ist doch |P1-PX| (=der Abstand von PX nach P1) in jedem Fall > |Lotfußpunkt 4,2,3| (=eine der 4 Höhen des Tetraeders) !
Oder liege ich da falsch ?
 

Giacomo_S

Ehrenmitglied
Registriert
13. August 2003
Beiträge
2.834
Suleiman schrieb:
Konkretes habe ich nichts vorzuweisen, aber immerhin einen Ansatz :):

Schritt 1: Die Ebenen, die durch die Seitenflächen bestimmt werden, festlegen. Vier Stück.
Schritt 2: Ebene 1 liege "unten" am Tetraeder. Jetzt für den Punkt prüfen, ob er unter oder über der Ebene liegt. Liegt er drunter, ist der Algorithmus beendet - er liegt nicht im Tetraeder. Liegt er drüber, gehts weiter mit Schritt 3.
Schritt 3,4,5: Analog wie Schritt 2, nur mit den Ebenen 2, 3, und 4.

Auch nicht schlecht. Aber was ist in einem dreidimensionalen System mit beliebig austauschbaren Dimensionen "unten" und was ist "oben" ?

Allerdings hat mich das auf eine Idee gebracht (noch nicht ausgereift).
Kann da nicht irgendetwas gehen, mit

Summe der Abstände Punkt PX-Tetraedermittelpunkt <= irgendetwas ?
 

cadaei

Meister
Registriert
30. November 2002
Beiträge
251
Giacomo_S schrieb:
Ich nehme an, der Lotfußpunkt, ist der Punkt, in dem sich die Höhe, die von einem Punkt ausgehend auf der gegenüberligenden Fläche senkrecht steht, schneidet.
ist korrekt.

Giacomo_S schrieb:
Aber bis Du Dir sicher, oder ist das eine vermutete Lösung ?
Die Lösung funktioniert, ich war nur zu faul, meine mathematischer auszudrücken, sie benutzt das gleiche Prinzip. Man könnte noch, wenn du definierst, dass sich ein Punkt auf einer Tetraederseite auch innerhalb befindet, aus den > jeweils ein ≥ machen. Wenn alle Bedingungen zutreffen, ist der Punkt im Tetraeder.

Giacomo_S schrieb:
Ich gebe folgendes zu bedenken: Befindet sich z.B. PX in unmittelbarer Nähe z.B. von Punkt P3 (aber innerhalb des Tetraeders) oder gar auf P3, dann ist doch |P1-PX| (=der Abstand von PX nach P1) in jedem Fall > |Lotfußpunkt 4,2,3| (=eine der 4 Höhen des Tetraeders) !
Oder liege ich da falsch ?

Der Lotfußpunkt ist immer von PX nicht von P1(!), also ist in diesem Fall |P1-PX| ≤ LPX auf P2,P3,P4
(in der Formel ist es andersrum, deshalb ≤ statt ≥)

Giacomo_S schrieb:
Allerdings hat mich das auf eine Idee gebracht (noch nicht ausgereift).
Kann da nicht irgendetwas gehen, mit

Summe der Abstände Punkt PX-Tetraedermittelpunkt <= irgendetwas ?

Das funktioniert leider nicht, denn dann gehst du von einer Kugel aus, also stimmt es nicht immer.
 

Ähnliche Beiträge

Oben