Schnittpunkte im Koordinatensystem

ness

Gleich vorn weg: ich geh in die Achte und hab mir all mein "Wissen" über "fortgeschrittenere" Themen in der Mathematik angelesen (wir sind grad bei linearen Funktionen ). In sofern kann es sein, dass mir Grundlagenwissen fehlt. Da wird mir dann die Wikipedia hoffentlich wieder helfen. (Nur falls ich komische Fragen stellen werde...)
Das Problem ist folgendes:
Ich habe ein koordinatensystem (x,y,z - 3 Dimensionen). Außerdem einen Strahl, der durch einen normalisierten Richtungsvektor sowie einen Ausgansgspunkt definiert ist, sowie ein Polygon, das durch x Punkte Beschrieben wird, die alle auf einer Ebene liegen.
Nun stelle ich mir zwei Fragen:
1.: wie bekomme ich raus, ob der Strahl durch das Polygon verläuft
2.: wie bekomme ich die Schnittpunktkoordinate heraus

Kyon

ich geh in die Achte und hab mir all mein "Wissen" über "fortgeschrittenere" Themen in der Mathematik angelesen

Sehr gut, weiter so!
Und, um Dich weiter an die Mathematik zu fesseln nur ein Hinweis. Dein Problem kannst Du mit Baryzentrischen Koordinaten lösen.

Gruß

ness

Ich hab mir das jetzt mal zusammengesucht:

#include <iostream>
int main()
{
	double Ax=0;
	double Ay=1;
	double Az=1;
	double Bx=2;
	double By=1;
	double Bz=1;
	double Cx=1;
	double Cy=3;
	double Cz=1;
	double Px=1;
	double Py=2;
	double Pz=1;
	double det=Ax*By*Cz+Cx*Ay*Bz+Bx*Cy*Az-Az*By*Cx-Ax*Cy*Bz-Bx*Ay*Cz;

	double a=(Px*By*Cz+Cx*Py*Bz+Bx*Cy*Pz-Pz*By*Cx-Px*Cy*Bz-Bx*Py*Cz)/det;
	double b=(Ax*Py*Cz+Cx*Ay*Pz+Px*Cy*Az-Az*Py*Cx-Ax*Cy*Pz-Px*Ay*Cz)/det;
	double c=(Ax*By*Pz+Px*Ay*Bz+Bx*Py*Az-Az*By*Px-Ax*Py*Bz-Bx*Ay*Pz)/det;

	std::cout<<"det="<<det<<std::endl<<"a="<<a<<std::endl<<"b="<<b<<std::endl<<"c="<<c<<std::endl<<"a+b+c="<<a+b+c;

	return 0;
};

Bei diesem konstruierten Beispiel kommt eins raus. -> P liegt also im Dreieck
Setzt man für Py 4 ein, kommt auch eins raus, aber a < 0 || b < 0 || c < 0 (|| c > 1 || b > 1 || a > 1) -> P liegt nicht im Dreieck.
Stimmt das jetzt erst mal so?
Wenn ja, hab ich die "low-level-berechnung".
Bleiben noch 2 Fragen: Soll ich besser jedes Polygon in Dreiecke aufteilen, oder mir zur Laufzeit die Formel für die Determinante berechnen?
Wie komm ich an P? Gibt es eine gescheitere Möglichkeit, als den Strahl in sehr keinen Abständen zu verfolgen (ich hoffe mal...)?

ness

*push*

borg

sagen wir:
$E: \vec{x} = \vec{a_1} + k \vec{v} + l \vec{w}, k, l \in \mathbb{R}$
und
$G: \vec{x} = \vec{a_2} + r \vec{u}, r \in \mathbb{R}$

ness schrieb:

1.: wie bekomme ich raus, ob der Strahl durch das Polygon verläuft

es gibt grundlegend erstmal 3 möglichkeiten der lagebeziehung zwischen einer ebene und einer geraden:

die gerade und die ebene schneiden sich,
genau dann wenn $\vec{u}, \vec{v}, \vec{w}$ linear unabhängig.

die gerade und die ebene sind echt parallel,
genau dann wenn $\vec{u}, \vec{v}, \vec{w}$ linear abhängig und $\vec{a\_2} - \vec{a\_1}, \vec{v}, \vec{w}$ linear unabhängig.

die gerade liegt in der ebene,
genau dann wenn $\vec{u}, \vec{v}, \vec{w}$ linear abhängig und $\vec{a\_2} - \vec{a\_1}, \vec{v}, \vec{w}$ linear abhängig.

ness schrieb:

2.: wie bekomme ich die Schnittpunktkoordinate heraus

wenn du herausgefunden hast das ebene und gerade sich schneiden,
musst du $\vec{a\_1} + k \vec{v} + l \vec{w} = \vec{a\_2} + r \vec{u}$ machen und die gleichung nach r auflösen. wenn du er hast liegt dein schnittpunkt bei $\vec{s} = \vec{a_2} + r \vec{u}$

edit: die dinger mit den pfeilen drüber sind vektoren, also einfach eine koordinate (x,y,z). lineare abhängigkeiten kannst du mithilfe von determinanten herausfinden, da scheinst du dich ja schon mit beschäftigt zu haben, wenn du da noch fragen zu hast, frag. die gleichung nach r auflösen tust du wohl am besten in dem du 3 gleichungssysteme draus machst und diese in einer matrix mit dem gaußverfahren auflöst (vielleicht gibts da verfahren die man mit dem computer besser beibringen kann, kA).

ness

Öhm, ja, was?

borg schrieb:

sagen wir:
$E: \vec{x} = \vec{a_1} + k \vec{v} + l \vec{w}, k, l \in \mathbb{R}$
und
$G: \vec{x} = \vec{a_2} + r \vec{u}, r \in \mathbb{R}$

Was ist hier was?

Das mit den linearen Abhängigkeiten krieg ich bestimmt hin, wenn ich mal länger google bemühe. Über das lösen von Gleichungssystemen denke ich sollte ich auch genug finden.
Aber warum ein System, ich seh hier nur eine lineare Gleichung. Oder sind da mehrere unbekannten? Halt warte, sind u,v,w vielleicht unbekannt? Deshalb 3 Gleichungssysteme? Aber wie finde ich dann heraus, ob die sich schneiden, wenn ich dafür u,v,w benötige?
Aber ich kapier das erst mal garnicht...
Und was ist mit den baryzentrischen Koordinaten? Auf welche Lösung hat Kyon angespielt? Das fand ich noch einfach...

borg

ness schrieb:

Und was ist mit den baryzentrischen Koordinaten? Auf welche Lösung hat Kyon angespielt? Das fand ich noch einfach...

kenn ich leider nicht. aber wenn das damit gut geht, benutz es! :p

ness schrieb:

Aber warum ein System, ich seh hier nur eine lineare Gleichung. Oder sind da mehrere unbekannten? Halt warte, sind u,v,w vielleicht unbekannt? Deshalb 3 Gleichungssysteme? Aber wie finde ich dann heraus, ob die sich schneiden, wenn ich dafür u,v,w benötige?

sagen wir a1=(2,1,-1), v=(1,-1,-1), w=(-3,1,4), a2=(3,0,1), u=(4,-1,2)

und wir müssen lösen:
a1 + k*v + l*w = a2 + ru
dann können wir daraus machen
k*v + l*w - ru = a2 - a1

in unserem fall also:
k*(1,-1,-1) + l*(-3,1,4) + r*(-4,1,-2) = (1,-1,2)

die 3 gleichungen sind
k -3l -4r = 1
-k +1 +r = -1
-k +4l -2r = 2

diese machen wir in eine matrix

k   l   r |
---------------
 1  -3  -4 |  2 
-1   1   1 | -1
-1   4  -2 |  2

das lösen wir auf nach

k   l   r |
---------------- 
 1   0   0 |  6/5   <-- k
 0   1   0 |  3/5   <-- l
 0   0   1 |  -2/5  <-- r

wir müssen also berechnen
s = (3,0,1) -2/5*(4,-1,2) = (7/5, 2/5, 1/5)

also S(7/5|2/5|1/5) <- schnittpunkt

sind bestimmt fehler in der rechnung, hab auch leider atm keine zeit für latex. aber so schwer ist es nicht, das kriegst du hin

scrub

vielleicht wärs als zwischenschritt mal gut, das LGS zu fuß zu lösen- ohne matrix.

Kyon

Setzt man für Py 4 ein, kommt auch eins raus,

Per Definition ist die Summe der Baryzentrischen Koordinaten (in Deinem Fall also a+b+c) eines Punktes immer 1; ist also richtig.

Stimmt das jetzt erst mal so?

Ja, sieht gut aus. Die Berechnung der Determinanten bin ich nicht im einzelnen durchgegangen, aber ich denke über 3x3 Determinanten brauchen wir uns hier nicht zu unterhalten...

Bleiben noch 2 Fragen: Soll ich besser jedes Polygon in Dreiecke aufteilen, oder mir zur Laufzeit die Formel für die Determinante berechnen?

Wie Du erkennst, ist der Test, ob ein Punkt in einem Polygon liegt, zur Lauftzeit nur durch die drei Vergleiche (a,b oder c < 0) möglich. Das ist natürlich sehr schnell und wenn Du die Triangulierung vorher machst, bleibt es zur Laufzeit auch schnell...
Zum zerlegen der Polygone in Dreiecke gibts einige Verfahren. Delaunay-Triangulierung kommt aber in jeder Computergrafik Vorlesung vor.

Wie komm ich an P? Gibt es eine gescheitere Möglichkeit, als den Strahl in sehr keinen Abständen zu verfolgen (ich hoffe mal...)?

Das ist die andere Sache. Um eine Schnittpunktberechnung, des Strahls mit der Ebene des Polygons, kommst Du nicht herum. (borg zeigt, wie es geht. E ist übrigens die Ebene, G die Gerade(klingt logisch); beide in Punkt-Richtungs-Form)
Damit kannst Du allerdings nur entscheiden, ob die Gerade(Strahl) durch die Ebene geht. Ob der Punkt dann auch in dem Polygon liegt, berechnest Du -schnell- mit den Baryzentrischen Koordinaten.

\\Edit
Da fällt mir noch ein: Wenn Du die Ebene in Normalenform hast, kannst Du Dir das Lösen eines Gleichungssystems sparen, dann reicht ein Skalarprodukt....

Gruß
Michael

ness

Ich glaube, so langsam kapier ich das...
Also k,l,r sind unbekannt, alles konzentriert sich darauf, diese zu finden.
Aber was ist:
$\vec{a\_1},\vec{v},\vec{w},\vec{a\_2},\vec{u}$
Die dürften ja alle gegeben sein, oder?

Kyon schrieb:

Da fällt mir noch ein: Wenn Du die Ebene in Normalenform hast, kannst Du Dir das Lösen eines Gleichungssystems sparen, dann reicht ein Skalarprodukt....

Das wäre gut, das sollte viel schneller sein. Was meinst du mit der Ebene in Normalenform? Ich weiß wie ich einen Vektor normalisiere, aber die Ebene wird ja dur 3 Vektoren (klar, also 2 davon normalisieren, oder?) und 2 Koeffizienten beschrieben.
/edit: so? http://de.wikipedia.org/wiki/Parameterdarstellung
/edit: normalenform? http://de.wikipedia.org/wiki/Normalgleichung
/edit: ja, ich habe mindestens einen Punkt in der Ebene und einen Normalenvektor...
/edit: ich glaub ich habs:
$Ebene: E\_1=\vec{a\_1}+l\vec{u}+k\vec{v}$
$E\_2=\vec{a\_1}+\vec{n}$
$E_1$ und $E_2$ sind das selbe, nur anders dargestellt (Ich komme an beides leicht ran.).
$Gerade: G=\vec{a_2}+m\vec{w}$
Nun überprüfe ich, ob u,v,w linear unabhängig sind, wie muss ich noch rausfinden...
Wenn das der Fall ist, kommt die 2. Definition der Ebene zum Zug:
\vec{a\_2}\*m\vec{w}=\vec{a\_1}\*\vec{n}
Aber wie lös ich das auf?

borg

ness schrieb:

Wenn das der Fall ist, kommt die 2. Definition der Ebene zum Zug:
$\vec{a\_2}+m\vec{w}=\vec{a\_1}+\vec{n}$
Aber wie lös ich das auf?

wenn du es auf diese form gebracht hast, bist du ja quasi fertig. du hast jetzt, wenn du so möchtest, 3 gleichungen mit je einer unbekannten. das ist durch einfaches umstellen zu lösen. wie du es mit der anderen form findest hab ich oben beschrieben, das sollte klar sein oder?

Kyon

Moment!
Da stimmt jetzt was nicht.

ness schrieb:

Ich glaube, so langsam kapier ich das...
Also k,l,r sind unbekannt, alles konzentriert sich darauf, diese zu finden.
Aber was ist:
$\vec{a\_1},\vec{v},\vec{w},\vec{a\_2},\vec{u}$
Die dürften ja alle gegeben sein, oder?

Nehmen wir mal als Beispiel die Gerade
$G: \vec{x}=\vec{a}+r\cdot\vec{u}$
Was soll diese Gleichung?
Du kannst mit ihr jeden Punkt $\vec{x}$ auf der Geraden G eindeutig darstellen, indem Du zu einem beliebigen (gegebenen) Punkt $\vec{a}$ der Geraden den Vector $\vec{u}$ hinzuaddierst. Mit dem Faktor $r\in \mathbb{R}$ kannst Du die Länge des Vektors u beliebig variieren, damit Du auch jeden Punkt der Geraden erreichen kannst. Der Punkt a nennt sich Aufpunkt, Startpunkt oder Ausgangspunkt(etc.) der Geraden. Der Vektor u ist der, wie Du ihn bezeichnest 'normalisierte Richtungsvektor'. D.h. alle Werte der Geraden sind gegeben, bis auf den Skalierungsfaktor u.

Was meinst du mit der Ebene in Normalenform? Ich weiß wie ich einen Vektor normalisiere, aber die Ebene wird ja dur 3 Vektoren (klar, also 2 davon normalisieren, oder?) und 2 Koeffizienten beschrieben.
-> http://de.wikipedia.org/wiki/Normalgleichung

Genau.

$Ebene: E\_1=\vec{a\_1}+l\vec{u}+k\vec{v}$
$E\_2=\vec{a\_1}+\vec{n}$

Nicht ganz..
Die Normalenform der Ebene lautet
$E: \vec{n}\circ (\vec{x}-\vec{a})=0$
$\circ$ ist das Skalarprodukt.
Mit dieser Gleichung kannst Du jeden beliebigen Punkt $\vec{x}$ in der Ebene darstellen. $\vec{x}-\vec{a}$ ist ein Vektor, der in der Ebene 'liegt'. Nach der Definition des Skalarproduktes muss die Gleichung oben 0 sein, da der Normalenvektor senkrecht auf der Ebene steht und damit auch auf jedem Vektor, der in der Ebene 'liegt'.
Für die Gerade gilt:
$G: \vec{x}=\vec{a_2}+m\vec{w}$

Nun überprüfe ich, ob u,v,w linear unabhängig sind, wie muss ich noch rausfinden...
Wenn das der Fall ist, kommt die 2. Definition der Ebene zum Zug:
$\vec{a\_2}+m\vec{w}=\vec{a\_1}+\vec{n}$
Aber wie lös ich das auf?

Ich schlage Dir mal 'nen anderen Weg vor. Versuche es mal so:
Du setzt die Geradengleichung in E ein, das ergibt
$\vec{n}\circ (\vec{a_2}+m\vec{w}-\vec{a})=0$
Damit hast Du nur eine Unbekannte und eine Gleichung, die Du nach m auflösen kannst. m setzt Du dann wieder in G ein und schon hast Du die Koordinaten des Schnittpunktes.
(Nebenbei, die Normalenform der Ebene kannst Du auch als $E: \vec{n}\circ \vec{x}-\vec{n}\circ\vec{a}=0$ schreiben, das erleichtert etwas das auflösen nach w)
Jetzt brauchst du nur noch 'nen Punkt der Ebene -> einer der Polygonpunkte, und eine Normale -> senkrechter Vektor auf eine beliebige Kante des Polygons (Stichwort:Skalarprodukt) und dann wars das.....

\\Edit: da fällt mir ein: 'Senkrechter Vektor auf eine Kante des Polygons' ist im $\mathbb{R}^3$ nicht eindeutig. Musst Du also 2 Kanten nehmen und Dir das Kreuzprodukt mal anschaun(z.B Wikipedia)...

So langsam machts mir auch wieder Spaß; die gute alte Lineare Algebra...

Gruß

ness

Kyon schrieb:

$\vec{n}\circ (\vec{a_2}+m\vec{w}-\vec{a})=0$

Ich mach mal weiter:
$\vec{n}\circ(\vec{a_2}+m\vec{w})-\vec{n}\circ\vec{a}=0$
$\vec{n}\circ(\vec{a_2}+m\vec{w})=\vec{n}\circ\vec{a}$
$\vec{n}\circ\vec{a_2}+\vec{n}\circ(m\vec{w})=\vec{n}\circ\vec{a}$
$\vec{n}\circ(m\vec{w})=\vec{n}\circ(\vec{a}-\vec{a_2})$
Ist das skalarprodukt überhaupt so komutativ? Und wenn ja, wie dann weiter?
Es gibt doch keine umkehroperation dazu?

Kyon

Du musst das Skalarprodukt erst auflösen.
Stell' Dir die Klammer als einen Vektor mit drei Komponenten vor.
Also
$(a_{21}+mw\_1-a\_1,a_{22}+mw\_2-a\_2,...)^T$

Dann kannst Du mit[1]
$\vec{a}\cdot\vec{b}=a\_1b\_1+a\_2b\_2+a\_3b\_3$
eine Gleichung machen, die du nach m auflösen kannst.
Darum auch die zweite Formel; ist dann wohl etwas einfacher...

Gruß

[1] http://de.wikipedia.org/wiki/Skalarprodukt

ness

Ja, ich glaube jetzt wirds grüen...
Ich rechne das mal durch, melde mich fals es Probleme gibt...
/edit: ich glaub, jetzt hab ichs wirklich:
$m=(n\_x a\_1\_x - n\_x a\_2\_x + n\_y a\_1\_y - n\_y a\_2\_y + n\_z a\_1\_z - n\_z a\_2\_z)/(n\_x w\_x + n\_y w\_y + n\_z w\_z)$
Kann das mal jemand durchsehen? Ich habs auch schon an nem minimalbeispiel durchgerechnet, hab auch schon ein beispiel probiert, dass sich nicht schneidet: beim divisor kam null raus. Das muss ja eigentlich der Fall sein, denn es die Gleichung *muss* ja dann unlösbar sein. Trotzdem kommt mir das wenig wasserdicht vor...
Sind meine Schlüsse richtig?
Ich rechne das heute nachmittag mal an einem etwas größerem Beispiel durch (pen+paper - ich bin in norwgen und hab keinen compiler zur hand), nicht das es nur zufällig funktioniert hat, weil so viele Werte mit 0 belegt waren...