Ein Dreieck, Ein Punkt, eine Gerade ... und ein Schnittpunkt?

[benneq]

Schönen guten Morgen!

Ich bin mal wieder am 'Malen nach Zahlen'. Inzwischen schon wieder viel zu lange, drum frag ich jetzt die klugen Köpfe:

Ich habe ein Dreieck - sogar ein gleichseitiges! - und einen Punkt. Das Dreieck existiert wirklich und der Punkt ist der Mauszeiger Herausfinden, OB der Punkt im Dreieck liegt war bisher nicht schwer dank Canvas -> isPointInPath. Mein Problem betrifft nur den Fall: Punkt außerhalb des Dreiecks.
Wie komme ich an den Punkt des Dreiecks, der die kürzeste Distanz zu meinem Mauszeiger hat?

Mein doofer Ansatz:
Aus den Punkten des Dreiecks Geradengleichungen erstellen und noch eine gerade aus Dreiecksmittelpunkt und dem Mauszeigerpunkt. Danach jeweils Schnittpunkte berechnen und der mit der kürzesten Distanz ist es.
An sich nicht sooo doof, aber irgendwie ist es ungemein schwierig in Java solche Gleichungssysteme aufzustellen, umzuformen und zu lösen.


Folge Daten stehen bereit:
x,y - Position des Mauszeigers
x,y - Position -> Mittelpunkt des Dreiecks
x,y - Position -> 3 Eckpunkte des Dreiecks
natürlich auch Seitenlängen, etc. pp.

Das Dreieck hat eine standard-Ausrichtung. Ich habe auch die aktuelle Drehung parat, aber ich denke, das hilft nicht weiter...

 so sieht's aus, wenn Drehung auf 0° steht:

|\
| \
| /
|/

Hoffentlich gibt's dafür 'ne einfache Lösung, die auch noch schnell Läuft. Die Rechnung wird grob 20x pro Sekunde durchgeführt... Wär schön, wenn am Ende noch Ressourcen für den Rest des Rechners übrig bleiben


Grüße und gut Code!!




EDIIITH!
Schritt weiter: Es gibt nur noch das ursprüngliche Dreieck Ich nehme nun die Mausposition und dreh sie gegen die Drehung des Dreiecks zurück. Ich kann also jetzt mit dem 'normalen' Dreieck rechnen... Aber ich brauch immernoch irgendwelche Formeln.
Mit 3 if-else weiß ich nun schonmal in welchem Bereich der Punkt liegt (links vom Dreieck, oder oben rechts oder unten rechts). Damit sollte man doch was anfangen können oder? Also irgendwie den Schnittpunkt mit dem Dreieck auf dem Weg zu dessen Mittelpunkt berechnen.

 

[Whiz-zarD]

Idee: Betrag eines Vektors = Länge eines Vektors.

Betrag(Eckpunkt 1 - Mausposition) = Länge 1
Betrag(Eckpunkt 2 - Mausposition) = Länge 2
Betrag(Eckpunkt 3 - Mausposition) = Länge 3

Kürzeste Strecke = Suche Minimum (Länge 1, Länge 2, Länge 3)

 

[r0b0t]

Schau mal hier:
http://www.java-forum.org/de/viewtopic.php?p=35533

 

[benneq]

@Wizz: Danke

@robot: Wow! Tolle Seite, extrem informativ und übersichtlich. Das werd ich mir mal nach den ersten Litern Kaffee genauer ansehn

Ergänzung (11. September 2011)

Ich glaub ich stell mich zo blöd an... Warum geht'n das nicht?

Mein Dreieck besteht aus:
P1: (300 / 150)
P2: (75 / 20)
P3: (75 / 280)

Mein Klick: (215 / 62)

Damit ist klar, dass der Klick oben rechts über dem Dreieck gelandet ist (in Canvas ist oben unten, also in einem normalen Koordinatensystem wäre der Klick 'unten rechts' unter dem Dreieck). Also bau ich mir eine Gerade aus P1 und P2, da diese Gerade zwischen Klickpunkt und Mittelpunkt liegt (nach Anleitung von robot):
double a0 = p1Y - p2Y;
double b0 = -(p1X - p2X);
double c0 = -(a0 * p1X + b0 * p1Y);

Dann noch eine Gerade zwischen Klick und Mittelpunkt: (triangleCenter ist 150)
double a1 = triangleCenter - klickY;
double b1 = -(triangleCenter - klickX);
double c1 = -(a1 * triangleCenter + b1 * triangleCenter);

ich hoffe mal, dass es bis hier noch korrekt ist...


... und dann habe ich die Formel zur Schnittpunktsberechnung genommen:
double y = ( a1 / a0 * c0 - c1 ) / (b1 - a1 / a0 * b0 );
double x = (b0 * y + c0) / (-a0);

Sieht jemand den Fehler??

Ergänzung (11. September 2011)

Gerade von Hand überprüft:

Die 2 Geradengleichungen stimmen, wenn ich die Punkte einsetze, aus denen ich die Gleichung berechnet habe, dann kommt das Richtige raus... dann setz ich mich mal an den Schnittpunkt

Ergänzung (11. September 2011)

Den Fehler konnte ich nun eingrenzen. Aber irgendwie nicht so klar was es genau ist:
Ich hab die Koordinaten für den Schnitt nun per Hand berechnet und TADA:
MEIN Ergebnis: y = 89 , x = 194
COMPUTERS Ergebnis: y = 89 , x = 147

Das hieße, dass das Problem in der letzten Zeile auftreten muss. So recht erklären kann ichs mir noch nicht ...

Ergänzung (11. September 2011)

ICH HAB'S!!!

Merke: Der beste Weg, um Probleme jeder Art zu vermeiden ist: Variablennamen nicht doppelt zu benutzen...

 

[Whiz-zarD]

Was rechnest du da überhaupt? O_o

Ich nehm mal dein Beispiel:

P1: (300, 150)
P2: (75, 20)
P3: (75, 280)
Maus: (215, 62)

Länge1 = Betrag(P1.X - Maus.X, P1.Y - Maus.Y) = Betrag(85, 88) = sqrt(85² + 88²) = 122,34
Länge2 = Betrag(P2.X - Maus.X, P2.Y - Maus.Y) = Betrag(140, 42) = sqrt(140² + 42²) = 146,16
Länge3 = Betrag(P3.X - Maus.X, P3.Y - Maus.Y) = Betrag(140, -218) = sqrt(140² + 218²) = 259,08

kürzeste Strecke = Länge1.
Also Strecke zwischen P1 und Maus.

 

[benneq]

Ich hab den Schnittpunkt zwischen
G1 und G2 berechnet, wobei:
- G1 = Gerade zwischen Klick und Mittelpunkt des Dreiecks
- G2 = Seite des Dreiecks, die am nächsten am Klick ist

damit bekommt man halt keine rechten Winkel, sondern eine Linie zum Mittelpunkt. Aber ich hab gerade ein wenig damit gespielt und es fühlt sich nicht intuitiv an. Ich denke kürzester Weg (also rechter Winkel auf der Seite des Dreiecks) ist besser für's Gehirn


Es geht mir auch nicht so sehr um den Abstand (den hab ich schon), sondern um den genauen Punkt auf der Geraden (P1 -> P2), der diesen Abstand zum Mauszeiger hat.

 

[R3ddy]

Hi benneque,

Folgendes sollte funktionieren:
P1(x1,y1) - erster Eckpunkt
P2(x2,y2) - zweiter Eckpunkt
P2(x3,y3) - Mauszeiger

der Punkt P4(x,y), auf der Graden die durch P1 und P2 geht, die den kürzesten Abstand zu P3 hat, ergibt sich aus folgenden Gleichungen:

x=(x1^2 x3 + x2 (x2 x3 + (y1 - y2) (y1 - y3)) +
x1 (-2 x2 x3 - (y1 - y2) (y2 - y3)))/(x1^2 -
2 x1 x2 + x2^2 + (y1 - y2)^2)

y=(x2^2 y1 + x1^2 y2 + x2 x3 (-y1 + y2) -
x1 (x3 (-y1 + y2) + x2 (y1 + y2)) + (y1 - y2)^2 y3)/(x1^2 -
2 x1 x2 + x2^2 + (y1 - y2)^2)

Darauf kommt man wenn man Die Gradengleichung durch Punkt P1 und P2 aufstellt, sowie die Gradengleichung senkrecht dazu, die durch Punkt P3 geht und die beiden dann gleichsetzt und auflöst.

Du musst allerdings noch prüfen ob der Punkt zwischen P1 und P2 liegt, dass sollte aber kein Problem sein.

 

[benneq]

Oh wow

Krasse Gleichung Hast du dir gerade aus den Fingern gesaugt? Oder worauf basiert die? Ein wenig Hintergrund ist nie verkehrt Seit ich an der Uni bin kann ich nicht mal mehr lineare Gleichungssysteme lösen, nur noch komplexe Kacke in n-Dimensionalen Räumen. Einkaufen geht auch nur, wenn ich die Produkte am Strichcode erkennen kann und auf dem Kassenbon der Betrag als Unärzahl steht... Echt schon peinlich

Das mit dem Prüfen ist ja das geringste Problem... Math.min und Math.max sind meine Freunde

 

[R3ddy]

Na sowas weiß man natürlich auswendig

Ne, hab ja schon angedeutet wie man drauf kommt:
Gradengleichung aufstellen, die durch Punkt P1 und P2 geht:
(y - y1)/(x - x1) = (y2 - y1)/(x2 - x1)

Grade senkrecht dazu die durch Punkt P3 geht:
y=y3 +m*(x - x3) mit m=-1/((y2 - y1)/(x2 - x1)))

Dann die Formeln nach x bzw. y Umstellen und nach der anderen Variablen auflösen. Das hab ich dann mit Mathematica erledigt.

 

[Quickbeam2k1]

Also mir ist nicht klar warum du den Mittelpunkt des Dreiecks betrachtest. Was man sich auch anschauen kann ist ob drei aufeinander folgeende Punkte einen links oder rechtsknick bilden.

Google mal nach algorithmischer Geometrie. Da dürfts noch weitere schöne Sachen drinnen geben

 

[benneq]

@Quickbeam: Der Mittelpunkt (wie mehrfach erwähnt) wurde ausschließlich betrachtet, um einen Schnittpunkt mit einer Seite des Dreiecks zu erhalten. Und inzwischen ist mir die senkrechte Variante lieber wegen der Benutzbarkeit.
Ob ich links, rechts, vor oder hinter das Dreieck geklickt habe, hatte ich schon im 1. Post gelöst

@Reddy: Danke... Ja stimmt ja... senkrecht ist, wenn die Steigung m' = -1/m ist ... *klick*

 

[Quickbeam2k1]

Also man kan mit Determinantenberechnungen für die 3 Dreieckspunkte und deinen Viertenpunkt schon direkt sagen ob der Punkt innerhalb oder außerhalb des Dreiecks liegt und man kan auch damit zeigen dann 2 geradensegmente einen schnittpunkt haben.
Das ist alles ziemlich effizient und so könnte man halt schnell rausfinden auf welcher seite es den Schnittpunkg gibt.

Hier ab Seite 27. Wobei ich da jetzt nicht gesehen hab dass der Point in Polygon test auf einen Orientierungstest im R^3 zurückgeführt wird.

Ich will halt nur sagen: Man kann mir etwas abstrakterer Mathematik schon mal einen Großteil der Probleme die du hast effizient lösen.

 

[Xtremebergi]

Warum benutzt du nicht einfach Vektoren? Das würde die Sache erheblich vereinfachen.

 

[benneq]

@Xtremebergi:
Ich nutz doch quasi schon Vektoren. Punkt + Steigung. Keine Anfang und Ende definiert.
Oder meinst du konkrete Vektor-Objekte? Soweit will ich nicht gehen, dann würde das Programm jede Sekunde noch 50 komplett, neue Objekte erstellen und wieder löschen.


@Quickbeam:
Ich will/muss nicht alles ausrechnen, ab und zu ist der bequeme Weg auch in Ordnung, wenn er nicht gerade langsam ist. Z.B. die Frage 'ist Punkt innerhalb oder außerhalb des Dreiecks?'. Die überlasse ich komplett dem Browser. Der hat da eine native Implementierung für und muss kein JS-Code interpretieren. Also nutz ich diese Lösung, außerdem ist es für mich ein 1-Zeiler
Das ist in diesem Zusammenhang auch die Abfrage, die am Häufigsten passiert.

 

[voodoo44]

Warum nimmst du nicht den vorgeschlagenen Weg, welcher mit Hilfe der Vektoren entsprechend den Abstand über den Betrag auszurechnen?

 

[benneq]

Ich hab das von Reddy schon implementiert und es funktioniert hervorragend

Aber man weiß ja nie, ob es noch eine un-algebraische Lösung gibt, die es irgendwie anders löst und dabei sehr simpel ist ^^