Bestimmen ob Strecke "rechts" liegt

[Gast]

Ich habe insgesamt drei Strecken s1 (Punkt1=>Punkt2), s2(Punkt2=>Punkt3) und s3(Punkt2=>Punkt4), die sich alle im gemeinsamen Punkt2 treffen. Nun möchte ich bestimmen, ob s3 "rechts" liegt wenn man von Punkt1 über Punkt2 nach Punkt3 geht. Wie kann man das bestimmen? Ich hätte es mit Winkeln zwischen den Strecken versucht aber das funktioniert nicht wirklich...

[Nasenbaer]

Soll das in etwa so aussehen?


p3
/
/
/
p1----p2
\
\
\
\
p4

Dann schau doch einfach ob der Endpunkt einer Strecke rechts vom gemeinsamen Punkt liegt. Also hier ob p3 ne größere X-Koordinate hat als p2.

Hoffe das Problem richtig verstanden zu haben. :)

[pool1892]

"rechts" macht per se keinen sinn, du musst ein koordinatensystem angeben.
und dann kannste das koordinatensystem so umlegen, dass deine erste strecke genau auf einer koordinatenachse liegt, etwa im bild der vertikalen. wenn du nun schaust, ob der punkt 3 in den beiden quadranten liegt, in denen der x-wert positiv ist, so liegt der punkt 3 "rechts" von punkt 1.
so ein koordinatenwechsel lässt sich natürlich auch mit winkeln beschreiben und das dann direkt berechnen, aber das ist nicht wirklich einfacher.
es gibt noch soundsoviele andere möglichkeiten, etwa mit ein paar fallunterscheidungen. aber das scheint mir gerade der schnellste weg zu sein, um das in allgemeinen linearen räumen zu machen. für komplexere räume muss man dann weiter ausholen, aber ich denke mal nicht, dass du das benötigen wirst.
die techniken finden sich alle in LA-I büchern bzw. in oberstufenmaterial, je nachdem, was du bei der hand hast.

aber es kann auch sein, dass du zu wenig informationen über den raum hast, dann lässt sich so eine orientierung nicht definieren.
EDIT:
@nasenbaer: das war genau mein vorschlag, nur auf die vertikale achse. sozusagen gleichzeitig gepostet

[Gast]

Soll das in etwa so aussehen?
Ja, das soll schon so aussehen, aber anhand der reinen Koordinaten geht das nicht weils ja von ner andern Perspektive aus ist. Stell dir vor du bist ein Auto und bewegst dich von P1 nach P2 und möchtest von dieser Perspektive aus bestimmen ob du jetzt links oder rechts abbiegst wenn du nach Punkt 4 fährst.

[Gast]

Nachtrag: Es ist übrigens ein zweidimensionaler Fall. Das mit den Koordinaten umbiegen erscheint mir auch nicht wirklich zielführend. Da würde man doch berechnen, ob der Punkt gegenüber der Verlängerung von s1 links oder rechts liegt und das hilft mir wenig. Denn ich möchte wissen, welcher der beiden Strecken s2 und s3 denn nun die linke und welche die rechte ist wenn ich von p1 nach p2 komme.

[Monger]

Wenn du die Linie P1->P2 verlängerst, und dann den Winkel mit P2->P3 und und P2->P4 nimmst, bekommst du einen negativen (oder alternativ: größer als 180°) und einen positiven (alternativ: kleiner als 180°) Winkel. Der erste Fall liegt immer links, der zweite Fall immer rechts.

[Gnafoo]

Kreuzprodukt und Rechte-Hand-Regel:

http://de.wikipedia.org/wiki/Kreuzprodukt

Ergo: bestimme die Differenzvektoren a=p2-p1 und b=p3-p1 (alles xz-Ebene). Dann nimm die y-Koordinate mit jeweils y=0 hinzu und berechne das Kreuzprodukt. Je nach Vorzeichen der resultierenden y-Komponente liegt p3 rechts oder links von der Strecke p1 nach p2.

Edit: wenn ich mich grad nicht vertan habe dürfte dich einfach das Vorzeichen von (p2.z-p1.z)*(p3.x-p1.x)-(p2.x-p1.x)*(p3.z-p1.z) interessieren. Geht natürlich analog in der xy-Ebene mit y statt z.

[pool1892]

Da würde man doch berechnen, ob der Punkt gegenüber der Verlängerung von s1 links oder rechts liegt und das hilft mir wenig. Denn ich möchte wissen, welcher der beiden Strecken s2 und s3 denn nun die linke und welche die rechte ist wenn ich von p1 nach p2 komme.
ach so, das ist was anderes als du geschrieben hattest, wenn ich dich recht verstehe (oder ich hab falsch gelesen).
du möchtest wissen, wie die beiden strecken s2 und s3 liegen, wenn die referenz die strecke s1 ist, oder? also wenn du nen kreis im uhrzeigersinn mit radius s1 um p2 ziehen würdest, welche der beiden strecken s2 und s3 bzw. deren verlängerungen wird zuerst geschnitten, ja? ist das jetzt korrekt?

[Gast]

@pool1982: Genau richtig!

@Gnafoo: Es müsste doch in der Formel irgendwie p4 vorkommen, oder?

@Monger: Das gilt aber auch nur wenn die Geraden genau so liegen wie in dem Beispiel. Es soll/muss aber auch bei Extremfällen funktionieren. Wie z.B.

p3
\
\
\
p1----p2
\
\
\
\
p4

(p4 rechts, p3 links)

p1----p2 ---- p3
\
\
\
\
p4

(p4 rechts, p3 links)

p1----p2
/ \
/ \
/ \
/ \
p3 p4

(p4 links, p3 rechts)

[Gnafoo]

Okay ich hab dich nicht ganz richtig verstanden. Bei der Formel kommt raus, ob P3 gegenüber der Verlängerung der Strecke P1-P2 links oder rechts liegt. In dem Fall würde ich das wohl irgendwie über die Winkel lösen. Aber Skalar- und Kreuzprodukt sind immer gute Kandidaten um was zu basteln :D. Da steckt auch jeweils der Winkel zwischen den beiden Vektoren drin.

Edit: du könntest die Geschichte mit dem Kreuzprodukt wohl ausgehend von den Vektoren P4-P2 und P3-P2 machen. Dann dürftest du rausbekommen können, wie die zueinander stehen.

[pool1892]

ok, gast, dann lösen wir das ganz einfach: du bestimmst den punkt p2 zum ursprung, und bringst die vektoren in polarkoordinaten, also länge mal winkel. dann brauchste nur noch die winkel zu vergleichen. du musst wissen, wie s1 liegt, also bei wieviel grad. dann rechnest du: (winkel(s3)-winkel(s2)+winkel(s1))modulo2pi - wenn der wert positiv ist, so ist im urzeigersinn s2 weiter rechts als s3 (weil der standardkreis gegen den uhrzeigersinn dreht)
so ok?
das kann dann auch ein rechner gut schlucken.
die jeweiligen techniken findeste sicher in büchern bzw. dem netz.

hups, nene, das ist (winkel(s3)-winkel(s1))mod2pi-(winkel(s2)-winkel(s1))mod2pi. sry

[pest]

ihr macht das echt alle viel zu kompliziert :|

[Gast]

@pest: Wie gehts denn unkompliziert?

@pool1982: Also du meinst so oder hab ich was vergessen:
1. Bestimmung Winkel mit transformierten Koordinaten:
double s1winkel = Math.atan2(y1 - y2 , x1 - x2);
double s2Winkel = Math.atan2(y3 - y2 , x3 - x2);
double s3Winkel = Math.atan2(y4 -y2 , x4 -x2);

2. Berechnung:
(s3winkel-s1winkel)%(2*Math.PI) - (s2winkel-s1winkel)%(2*Math.PI)

Ist das korrekt?

[Gast]

@pest: Wie gehts denn unkompliziert?

Kreuzprodukt mit z=0, und dann das Vorzeichen testen.

[Gast]

probeirs mal unter dem begriff konvexe hülle ;)

[Gast]

2. Berechnung:
(s3winkel-s1winkel)%(2*Math.PI) - (s2winkel-s1winkel)%(2*Math.PI)

Modulo rechnen mit floats, yeah

[Berni]

Grundsätzlich geht modulo auch bei float/double aber ich glaube man kanns in diesem Fall auch einfach weglassen, denn atan2 bringt eh nur Werte zwischen -PI...PI raus und somit wird ein modulo hier nie was am Ergebnis ändern.

[Gast]

Grundsätzlich geht modulo auch bei float/double aber ich glaube man kanns in diesem Fall auch einfach weglassen, denn atan2 bringt eh nur Werte zwischen -PI...PI raus und somit wird ein modulo hier nie was am Ergebnis ändern.
Modulo ist der Rest aus der Division ganzer Zahlen, das macht mit Reellen Zahlen überhaupt keinen Sinn.

[Gnafoo]

Modulo ist der Rest aus der Division ganzer Zahlen, das macht mit Reellen Zahlen überhaupt keinen Sinn.
Wieso nicht? Das Konzept lässt sich doch ohne Probleme sinnvoll auf Gleitkommazahlen erweitern. Siehe z.B. fmod in C/C++.

z=fmod(a, b) ist die Zahl für die gilt: a = i*b + z, wobei i eine Ganzzahl und maximal ist. Eben genau der Rest, der vom ganzzahligen Vielfachen von b zum genauen Ergebnis fehlen würde.

[DocEW]

Auf die schnelle würde ich sagen, du musst einfach nur testen, ob P4 rechts von s1 liegt ODER P4 rechts von s2 liegt. Ist mindestens eins von beidem erfüllt, liegt P4 in deinem Sinne "rechts".
Zum Testen, ob ein Punkt rechts oder links von einer Geraden liegt, brauchst du die Normalform (siehe http://de.wikipedia.org/wiki/Geradengleichung#Normalform): r*n - c = 0. Wenn du für r einen Punkt rechts von der Geraden einsetzt, kommt für r*n - c etwas Positives raus, für einen Punkt links davon etwas Negatives.

[Bis]

ich habs doch schon erwähnt .. konvexe hülle
für die berechnung dieser gibbet den graham-scan (http://de.wikipedia.org/wiki/Graham_Scan) der dann auch dein problem löst.

[DocEW]

ich habs doch schon erwähnt .. konvexe hülle
für die berechnung dieser gibbet den graham-scan (http://de.wikipedia.org/wiki/Graham_Scan) der dann auch dein problem löst.
Wie soll das funktionieren? P4 kann rechts liegen und dabei sowohl innerhalb der konvexen Hülle der drei anderen liegen oder auch nicht.

[Bis]

Wie soll das funktionieren? P4 kann rechts liegen und dabei sowohl innerhalb der konvexen Hülle der drei anderen liegen oder auch nicht.

hallo?

so:
http://upload.wikimedia.org/math/7/5/7/75780acb99f31a81df0b86acad3af718.png

[DocEW]

Hallo.
1.) Du löst nicht das Problem des Gasts, sondern bestimmst nur, ob ein Punkt rechts oder links von einer Strecke liegt.
2.) Das ganze unter dem Stichwort "Konvexe Hülle" zu verkaufen, nur weil man es in diesem einen Algorithmus im Proprocessing(!) benötig ist ein bisschen dick aufgetragen.

[Coda]

Ich halte auch die Lösung mit dem Kreuzprodukt für am unproblematischsten.

[Bis]

Hallo.
1.) Du löst nicht das Problem des Gasts, sondern bestimmst nur, ob ein Punkt rechts oder links von einer Strecke liegt.
2.) Das ganze unter dem Stichwort "Konvexe Hülle" zu verkaufen, nur weil man es in diesem einen Algorithmus im Proprocessing(!) benötig ist ein bisschen dick aufgetragen.

nö und nö

1)nimmt man die punkte p2,p3,p4 löst graham das problem
2)bei 4 punkten und bekannter direction spuckt die konvexe hülle den übrigen punkt als rechten/linken aus

ein bisschen gehirn investieren und man hätte es wissen können, oder? ;)

Ich halte auch die Lösung mit dem Kreuzprodukt für am unproblematischsten.

japp, eben die idee des graham scan.

[DocEW]

OK, ich verstehe es anscheinend immer noch nicht. Folgendes Beispiel:

p3
|
|
|
p1----p2
/
/
/
p4

Nehme ich jetzt, wie von dir vorgeschlagen, die Punkte p2, p3 und p4, erhalte ich die Information, dass p4 links von p2p3 liegt, oder? Und dann? Die Antwort auf die Frage vom Gast wäre aber "rechts".

P.S.: Ich bleibe dabei, dass das ganze nicht viel mit der Berechnung der konvexen Hülle zu tun hat. Das ist einfach eine Formel um die Lage eines Punktes relativ zu einer Geraden festzustellen. Da hättest du genauso gut ein anderes Stichwort geben können, wie z.B. "Bewegungsplanung für Roboter". Da braucht man das sicher auch irgendwo mal in irgendeinem Algorithmus.

[Coda]

japp, eben die idee des graham scan.
Da braucht man doch nur einen Teil dieses Algorithmus, oder nicht?