Ermitteln, ob Punkt auf Linie liegt
Hallo Zusammen,
Ich habe ein Mathematisches Problem:
Ich schreibe mir gerade zur Übung ein einfaches Zeichenprogramm. Das kann Linien,Rechtecke usw. zeichnen.
Die Linie wird mit Hilfe von einer Klasse gezeichnet und in einer List<> abgespeichert.
Wenn ich nun auf die Zeichenfläche klicke instanziiert er jedes ZeichenObjekt zurück in seine Klasse und überprüft dort mit der Methode:
IsOnPoint(PointF checkPoint)
ob z.B. die Linie angeklickt worden ist!
Dann überprüft er mit der Methode
public bool Punkt_auf_Linie(PointF Anfangspunkt, PointF Endpunkt, PointF Kontrollpunkt)
der Klasse "MyMathOP" ob der Punkt auf der Linie liegt.
Und hier ist dann mein eigentliches Problem mit der Formel bzw. mit der Umsetzung.
Die Formel "Punkt auf Gerade" lautet ja y = m * x + t
stimmt es das das t der Punkt ist wo die Linie (wenn man sie verlängert) die Y-Achse schneidet
weil wenn ich das Programm im Einzelsatz debugge eine ewig große Zahl dabei herauskommt
meine Schwester meinte das das auch ohne t geht
hab ich auch schon probiert aber das funktioniert auch nicht
hier meine Methode:
public bool Punkt_auf_Linie(PointF Anfangspunkt, PointF Endpunkt, PointF Kontrollpunkt)
{
double m = (double)Endpunkt.Y - (double)Anfangspunkt.Y / (double)Endpunkt.X - (double)Anfangspunkt.X;//Steigung
double t = Endpunkt.Y * Anfangspunkt.X + Anfangspunkt.Y;// Schnittpunkt Y Achse
double y = m * (double)Kontrollpunkt.X + t;
double toleranz = 0.5;
if (y - Kontrollpunkt.X <= toleranz && y - Kontrollpunkt.X >= -toleranz)
{
return true;
}
else
{
return false;
}
}
also irgendwo ist da ein Fehler drin aber ich find ihn trotz vieler Versuche nicht.
Ich bin um jeden Ratschlag sehr sehr dankbar
Gruß
Puma321
ps. das raubt mir noch den letzten Nerv
Ja, denn der Schnittpunkt mit der Y-Achse lässt sich ermitteln, indem man X=0 setzt. Dadurch wird m*x = 0 und es bleibt nur t übrig.
Deine Formel für m benötigt Klammern. Punkt vor Strich!
Wie kommst du auf die Formel für t? Die kann ich grad gedanklich nicht nachvollziehen.
Es wäre außerdem sinnvoll wenn du am Schluss nicht y mit Punkt.X vergleichst.
Denks nochmal durch. Und vergiss debuggen nicht, mit Kontrolle der Werte an einem von Hand berechneten Beispiel.
Ohne t kann das schon auch funktionieren. Mit der aus beiden Punkten berechneten Steigung kannst du ausrechnen, wo y bei deinem Kontrollpunkt liegen müsste wenn du im Abstand dx von einem der Ausgangspunkte bist. Mals dir auf, dann siehst du bestimmt was ich meine.
Die Geradengleichung lautet y = mx + t
Nachdem du m = (y2 - y1)/(x2 - x1) ausgerechnet hast (Klammern nicht vergessen!) kannst du einfach deine Ausgangsgleichung y =mx + t nach t umformen => t = y - mx.
Dann setzt du für y und x einen der beiden Punkte ein (ist egal welchen).
private bool PunktAufLinie(PointF p1, PointF p2, PointF kP)
{
double m = (p2.Y - p1.Y) / (p2.X - p1.X); // Steigung
double t = p1.Y - m * p1.X; // Die Verschiebung entlang der y-Achse
// double t = p2.Y - m * p2.X; ist auch möglich!
double ykP = m * kP.X + t; // Berechne den Sollwert von kP.Y
const double toleranz = 0.5; // Die erlaubte Abweichung vom Sollwert
return Math.Abs(ykP - kP.Y) <= toleranz; // Ist der Abstand zwischen dem y-Wert des Kontrollpunktes und dem Sollwert des Kontrollpunktes innerhalb der Toleranzgrenze?
}
Noch als Zusatz: Die Funktion betrachtet nur die Differenz in den y-Werten und nicht den tatsächlichen Abstand zwischen dem Kontrollpunkt und der Geraden!
Vielen Dank DerKleineTomy es hat funktioniert
Die Klammern hab ich nicht vergessen nur ich hab sie hier vergessen reinzuschreiben sorry
Nur wenn ich dann eine Linie erstellt hab die parallel zur Y- Achse verläuft funktioniert es nicht
deshalb hab ich noch eine kleine Abfrage unten hingehängt die dann diesen Fehler behebt
nur bleibt dann immer noch ein Problem:
wenn ich die Linie jetzt mit z.B. mit den Koordinaten zeichne
P1 (33|200)
P2 (34|45)
dann erkennt er die Abfrage nicht, da ja X nur um 1 Pixel verschoben ist
wenn ich also dann nochmals abfragen würde ob es nur gering verschoben ist, ist auch dieses wieder ziemlich aufwendig da es ja von der Länge der Linie auch noch abhängig ist
gibt es da noch eine elegantere Lösung ?( oder muss ich das abfragen
was meintest du mit dem Komentar:
Noch als Zusatz: Die Funktion betrachtet nur die Differenz in den y-Werten und nicht den tatsächlichen Abstand zwischen dem Kontrollpunkt und der Geraden!
Ist das des Rätsels Lösung?
Währe es möglich das du dies noch genauer erklären könntest?
Vielen Dank für eure Bemühungen!!! 🙂 🙂 🙂
public bool Punkt_auf_Linie(PointF p1, PointF p2, PointF kP)
{
double m = (p2.Y - p1.Y) / (p2.X - p1.X); // Steigung
double t = p1.Y - m * p1.X; // Die Verschiebung entlang der y-Achse
// double t = p2.Y - m * p2.X; ist auch möglich!
double ykP = m * kP.X + t; // Berechne den Sollwert von kP.Y
const double toleranz = 0.5; // Die erlaubte Abweichung vom Sollwert
bool pal = Math.Abs(ykP - kP.Y) <= toleranz; // Ist der Abstand zwischen dem y-Wert des Kontrollpunktes und dem Sollwert des Kontrollpunktes innerhalb der Toleranzgrenze?
if (pal == true)
{
return pal;
}
else
{
if (p1.X == p2.X)
{
return true;
}
else
{
return false;
}
}
}
Nur mal so am Rande: [Tipp] Anfängerfehler == true / == false
Damit lässt sich dein ganzes if-Konstrukt zu return pal || p1.X == p2.X zusammenfassen.
bei p1.X==p2.X gibst du true zurück?
In diesem Fall ist keine Aussage möglich, denn da kriegst du vorher schon ein Rechenproblem bei der Steigung.
Hi Puma321,
Zunächst vorweg:
Numerisch zu bestimmen, ob ein Punkt exakt auf einer Linie liegt, ist schwierig wegen der beschränkten Rechengenauigkeit.
Stattdessen begnügt man sich damit, zu bestimmen ob der Abstand zwischen Punkt und Linie klein genug ist.
Diesen Schwellwert kann man sogar bewusst etwas größer wählen (mehrere Pixel) um beispielsweise dem User das Auswählen einer Linie zu erleichtern, da es sehr schwer ist, exakt einen Pixel zu treffen.
gibt es da noch eine elegantere Lösung?
Aber ja 😃
Je mathematischer, umso eleganter 😉
Geraden-Gleichungen
Zunächst gibt es für Geraden die unterschiedlichsten Arten der mathematischen Repräsentierung. Hierzu zählen:Die Steigungsform: y=mx+n
*Die (Hessesche) Normalform: p * n - c = 0 ((ich Schreibe Vektoren fettgedruckt und schreibe deren Skalarprodukt als einfachen *)
Die Parameterform: p = a + tv
Nun kann die Steigungsform leider keine senkrechten Geraden beschreiben, fällt also flach. Und die Normalform ist zwar super-elegant für Punkt-Gerade-Abstandsberechnungen, aber schwierig zu erweitern, wenn wir uns Strecken statt Geraden widmen wollen.
(Ich verwende 'Strecke' mal als Synonym für 'Linie')
Strecken-Gleichungen
Die Parameterform lässt sich nun elegant auf Strecken statt Geraden erweitern:
Die Strecke zwischen zwei Punkten A und B lässt sich definieren als:
[B]P[/B] = [B]A[/B] + t * ([B]B[/B]-[B]A[/B]), mit t aus [0,1]
Wenn wir für t alle reellen Zahlen zulassen, dann erhalten wir die komplette Gerade.
Abstand zwischen Punkt und Strecke
Der Abstand zwischen einem Punkt und einer Strecke lässt sich nun formalisieren als der minimale Abstand zwischen dem Zielpunkt und allen Punkten auf der Strecke. Oder aber als exakt der Abstand zwischen dem Zielpunkt und seinem nähesten Punkt auf der Strecke.
Wir finden also im ersten Schritt den nähesten Punkt auf der Strecke und bestimmen im zweiten Schritt den Abstand zu diesem.
Zum Auffinden des nähesten Punktes, bestimmen wir den zugehörigen Parameter t aus obiger Gleichung.
Hierzu nutzen wir das Skalarprodukt zur orthogonalen Projektion und definieren t als:
t' := (([B]P[/B]-[B]A[/B])*([B]B[/B]-[B]A[/B])) / (([B]B[/B]-[B]A[/B])*([B]B[/B]-[B]A[/B]))
Der zugehörige Punkt P' (t' eingesetzt in die Streckengleichung) ist nun die orthogonale Projektion von P auf die Gerade durch A und B und damit der zu P näheste Punkt auf der Gerade. Allerdings könnte P' außerhalb der Strecke liegen! Das ist genau der Fall, wenn t'<0 oder t'>1. Daher müssen wir den Parameterwert t' noch auf das Interval [0,1] beschränken.
t'' := clamp(t', 0, 1) = min(1, max(0, t'))
Nun ist der zugehörige Punkt P'' der näheste Punkt zu P, der auf der Strecke zwischen A und B liegt.
Der Abstand zwischen P und P'' ist schlussendlich der gesuchte Abstand zwischen P und der Strecke AB.
Hier noch der zugehörige PseudoCode:
IsPointOnLine(P,A,B):
V := B-A
t := clamp( ((P-A)·V) / (V·V), 0, 1)
Q := A + t·V
ret (|P-Q| < threshold)
Und hier der C#-Code:
using System.IO;
using System;
using System.Drawing;
public static class PointExtensions
{
public static float Scalar(this PointF a, PointF b)
{
return a.X*b.X + a.Y*b.Y;
}
public static PointF Scale(this PointF a, float factor)
{
return new PointF(a.X * factor, a.Y * factor);
}
public static PointF Add(this PointF a, PointF b)
{
return new PointF(a.X+b.X, a.Y+b.Y);
}
public static PointF Subtract(this PointF a, PointF b)
{
return new PointF(a.X-b.X, a.Y-b.Y);
}
}
class Program
{
static void Main(string[] args)
{
PointF a = new PointF(2,3);
PointF b = new PointF(6,5);
PointF x = new PointF(float.Parse(args[0]),float.Parse(args[1]));
Console.WriteLine(IsPointOnLine(x,a,b));
}
static bool IsPointOnLine(PointF p, PointF lineStart, PointF lineEnd)
{
// Den zu p nähesten Punkt q auf der Strecke bestimmen
PointF startToP = p.Subtract(lineStart);
PointF startToEnd = lineEnd.Subtract(lineStart);
float t = startToP.Scalar(startToEnd) / startToEnd.Scalar(startToEnd);
t = Math.Max(0, Math.Min(t, 1));
PointF q = lineStart.Add(startToEnd.Scale(t));
// Abstand zwischen p und q berechnen
float threshold = 0.5f;
float squared_distance = (p.Subtract(q)).Scalar(p.Subtract(q));
return squared_distance <= (threshold * threshold);
}
}
Natürlich kann man auch eine ordentliche Vektor/Lineare-Algebra Bibliothek verwenden statt mit PointF rumzufummeln. Oder aber man schreibt alles aus ohne Hilfsfunktionen. Wie einem beliebt 😃
Die Berechnung kann genau dann fehlschlagen, wenn eine Division durch Null auftritt, was passiert wenn die Strecke zu einem einzelnen Punkt entartet. Das müsste man noch abfangen.
Ganz nach dem Motto: Wenn Start- und Endpunkt zu nah beieinander liegen, dann ist der Abstand vom Punkt zur Strecke einfach der Abstand zwischen Punkt und Startpunkt.
beste Grüße
zommi
Hi zommi,
Die Lösung von dir ist echt super.
Hat alles funktioniert.
Das hätte ich ohne euch nicht geschaft denn die ganzen Formeln sind mir unbekannt da ich die Hauptschule besucht habe. Das Internet ist da auch sehr hilfreich aber dennoch wenn man es nie gelernt hat sehr aufreibend!
Nochmals vielen Dank an alle Beteiligten.
Gestern Abend hab ich noch ein bischen in Wiki herumgestöbert und bin auf den Bresenhamm-Algorithmus gestoßen
Bresenham-Algorithmus
Mit dieser müsste es doch auch möglich sein herauszufinden ob ich eine Elypse angeklickt habe oder liege ich da mal wieder falsch? (Die Kreisvariante nur etwas modivizierter)
Nochmals vielen vielen Dank für eure Hilfe. 👍 👍
Gruß
Puma321
ps.
hier noch die Methode von der Linie
Die Berechnung kann genau dann fehlschlagen, wenn eine Division durch Null auftritt, was passiert wenn die Strecke zu einem einzelnen Punkt entartet. Das müsste man noch abfangen.
brauch ich nicht abfangen da ich keine Linien zeichnen kann die nur ein einzelner Punkt sind
public static class MyMathOP
{
private static float Scalar(this PointF a, PointF b)
{
return a.X * b.X + a.Y * b.Y;
}
private static PointF Scale(this PointF a, float factor)
{
return new PointF(a.X * factor, a.Y * factor);
}
private static PointF Add(this PointF a, PointF b)
{
return new PointF(a.X + b.X, a.Y + b.Y);
}
private static PointF Subtract(this PointF a, PointF b)
{
return new PointF(a.X - b.X, a.Y - b.Y);
}
public static bool Punkt_auf_Linie(PointF p, PointF lineStart, PointF lineEnd)
{
// Den zu p nähesten Punkt q auf der Strecke bestimmen
PointF startToP = p.Subtract(lineStart);
PointF startToEnd = lineEnd.Subtract(lineStart);
float t = startToP.Scalar(startToEnd) / startToEnd.Scalar(startToEnd);
t = Math.Max(0, Math.Min(t, 1));
PointF q = lineStart.Add(startToEnd.Scale(t));
// Abstand zwischen p und q berechnen
float threshold = 3f;
float squared_distance = (p.Subtract(q)).Scalar(p.Subtract(q));
return squared_distance <= (threshold * threshold);
}
}