Prüfen ob Punkt auf Linie

[KahPee]

Da es ein neues Thema ist fang ich nen neuen Thread an (Ich liebe Forenregeln). Wie der Threadtitel schon sagt geht darum zu prüfen ob ein auf eine Linie geklickt wurde. Start und Endpunkt der Linie sowie der geklickte Punkt sind bekannt:

Zitat von DeddyH:

Ich habe gerade etwas bei den Schweizern gefunden.

Delphi-Quellcode:

//von den Schweizern:
function Collinear(x1, y1, x2, y2, x3, y3: Double): Boolean;
begin
  Result := (((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)) = 0);
end;

Das ist schon mal ziemlich gut. Allerdings glaube ich, dass diese Prozedur missachtet, dass eine Linie nicht perfekt auf die Leinwand gezeichnet werden kann. Es kommt ja beim Zeichnen zu Rundungsfehlern, da es ja nicht möglich ist 1,4 Pixel zu Zeichnen..
Hat jemand ne Idee wie man das noch beachten kann?

[mkinzler]

Irgendeine Näherung muss man aber machen. Man könnte die dicke der Linie erhöhen

[Noedel]

also in Mathe macht man das immer folgendermaßen:
bekannten Punkt P in f(x) einsetzen und auf Gleichheit prüfen.
Das sollte nicht so schwer zu realisieren sein.
Jetzt kann es immer noch sein, dass der Punkt "außerhalb" der Linie liegt. Dazu müsstest du dann
sehen, ob der x-Wert des Punktes zwischen dem x-Wert des Startpunktes und x-Wert des Endpunktes liegt.
Da es ja keine senkrechten Linien geben kann (laut deiner Aussage (Linie ist mit f(x)=ax+b beschreibbar)), müsste das so hinhauen.

[himitsu]

Vorallem das =0 zusammen mit Double ist witzig ... wo wir doch alle Wissen, daß man da doch nicht so genau prüfen soll

eventuell ja so?

Delphi-Quellcode:

function Collinear(L1x, L1y, L2x, L2y, Px, Py, B: Integer): Boolean;
begin
  Result := Abs((L2x - L1x) * (Py - L1y) - (Px - L1x) * (L2y - L1y)) <= B*B*B;
end;

[SirThornberry]

Wenn man Toleranz zulassen will kann man es auch anders machen.
Man hat ja:
- Startpunkt
- Endpunkt
- Klickpunkt

Jetzt kann man zu erst prüfen ob x und y des Klickpunktes innerhalb der Linienpunkte sind.
Anschließend nimmt man sich zum Beispiel X des Klickpunktes und berechnet welchen Y-Wert der Klickpunkt haben müsste damit er auf der Linie liegt. Diesen errechneten Y-Wert vergleicht man dann mit dem tatsächlichen Y-Wert des Klickpunktes.

[KahPee]

Zitat von mkinzler:

Irgendeine Näherung muss man aber machen. Man könnte die dicke der Linie erhöhen

Ja klar. Das Problem dabei ist nur folgendes.. Wenn ich den obigen Code nehme. So könnte es sein, dass alle drei Punkte auf einer Linie liegen aber die Prozedur zurückgibt, dass sie nicht auf einer Linie liegen.

Die Liniendicke (pen.width) ließe sich meiner Meinung nach genauso wie die Toleranz recht einfach einbauen:

Delphi-Quellcode:

function Collinear(x1, y1, x2, y2, x3, y3: Double): Boolean;  //x2,y2 ist der Punkt auf den geklickt wurde
var i: integer;
begin
  for i:=-(toleranz+liniendicke) to (toleranz+liniendicke) do
  begin
   if ((((x2+i) - x1) * (y3 - y1) - (x3 - x1) * ((y2+i) - y1)) = 0) then 
    begin
     result:=true;
     exit;
    end
   else result:=false;
  end;

end;

mfg Kahpee

[DeddyH]

Oder man prüft nicht genau auf 0, sondern baut eine Toleranzschwelle ein. Oder man bildet 2 rechtwinklige Dreiecke und prüft, ob die Verhältnisse zwischen Hypotenuse und Ankathete in etwa gleich sind, wobei man auch hier eine Toleranzschwelle einbauen müsste.

[edit] *Oops* die obigen Beiträge sind irgendwie an mir vorbeigegangen [/edit]

[KahPee]

Ich hab grad ein Problem mehr gefunden.. -> senkrechte Linien sind möglich. Allerdings ist das kein wirkliches Problem. Wenn die x werte von start- und endpunkt gleich sind wird einfach ne andere Routine aufgerufen.

Da das schweizersystem scheinbar nicht so einfach ist wie zuerst gedacht.. Vllt doch noch mal die konventionelle variante:

Zitat:

d.h. ich würde als allererstes die Steigung der Linie ausrechnen. Dann müsste man den y-Achsenabschnitt ermitteln (bei dem Ursprung oben links wird der negativ)

und dann für x=start.x bis end.x alle Punkte der Linie mittels f(x)=m*x+b errechnen. Wenn ein Punkt errechnet wurde wird dieser mit dem Punkt an den geklickt wurde verglichen. Sollte es einen Treffer geben wird die Prozedur abgebrochen und der Wert der Funktion als "true" zurückgegeben. Wenn es keinen Treffer gab wird der nächste Punkt geprüft.

Delphi-Quellcode:

function checkpointonline(start.x, start.y, ende.x,ende.y,p.x,p.y):boolean;
var x: extended;
    b,i,a: integer;
begin
  m := (end.y-start.y)/(end.x-start.x);
  b:= round(end.y-(m*end.x);

  for i:=-(toleranz+stifdicke) to toleranz+stiftdicke do
   begin
   for a:=-(toleranz+stifdicke) to toleranz+stiftdicke do
   begin
     if (p.y+i)=round((p.x+a)*m+b) then
      begin
        result:=true;
        exit;
      end
     else result:=false;
   end;
  end;
end;

Problem bei diesem Algorithmus könnte sein, dass das ziemlich langsam wird bei längeren Linien und vorallem vielen Linien die überprüft werden sollen.

[Aphton]

Hier sind meine Überlegungen zum Thema.
Die erste Funktion ist fürs performante und direkte Prüfen - ob sich ein Punkt auf der Linie befindet - gedacht.
Die zweite Funktion berücksichtigt auch die Dicke einer Linie, die beliebig gesetzt werden kann.

Delphi-Quellcode:

function PointOnLine( LineStart, LineEnd, LinePoint: TPoint ): Boolean; overload;
var
    v: Single;
begin
    Result := False;
    // Verschiebe Line zum Ursprung und passe Punkt an
    LineEnd := Point( LineEnd.X - LineStart.X, LineEnd.Y - LineStart.Y );
    LinePoint := Point( LinePoint.X - LineStart.X, LinePoint.Y - LineStart.Y );
    // wenn Punkt.X <= LineEnd.X, kann sie auf der Linie liegen
    if LinePoint.X > LineEnd.X then
        Exit;
    // Da der Punkt auf der Linie liegt, muss sie ein vielfaches des
    // Richtungsvektors vek(linestart-lineends) sein
    v := LinePoint.X / LineEnd.X;
    if LinePoint.Y / LineEnd.Y <> v then
        Exit;
    Result := True;
end;

function PointOnLine( LineStart, LineEnd, LinePoint: TPoint; Thickness: Single ): Boolean; overload;
var
    kX, y: Single;
begin
    Result := False;
    // Verschiebe Line zum Ursprung und passe Punkt an
    LineEnd := Point( LineEnd.X - LineStart.X, LineEnd.Y - LineStart.Y );
    LinePoint := Point( LinePoint.X - LineStart.X, LinePoint.Y - LineStart.Y );
    // wenn Punkt.X <= LineEnd.X, kann sie auf der Linie liegen
    if LinePoint.X > LineEnd.X then
        Exit;
    // berechne die Steigung der Funktion und ermittle den y wert an der Stelle LinePoint.X
    kX := LineEnd.Y / LineEnd.X;
    y := kX * LinePoint.X;
    // Prüfe, ob die Differenz < Thickness ist
    if Abs( LinePoint.Y - y ) > Thickness then
        Exit;
    Result := True;
end;

Edit: Ich habe nicht ausgiebig getestet, ob die beiden Routinen auch 100%ig fehlerfrei funktionieren.

MfG

[KahPee]

So ich habe einen deutlich besseren Lösungsweg gefunden.

Die Funktion der Linie ist durch f(x)=m*x+b gegeben (m und b sind bekannt).
Da wir mit einer Toleranz arbeiten wollen rechnen wir einfach die Abweichung des geklickten Punkts(x1,y1) von der Linie aus. Die Abweichung ist die Strecke vom Punkt zu der gegebenen Linie f(x) also durch die Orthogonale die durch g(x)=-(1/m)*x+c (m bekannt) definiert ist.
Die unbekannte c kann man durch einsetzten des Punktes in die Orthogonale rausbekommen:
g(x1)=y1 =>-(1/m)*x1+c=y1 =>c=y1+(1/m)*x1

nun kann man g(x)=f(x) lösen und dann kann man den Schnittpunkt(x2,y2) der Orthogonalen und mit der Linie ausrechnen (der Schnittpunkt ist dann letztendlich in Abhängigkeit von m, b, x1 und x2 gegeben)

Anschließend noch die Abweichung:

Abweichung=sqrt((x1-x2)^2+(y1-y2)^2)

Das ist der mathematische Weg. Aber der informatische ergibt sich dann ja. Einfach noch prüfen ob der Betrag der Abweichung <= tol+stifdicke ist. Diese Variante missachtet wenn man ganz am ende der Linie nach oben oder unten daneben klickt.


mfg KahPee