Hilfe gesucht: Punkt im Tetraeder

[Giacomo_S]

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]

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]

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.

 

[sillyLilly]

Naja ... ich muss ja nicht alles verstehen 8)

 

[Misterbluedevil]

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]

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]

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 ?

 

[Giacomo_S]

Naja ... ich muss ja nicht alles verstehen 8)

Eben.
Jede / r hat auch seine / ihre Themen.

 

[cadaei]

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.

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.

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 ≥)

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.