# Punkt auf Linie



## Schuriko (9. Mrz 2020)

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 (9. Mrz 2020)

Mathemtisch gesehen?





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


----------



## TM69 (9. Mrz 2020)

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 (9. Mrz 2020)

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 (9. Mrz 2020)

httpdigest hat gesagt.:


> 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;
> ...


Was soll



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


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


----------



## httpdigest (9. Mrz 2020)

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.


----------

