Projektion Punkt auf Dreieck im R4(!)

07.09.2010, 05:59

thewer

Projektion Punkt auf Dreieck im R4(!)

Hallo,
ich habe ein kleines Problem, bei dem ich nicht weiter komme:

Ich habe Messpunkte im R4 (x,y,z und die Messdaten gleicher Einheit, also ein 3+1 dimensionaler oder 4dimensionaler Raum, wenn man 4D nicht als Zeit versteht).

Die Messdaten koennen (sorry, englisches Keyboard) linear verbunden werden, ich suche den geringsten Abstand von meinen Messdaten zu einem Vergleichspunkt P.

Dazu bilde ich aus 4 Messpunkten einen Simplex, berechne den Normalenvektor(4D) und projeziere den Punkt P in die Hyperebene, die der Simplex aufspannt, ergibt P'.

Dann berechne ich die baryzentrischen 4D-Koordinaten von P', um zu beurteilen, ob P' im Simplex oder ausserhalb liegt, wenn ausserhalb, ob der naechste Punkt des Simplex dazu ein Eckpunkt, eine Kante oder ein Dreieck ist.

Abstand Eckpunkt/Kante/Dreieck zu P ist dann der gesuchte Minimalabstand (=Fehler der Messung).

Eckpunkt/Kante sind kein Problem, aber wenn meine baryzentrischen Koordinaten aussagen, dass P' bzw. P am naechsten zu einem Dreieck im R4 liegen, versagen meine mathematische Faehigkeiten (bzw. die Vorstellungskraft im 4D Raum).

Im 3D Raum waere das einfach ein Kreuzprodukt zweier Dreiecksvektoren durch P, aber im 4D Raum steht ja eine ganze (2D) Ebene senkrecht darauf...

Was ich versucht habe:
GL-System des Dreiecks gleichsetzen mit einem 'Doppellot' (wahrscheinlich totaler Humbug, da auf meinen kruden Vorstellungen von 4D gewachsen) von P gleichsetzen (A+uBA+vCA = P+xN+yM). N ist dabe der Nomalvektor zum Simplex, M ein Vektor, der normal zu N, BA und CA ist.

Das GL-System liefert dann einen Punkt der leider nur in der Ebene liegt, die das Dreieck aufspannt, nicht im Dreieck selbst... (auf den ersten Blick sah der Punkt ganz gut aus...)

Kann mir jemand dabei helfen eine Loesung zu finden? Danke schon mal fuer jeden kleinen Tipp...

08.09.2010, 05:53

thewer

Auf diesen Beitrag antworten »

Hallo,

hab noch mal drueber deschlafen und bin mir jetzt sicher, dass die Gleichung
A+uBA+vCA = P+xN+yM richtig ist -

Was mich jedoch wundert ist, dass die Projektion von P auf das Dreieck ABC nicht im Dreieck liegt, obwohl die baryzentrischen Koordinaten fuer meinen Simplex aussagen, dass das Dreieck ABC der naechste Punkt ist...
Heisst das, dass die baryzentrischen Koordinaten im R4 mir nur aussagen, welche 2D-Ebene am naechsten liegt (die durch das Dreieck beschrieben wird)?
Dann haette ich bei den baryzentrischen Koordinaten was nicht verstanden.

Konkrete Zahlen:
P 4.0 0.0 2.0 2.0
A 0.0 0.0 2.0 1.0
B 0.0 4.0 2.0 3.0
C 4.0 0.0 2.0 2.5
D 4.0 4.0 4.0 4.0

In dem Fall ist mein P' auf den Simplex A,B,C,D
P' 3.9 -0.2 2.1 2.3

Die baryzentrischen Vektoren waeren
AP -4.0 0.0 0.0 -1.0
BP -4.0 4.0 0.0 1.0
CP 0.0 0.0 0.0 0.5
DP 0.0 4.0 2.0 2.0

Eine Linearkombination dieser Vektoren soll P'P ergeben:
P'P -0.13 -0.17 0.09 0.34

was mit den Faktoren
r(i) 0.12 -0.09 0.92 0.04
passiert.

Diese sagen aus (???????), dass
das Dreieck ACD am naechsten an P' liegt.

Daher eine Projektion ueber die Normalvektoren (senkrecht zu ACD)
n1 -0.4 -0.5 0.3 1
n2 -0.38 0.95 -2.66 1
von P auf ACD

ergibt
P'' 3.85 -0.12 1.94 2.40

was (leicht) ausserhalb des Dreiecks liegt.

(Gerechnet wurde mit Excel, also mit mehr Kommastellen als angegeben)

Hat jemand eine Idee, wie ich meine baryzentrischen Koordinaten deuten muss / was ich falsch mache?

Bin mir uebrigens nicht sicher, ob ich im richtigen Unterforum bin -
heisst zwar geometrische Fragestellungen aus der Hochschulmathe koennen diskutiert werden, aber vielleicht waere Algebra besser gewesen?!

Danke nochmals, falls jemandem was einfaellt...

08.09.2010, 20:53

Leopold

Auf diesen Beitrag antworten »

Eine Kleinigkeit zur Grammatik vorweg: Es heißt "das" Simplex.

Auch im $\begin{eqnarray*} \mathbb{R}^4 \end{eqnarray*}$ gibt es ein Kreuzprodukt. Es ist für drei Vektoren erklärt und bestimmt einen Vektor, der auf diesen senkrecht steht und, sofern sie linear unabhängig sind, vom Nullvektor verschieden ist. Man kann es auch so sagen: Das Kreuzprodukt definiert einen Normalenvektor der von den drei Vektoren aufgespannten dreidimensionalen Hyperebene.
Zur Berechnung des Kreuzproduktes $\begin{eqnarray*} \vec{u} \times \vec{v} \times \vec{w} \end{eqnarray*}$ denkt man sich die Vektoren $\begin{eqnarray*} \vec{u}, \vec{v}, \vec{w} \end{eqnarray*}$ in Spaltenschreibweise und nimmt eine weitere Spalte $\begin{eqnarray*} \vec{e} \end{eqnarray*}$ mit den unbestimmten Koordinaten $\begin{eqnarray*} e_1,\ldots,e_4 \end{eqnarray*}$ hinzu. Dann berechnet man, die Entwicklung nach der ersten Spalte liegt nahe, die Determinante

$\begin{eqnarray*} \begin{vmatrix} \vec{e} & \vec{u} & \vec{v} & \vec{w} \end{vmatrix} = \sum_{i=1}^4 \alpha_i e_i \end{eqnarray*}$

Durch sie wird eine Linearform in $\begin{eqnarray*} e_1,\ldots,e_4 \end{eqnarray*}$ definiert. In dieser Linearform ersetzt man jetzt $\begin{eqnarray*} e_1,\ldots,e_4 \end{eqnarray*}$ durch die kanonischen Einheitsvektoren $\begin{eqnarray*} \vec{e}_1,\ldots,\vec{e}_4 \end{eqnarray*}$ und interpretiert die Multiplikation als skalare Multiplikation. Der Vektor, den man damit erhält, ist das Kreuzprodukt

$\begin{eqnarray*} \vec{u} \times \vec{v} \times \vec{w} = \sum_{i=1}^4 \alpha_i \vec{e}_i \end{eqnarray*}$

Einen Normalenvektor der Hyperebene $\begin{eqnarray*} H \end{eqnarray*}$ , in der $\begin{eqnarray*} A,B,C,D \end{eqnarray*}$ liegen, erhältst du also zum Beispiel durch

$\begin{eqnarray*} \vec{n} = \vec{u} \times \vec{v} \times \vec{w} \ \ \text{mit} \ \ \vec{u} = \overrightarrow{AB} \, , \ \vec{v} = \overrightarrow{AC} \, , \ \vec{w} = \overrightarrow{AD} \end{eqnarray*}$

oder ein von Null verschiedenes Vielfaches davon.

Was die Interpretation der baryzentrischen Koordinaten betrifft, so messen diese keine Abstände, sondern Verhältnisse von Abständen.
Es sei $\begin{eqnarray*} h_A \end{eqnarray*}$ (Höhe) der positiv gemessene Abstand des Punktes $\begin{eqnarray*} A \end{eqnarray*}$ von der gegenüberliegenden Ebene $\begin{eqnarray*} BCD \end{eqnarray*}$ und $\begin{eqnarray*} \delta_A \end{eqnarray*}$ der orientierte Abstand eines Punktes $\begin{eqnarray*} X \in H \end{eqnarray*}$ von der Ebene $\begin{eqnarray*} BCD \end{eqnarray*}$ (also positiv gemessen, wenn $\begin{eqnarray*} X \end{eqnarray*}$ und $\begin{eqnarray*} A \end{eqnarray*}$ im selben durch $\begin{eqnarray*} BCD \end{eqnarray*}$ bestimmten Halbraum von $\begin{eqnarray*} H \end{eqnarray*}$ liegen, und negativ gemessen, wenn sie in verschiedenen Halbräumen liegen, und natürlich $\begin{eqnarray*} 0 \end{eqnarray*}$ , wenn $\begin{eqnarray*} X \end{eqnarray*}$ in der Ebene $\begin{eqnarray*} BCD \end{eqnarray*}$ selbst liegt). Entsprechend werden $\begin{eqnarray*} h_B, h_C, h_D \end{eqnarray*}$ und $\begin{eqnarray*} \delta_B, \delta_C, \delta_D \end{eqnarray*}$ definiert.

Sind nun $\begin{eqnarray*} \xi_A,\xi_B,\xi_C,\xi_D \end{eqnarray*}$ die baryzentrischen Koordinaten des Punktes $\begin{eqnarray*} X \end{eqnarray*}$ , so gilt

$\begin{eqnarray*} \delta_A = \xi_A h_A \, , \ \delta_B = \xi_B h_B \, , \ \ \delta_C = \xi_C h_C \, , \ \ \delta_D = \xi_D h_D \end{eqnarray*}$

Ich kann im konkreten Fall deine gerundeten Zahlen bestätigen und habe mit einem CAS die exakten Werte ermittelt. Für $\begin{eqnarray*} P' \end{eqnarray*}$ finde ich die baryzentrischen Koordinaten

$\begin{eqnarray*} \xi_A = \frac{11}{93} \, , \ \ \xi_B = - \frac{8}{93} \, , \ \ \xi_C = \frac{86}{93} \, , \ \ \xi_D = \frac{4}{93} \end{eqnarray*}$

Die Höhen des Tetraeders sind

$\begin{eqnarray*} h_A = \frac{4}{437} \sqrt{40641} \, , \ \ h_B = \frac{4}{401} \sqrt{37293} \, , \ \ h_C = \frac{1}{26} \sqrt{2418} \, , \ \ h_D = \frac{2}{89} \sqrt{8277} \end{eqnarray*}$

Man kann etwa $\begin{eqnarray*} h_A \end{eqnarray*}$ berechnen, indem man die Gerade durch $\begin{eqnarray*} A \end{eqnarray*}$ , die auf der Ebene $\begin{eqnarray*} BCD \end{eqnarray*}$ senkrecht steht, mit der Ebene schneidet und den Abstand von $\begin{eqnarray*} A \end{eqnarray*}$ zum Lotfußpunkt ermittelt. Ein Richtungsvektor $\begin{eqnarray*} \vec{n}_A \end{eqnarray*}$ der Lotgeraden muß senkrecht auf $\begin{eqnarray*} \vec{r} = \overrightarrow{BC}, \vec{s} = \overrightarrow{BD} \end{eqnarray*}$ und auf dem Normalenvektor $\begin{eqnarray*} \vec{n} \end{eqnarray*}$ von $\begin{eqnarray*} H \end{eqnarray*}$ stehen (denn $\begin{eqnarray*} \vec{n} \end{eqnarray*}$ steht ja senkrecht auf allen Vektoren der Hyperebene $\begin{eqnarray*} H \end{eqnarray*}$ , also auch auf $\begin{eqnarray*} \vec{n}_A \end{eqnarray*}$ ). Wenn ich dich richtig verstanden habe, war das ja auch dein Ansatz. Man kann also

$\begin{eqnarray*} \vec{n}_A = \vec{r} \times \vec{s} \times \vec{n} \end{eqnarray*}$

oder ein von Null verschiedenes Vielfaches davon als Richtungsvektor der Lotgeraden nehmen.

09.09.2010, 08:48

thewer

Auf diesen Beitrag antworten »

Hallo,

Danke fuer die Antwort.
Das mit dem Simplex ist peinlich - die Uni liegt schon eine Weile zurueck und in unmittelbarer Naehe gibt's weit und breit keine Mathebuecher... Mein Wissen beruht also nur auf dem Internet (Wiki).

Bezueglich den barymetrischen Koordinaten -

ich bin mir inzwischen (siehe 2. Post) sicher, dass die Berechnungen vom Prinzip her richtig sind, mein Problem ist, dass ich nicht den Abstand zu einer Ebene, sondern den Abstand zu einem Dreieck suche.

D.h. wenn das Lot vom Punkt P auf das Dreieck nicht im Dreieck selber liegt, bringt mir die Hoehe als Ergebnis nichts - daher die barymetrischen Koordinaten um das heraus zu finden.

Mein Problem: Ich habe im Raum verteilte Messpunkte und ich suche den Abstand zu einer Berechnung. Da zwischen den Messpunkten interpoliert werden kann und ich die geringste Abweichung suche, spanne ich ein Simplex auf (keine Extrapolation, ausserhalb des Simplex gelten andere Punkte), und ueberpruefe den Fusspunkt P' des Lotes mit den barymetrischen Koordinaten (Summe immer gleich 1, da P' ja in der Hyperebene des Simplex, aber teilweise negative Koordinaten).

Ist nun eine Koordinate negativ, heisst das
- der Fusspunkt liegt nicht innerhalb des Simplex, meine Hoehe (Abstand P-Fusspkt) ist also nicht der gesuchte Abstand
- bei genau einer negativen Koordinate ist 'angeblich' das gegenueberliegende Dreieck am naechsten.

Daher projeziere ich P zunaechst in die 2D-Ebene des Dreiecks (P'').
Leider bin ich mir jetzt auch hier sicher, dass P'' nicht innerhalb das Dreiecks liegen muss, sondern (wenn die negative Koordinate gross genug und der Punkt nahe am Rand des Dreiecks liegt) nur in der davon aufgespannten 2D-Ebene.

Also muss ich auch das ueberpruefen (im 4D: Ein Eckpunkt das Simplex mit den drei anliegenden Geraden und dem Normalvektor n als Koordinatensystem, ueberprueft die Lage von P''). Hier kann es dann vorkommen, dass nur noch 2 Punkte am Naechsten liegen (positive Anteile der Richtungsvektoren).

Naechster Schritt, Hoehe von P auf die Gerade bestimmen (ueber Skalarprodukt/Dreieckswinkel), mit den Winkeln bestimmen, ob der Fusspukt zwischen den Punkten liegt...

Insgesamt also ein langwieriger Prozess, bei dem ich mich frage, ob's nicht einfacher geht und ob ich nicht schon aus den ersten baryzentrischen Koordinaten sehen koennte, was wirklich am naechsten liegt...

Fuer einen Tipp bin ich immer noch dankbar! smile

09.09.2010, 12:11

Leopold

Auf diesen Beitrag antworten »

Hier steht es doch, wie man den Abstand eines Punktes der Hyperebene von den Seiten des Tetraeders berechnet.

Zitat:

Original von Leopold
Was die Interpretation der baryzentrischen Koordinaten betrifft, so messen diese keine Abstände, sondern Verhältnisse von Abständen.
Es sei $\begin{eqnarray*} h_A \end{eqnarray*}$ (Höhe) der positiv gemessene Abstand des Punktes $\begin{eqnarray*} A \end{eqnarray*}$ von der gegenüberliegenden Ebene $\begin{eqnarray*} BCD \end{eqnarray*}$ und $\begin{eqnarray*} \delta_A \end{eqnarray*}$ der orientierte Abstand eines Punktes $\begin{eqnarray*} X \in H \end{eqnarray*}$ von der Ebene $\begin{eqnarray*} BCD \end{eqnarray*}$ (also positiv gemessen, wenn $\begin{eqnarray*} X \end{eqnarray*}$ und $\begin{eqnarray*} A \end{eqnarray*}$ im selben durch $\begin{eqnarray*} BCD \end{eqnarray*}$ bestimmten Halbraum von $\begin{eqnarray*} H \end{eqnarray*}$ liegen, und negativ gemessen, wenn sie in verschiedenen Halbräumen liegen, und natürlich $\begin{eqnarray*} 0 \end{eqnarray*}$ , wenn $\begin{eqnarray*} X \end{eqnarray*}$ in der Ebene $\begin{eqnarray*} BCD \end{eqnarray*}$ selbst liegt). Entsprechend werden $\begin{eqnarray*} h_B, h_C, h_D \end{eqnarray*}$ und $\begin{eqnarray*} \delta_B, \delta_C, \delta_D \end{eqnarray*}$ definiert.

Sind nun $\begin{eqnarray*} \xi_A,\xi_B,\xi_C,\xi_D \end{eqnarray*}$ die baryzentrischen Koordinaten des Punktes $\begin{eqnarray*} X \end{eqnarray*}$ , so gilt

$\begin{eqnarray*} \delta_A = \xi_A h_A \, , \ \delta_B = \xi_B h_B \, , \ \ \delta_C = \xi_C h_C \, , \ \ \delta_D = \xi_D h_D \end{eqnarray*}$

10.09.2010, 05:16

thewer

Auf diesen Beitrag antworten »

Hallo und Danke nochmal -

ich habe den Ansatz schon verstanden und mache es im Prinzip auch so.

Leider loest das mein Problem nicht - habe ich wohl nicht gut genug beschrieben.

ich suche ja den Abstand des Punktes P zum Simplex und nicht zur Hyperebene oder Ebenen, die der Simplex bzw. Teile davon aufspannen.

Der beschriebene Ansatz liefert den Abstand (des Punktes P') zu den 2D-Ebenen die von den 4 Dreiecken des Simplex aufgespannt werden, nicht jedoch den Abstand zu den Dreiecken selbst.

Die Definition von Abstand ist hier der "zu P am naechsten liegende Punkt des Simplex". Liegt also der Fusspunkt des Lotes von P auf das Simplex im Simplex, ist es der Fusspunkt selbst. Ansonsten sollte aus der Lage des Fusspunktes P' hervor gehen, ob eine Kante oder Ecke des Simplex der naechste Punkt ist.

In meinem konkreten Beispiel liegt der naechste Punkt auf der Strecke AC, d.h. auf dem Lot von P auf AC (d=0.468).

Um heraus zu finden, ob P' im Simplex liegt, brauche ich die baryzentrischen Koordinaten - P' ist dabei fuer $\begin{eqnarray*} \xi_B \end{eqnarray*}$ negativ, was aussagen sollte, dass die 2D-Ebene, die durch ACD aufgespannt wird, am naechsten liegt (Ebene ABC ist naeher, aber P' im falschen Halbraum?!). Nun beginnt der beschriebene iterative Prozess - Lot von P auf ACD, ueberpruefen, ob der neue Fusspunkt im Dreieck liegt (neue baryz.Koord.) - nein, AC am naechsten, Lot von P auf AC...

Daher die Frage, ob es nicht einfacher geht und ob ich aus den baryzentrischen Koordinaten von P' nicht gleich den naechsten Punkt konstruieren kann, bzw. ersehen, dass eine Gerade und nicht ein Dreieck am naechsten liegt (vielleicht mit Hilfe der orientierten Hoehen?!).

Danke nochmal fuer die Hilfe.

Neue Frage »

Antworten »

Projektion Punkt auf Dreieck im R4(!)

Verwandte Themen