AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Multimedia Delphi Prüfen ob Punkt auf Linie

Prüfen ob Punkt auf Linie

Offene Frage von "KahPee"
Ein Thema von KahPee · begonnen am 21. Feb 2010 · letzter Beitrag vom 21. Feb 2010
Antwort Antwort
Benutzerbild von KahPee
KahPee

Registriert seit: 12. Mai 2009
214 Beiträge
 
Turbo Delphi für Win32
 
#1

Prüfen ob Punkt auf Linie

  Alt 21. Feb 2010, 11:42
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?
  Mit Zitat antworten Zitat
mkinzler
(Moderator)

Registriert seit: 9. Dez 2005
Ort: Heilbronn
39.851 Beiträge
 
Delphi 11 Alexandria
 
#2

Re: Prüfen ob Punkt auf Linie

  Alt 21. Feb 2010, 11:44
Irgendeine Näherung muss man aber machen. Man könnte die dicke der Linie erhöhen
Markus Kinzler
  Mit Zitat antworten Zitat
Noedel

Registriert seit: 7. Aug 2008
204 Beiträge
 
Delphi 7 Professional
 
#3

Re: Prüfen ob Punkt auf Linie

  Alt 21. Feb 2010, 11:47
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.
-"Was studierst du eigentlich? Nerdologie?"
-"Informatik..."
-"Wusst ich´s doch!"
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu
Online

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
43.017 Beiträge
 
Delphi 12 Athens
 
#4

Re: Prüfen ob Punkt auf Linie

  Alt 21. Feb 2010, 11:52
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;
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
my Delphi wish list : BugReports/FeatureRequests
  Mit Zitat antworten Zitat
Benutzerbild von SirThornberry
SirThornberry
(Moderator)

Registriert seit: 23. Sep 2003
Ort: Bockwen
12.235 Beiträge
 
Delphi 2006 Professional
 
#5

Re: Prüfen ob Punkt auf Linie

  Alt 21. Feb 2010, 11:54
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.
Jens
Mit Source ist es wie mit Kunst - Hauptsache der Künstler versteht's
  Mit Zitat antworten Zitat
Benutzerbild von KahPee
KahPee

Registriert seit: 12. Mai 2009
214 Beiträge
 
Turbo Delphi für Win32
 
#6

Re: Prüfen ob Punkt auf Linie

  Alt 21. Feb 2010, 11:55
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
  Mit Zitat antworten Zitat
Benutzerbild von DeddyH
DeddyH

Registriert seit: 17. Sep 2006
Ort: Barchfeld
27.534 Beiträge
 
Delphi 11 Alexandria
 
#7

Re: Prüfen ob Punkt auf Linie

  Alt 21. Feb 2010, 11:55
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]
Detlef
"Ich habe Angst vor dem Tag, an dem die Technologie unsere menschlichen Interaktionen übertrumpft. Die Welt wird eine Generation von Idioten bekommen." (Albert Einstein)
Dieser Tag ist längst gekommen
  Mit Zitat antworten Zitat
Benutzerbild von KahPee
KahPee

Registriert seit: 12. Mai 2009
214 Beiträge
 
Turbo Delphi für Win32
 
#8

Re: Prüfen ob Punkt auf Linie

  Alt 21. Feb 2010, 12:07
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.
  Mit Zitat antworten Zitat
Benutzerbild von Aphton
Aphton

Registriert seit: 31. Mai 2009
1.198 Beiträge
 
Turbo Delphi für Win32
 
#9

Re: Prüfen ob Punkt auf Linie

  Alt 21. Feb 2010, 13:53
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
das Erkennen beginnt, wenn der Erkennende vom zu Erkennenden Abstand nimmt
MfG
  Mit Zitat antworten Zitat
Benutzerbild von KahPee
KahPee

Registriert seit: 12. Mai 2009
214 Beiträge
 
Turbo Delphi für Win32
 
#10

Re: Prüfen ob Punkt auf Linie

  Alt 21. Feb 2010, 14:06
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
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 23:43 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz