Punkt auf Linie

[Schuriko]

Ich suche gerade eine effiziente Methode, wie man herausbekommt, ob P3(x,y) auf der einer Linie liegt die sich von P1(x,y) zu P2(x,y) erstreckt.
Kann mir hier einer weiterhelfen?

 

[krgewb]

Mathemtisch gesehen?

Ich denke, dass es nicht trivial wird wegen der Ungenauigkeit bei float.

 

[TM69]

Dieses lässt sich ganz einfach durch die Formel:

sqrt((p1.x - p3.x)^2 + (p1.y - p3.y)^2) + sqrt((p2.x - p3.x)^2 + (p2.y - p3.y)^2) = sqrt((p1.x - p2.x)^2 + (p1.y - p2.y)^2)

berechnen. Wobei P1 und P2 der Start / Endpunkt ist und P3 der gesuchte Punkt.

 

[httpdigest]

Wenn du Fließkommaarithmetik verwendest und die Linie nicht exakt entlang einer der beiden Hauptaxen verläuft, wird der Punkt P3 niemals _exakt_ auf der Linie sein. Du kannst hier nur mit einem maximalen Margin/Epsilon rechnen. Und dann einfach lineare Algebra anwenden:

float dy = p2y - p1y, dx = p2x - p1x;
float d = Math.abs(dy*p3x - dx*p3y + p2x*p1y - p2y*p1x) / (dy*dy + dx*dx);
boolean punktAufLinie = d < 1E-3f; // <- beliebiges Epsilon

 

[Schuriko]

Wenn du Fließkommaarithmetik verwendest und die Linie nicht exakt entlang einer der beiden Hauptaxen verläuft, wird der Punkt P3 niemals _exakt_ auf der Linie sein. Du kannst hier nur mit einem maximalen Margin/Epsilon rechnen. Und dann einfach lineare Algebra anwenden:

float dy = p2y - p1y, dx = p2x - p1x;
float d = Math.abs(dy*p3x - dx*p3y + p2x*p1y - p2y*p1x) / (dy*dy + dx*dx);
boolean punktAufLinie = d < 1E-3f; // <- beliebiges Epsilon

Was soll

boolean punktAufLinie = d < 1E-3f; // <- beliebiges Epsilon

sein? Woher kommt 1E und 3f????

 

[httpdigest]

https://en.wikipedia.org/wiki/Scientific_notation#E_notation
1E-3 steht für eine Eins mit drei führenden Nullen, also: 0.001. Das "f" ist der Suffix für eine Floating-Point-Zahl.
Gerade wenn man sehr kleine (nahe Null) Zahlen repräsentieren will, z.B. ein Nano-Irgendwas, also eine Eins mit Neun (Nano = ein Milliardstel) Nullen, braucht man nicht 0.000000001 zu schreiben und dem Leser abzuverlangen, dass er erstmal die Nullen zählt, sondern kann 1E-9 schreiben.