Koordinaten nahe einer Strecke finden

[DominikJ]

Moin,

ich stehe grad mal total aufm Schlauch.

Und zwar habe ich 2 Punkte.

Koordinaten sind Variable aber als Beispiel kann man ja einfach P1[2|5] und P2[4|1] nehmen.

Nun habe ich noch einen Haufen andere Koordinaten.

Mein Problem ist nun, ich muss nun alle Koordinaten sammeln, welche maximal eine Entfernungseinheit von der Verbindung Zwischen P1 und P2 entfernt sind.

Hat wer ne Denkstütze für mich? Oder evtl. was ähnliches gemacht?

Danke & Gruß,

Dominik

[Sturm]

Hmm... nach einer Minute überlegen bin ich auf folgende Idee gekommen:

Meine These ist, dass alle validen Koordinaten:

- Innerhalb eines Kreises (Kreis 1) mit Mittelpunkt P1 und Radius 1 liegen ODER

- Innerhalb eines Kreises (Kreis 2) mit Mittelpunkt P2 und Radius 1 liegen ODER

- zwischen den beiden Tangenten liegen, die Kreis 1 und Kreis 2 berühren...

Meinungen und / oder Verbesserungen sind willkommen!

EDIT zu Bedingung 3: Es sind natürlich nicht alle Koordinaten zwischen den beiden Tangenten gültig.

Es sind nur die gültig, die zwischen den beiden Kreisen liegen!

Bearbeitet 29. April 2009 von Sturm

[flashpixx]

Mein Problem ist nun, ich muss nun alle Koordinaten sammeln, welche maximal eine Entfernungseinheit von der Verbindung Zwischen P1 und P2 entfernt sind.

Was heißt "maximal eine"? Ich deute es <= 1. Daraus folgt, dass Du alle Punkte haben willst (ich gehe von 2D aus), die innerhalb eines Kreise mit dem Radius 1 und auf der Kreislinie liegen. Da Du nun das ganze auf zwei Punkte beziehst ist die Lösung, die Schnittmenge beider Kreise.

siehe dazu das Venn-Diagramm für den Durchschnitt Mengendiagramm ? Wikipedia

Phil

[Sturm]

Was heißt "maximal eine"? Ich deute es <= 1. Daraus folgt, dass Du alle Punkte haben willst (ich gehe von 2D aus), die innerhalb eines Kreise mit dem Radius 1 und auf der Kreislinie liegen. Da Du nun das ganze auf zwei Punkte beziehst ist die Lösung, die Schnittmenge beider Kreise.

siehe dazu das Venn-Diagramm für den Durchschnitt Mengendiagramm ? Wikipedia

Phil

Ich glaube, er möchte die Vereinigungsmenge aller Kreise haben,

deren Mittelpunkt auf der Strecke zwischen P1 und P2 liegt und

die den Radius 1 haben ...

[kingofbrain]

Servus,

mein Ansatz wäre folgender: die kürzeste Verbindung eines Punkte zu einer Strecke ist das Lot auf die Strecke durch den Punkt, wenn der Punkt ein Lot auf die Strecke bilden kann. In allen anderen Fällen ist es die kürzere Entfernung zu den beiden Endpunkten der Strecke. Diese zwei Längen sollten mathematisch zu ermitteln sein (meine Geometriekenntnisse sind ein wenig eingerostet) und gegen den maximal zulässigen Wert verglichen werden können.

Peter

[flashpixx]

die kürzeste Verbindung eines Punkte zu einer Strecke ist das Lot auf die Strecke durch den Punkt, wenn der Punkt ein Lot auf die Strecke bilden kann.

Das Lot ist nur dadurch definiert, dass es orthogonal zu der Strecke ist, über die Länge ist keine Aussage getroffen.

Diese zwei Längen sollten mathematisch zu ermitteln sein (meine Geometriekenntnisse sind ein wenig eingerostet) und gegen den maximal zulässigen Wert verglichen werden können.

Wie hilft dies weiter? Ich berechne also entweder den Abstand des Punktes zur Graden oder zu einem der Endpunkte der Strecke.

Bitte einmal an den OP, was ist das genaue Problem!

Phil

[flashpixx]

Ich glaube, er möchte die Vereinigungsmenge aller Kreise haben,

deren Mittelpunkt auf der Strecke zwischen P1 und P2 liegt und

die den Radius 1 haben ...

Das sind aber per Definition unendlich viele Kreise !?

Phil

[Sturm]

Was kingofbrain denke ich meint:

Wenn die Strecke zwischen einem Punkt X und der Strecke P1P2 kleiner als 1 ist, ist Punkt X gültig. Die Strecke zwischen Punkt X und der Strecke P1P2 ermittelt er über das Lot.

Und wenn das Lot nicht möglich ist, überprüft er, die Entfernung zu den Endpunkten der Strecke...

In meinen Ohren klingt das nicht schlecht, wenn er überprüfen will, ob ein Punkt X gültig ist.

Das sind aber per Definition unendlich viele Kreise !?

Rischtiiisch Daher mein Ansatz mit den Tangenten.

Jedes Lot auf die Strecke P1P2 sollte eine der Tangenten schneiden und mit ihr einen rechten Winkel bilden. Und zwar immer bei der Einheit 1.

Bearbeitet 29. April 2009 von Sturm

[Sturm]

Und weils so schön ist meine Idee nochmal als Grafik

Alle Punkte innerhalb des gelben Bereichs sind weniger als eine Einheit von p1p2 entfernt.

[flashpixx]

Wenn die Strecke zwischen einem Punkt X und der Strecke P1P2 kleiner als 1 ist, ist Punkt X gültig. Die Strecke zwischen Punkt X und der Strecke P1P2 ermittelt er über das Lot.

Und wenn das Lot nicht möglich ist, überprüft er, die Entfernung zu den Endpunkten der Strecke...

Das ist geometrisch gesehen ein Rechteck einmal mit der Seitenlänge "Streckenlänge zwischen P1 und P2" wobei die Seiten die nicht der Streckenlänge entsprechen Kreisbögen sind (mit Radius 1) sind.

Was meiner Ansicht auch Deinem Ansatz entspricht, nur dass Du, genau 2 Tangenten betrachtest, die parallel zu der Verbindungsstrecke liegen und beide Kreise berühren. (Theoretisch kann ich bei Deiner Beschreibung auch eine Tangente nehmen, die Kreis eins "bildlich" recht schneidet und diagonal verläuft und Kreis 2 links schneidet - Du hattest die Parallelität in Deinen Tangenten vergessen)

Phil

P.S.: Zum Bild, genauso, aber die Tangenten verlaufen Parallel, nach Deinem ersten Post währen sie auch diagonal möglich

Bearbeitet 29. April 2009 von flashpixx
Kommentar zu Bild

[DominikJ]

Hey,

an die Kreisgeschichte hatte ich auch schon gedacht.

Es geht dadrum, bestimmte Punkte auf einer Karte welche nahe einer Route liegen mit in eine Route einzubeziehen. Natürlich ist die Methode so oder so sinnfrei, da eine Straße nicht Gerade verläuft...

Ich habe es nun wie folgt gemacht, hatte den Lösungsansatz auch kurz nach erstellen des Threads verfolgt, konnte aber leider nid Antowrten, weil mir förmlich der A*sch brannte und was fertig machen musste

-> Entfernung zwischen Punkt A zu B berechnen = StreckeAB

-> Datenbank abklappern nach Einträgen, bei welchen:

 -> Entfernung zu Punkt A maximal StreckeAB+5,

 -> Entfernung zu Punkt B maximal StreckeAB+5,

 -> Gesamtentfernung zu beiden Punkten maximal StreckeAB+5 

Somit habe ich nahe am Ursprungs- und Zielort relativ genaue Ergebnisse, auf der Strecke natürliche enorme Abweichungen.

Diese Lösung ist auch in der Programmierung recht leicht umzusetzen, bzw. ist diese es schon ...

Danke für eure Hilfe!

Edit:

Sturm,

das war mein aller erster gedanke und steht auch so aufm papier.

Leider hatte ich da Probleme bei der Umsetzung und Geometrie war nie so meine Stärke -.-

Wenn dafür nochwer nen Pseudocode hat ist das natürlich was anderes

Bearbeitet 29. April 2009 von DominikJ

[Sturm]

Du hast recht, flashpixx!

Die Möglichkeit der nichtparallelen Tangenten habe ich nicht bedacht. :old

Aber ansonsten schaut die Lösung denke ich mal akzeptabel aus. Mal schauen was DominikJ meint

EDIT: Nichts zu danken! Hoffe nur, dass deine Strecken nicht zu groß werden

Bearbeitet 29. April 2009 von Sturm

[DominikJ]

EDIT: Nichts zu danken! Hoffe nur, dass deine Strecken nicht zu groß werden

Ich hatte den wert erst auf 25 gesetzt, was mir auf einer Strecke von Hannover nach Berlin erstmal Salzwedel angezeigt hat

Da suche ich gerade ein Programm um mir das mal zu veranschaulichen.

Hat irgendwer da nen Freeware/Opensource Tool zu empfehlen?

Gruß

[flashpixx]

Ich hatte den wert erst auf 25 gesetzt, was mir auf einer Strecke von Hannover nach Berlin erstmal Salzwedel angezeigt hat

Kannst Du bitte einmal das Problem genau beschreiben?

Willst Du so etwas wie eine Umkreissuche realisieren, d.h. Du hast eine Strecke und möchtest umliegende Orte an der Strecke anzeigen?

Ich sehe da das Problem, dass Du hier von einem Idealfall ausgehst, eine Straße ist nicht gerade, d.h. Du musst Deine Strecke in einen Polygonzug zerlegen und für jede Teilstrecke die Berechnung durchführen

Phil

[DominikJ]

Kannst Du bitte einmal das Problem genau beschreiben?

Willst Du so etwas wie eine Umkreissuche realisieren, d.h. Du hast eine Strecke und möchtest umliegende Orte an der Strecke anzeigen?

Ich sehe da das Problem, dass Du hier von einem Idealfall ausgehst, eine Straße ist nicht gerade, d.h. Du musst Deine Strecke in einen Polygonzug zerlegen und für jede Teilstrecke die Berechnung durchführen

Phil

Ja, genau das.

Und wie ich ja auch schon geschrieben hab, ist es relativ sinnlos es so zu machen, da eine Strecke nicht gerade verläuft... bzw. sehr unwahrscheinlich.

Leider kann ich es nicht anders machen, da ich nur die Selektion mache, die Darstellung jedoch in einem Drittprogramm erfolgt.

[kingofbrain]

Die Diskussion ist zwar schon weiter und mein Lösungsvorschlag in einem anderen mit dem Rechteck mit den Halbkreisen an den Streckenenden), aber hier trotzdem noch die Antwort auf flashpixx' Fragen:

Das Lot ist nur dadurch definiert, dass es orthogonal zu der Strecke ist, über die Länge ist keine Aussage getroffen.

Ich bin mir sicher, dass ich von einem gegebenen Punkt X und einer Strecke s berechnen kann, ob X erstens so über oder unter s liegt, dass ich ein Lot bilden kann, und dass ich zusätzlich auch errechnen kann, wie lang dieses Lot ist. Die Aussage über die Länge ist ja genau die Lage von X.

Wie hilft dies weiter? Ich berechne also entweder den Abstand des Punktes zur Graden oder zu einem der Endpunkte der Strecke.

Phil

Genau, und mit diesen Daten kannst Du ermitteln, ob der Punkt innerhalb oder außerhalb eines bestimmten Abstansds um die Strecke herum liegt. Und so hatte ich den OP verstanden.

Peter

[flashpixx]

Leider kann ich es nicht anders machen, da ich nur die Selektion mache, die Darstellung jedoch in einem Drittprogramm erfolgt.

Vielleicht möchtest Du einmal alle notwendigen Infos posten, denn es macht wenig Sinn, Dir stückchenweise Informationen heraus zu kitzeln. Du möchtest eine Umkreissuche realisieren, okay, welche Daten hast Du, welches Format haben die Daten usw?

Phil

[Bubble]

Und wie ich ja auch schon geschrieben hab, ist es relativ sinnlos es so zu machen, da eine Strecke nicht gerade verläuft... bzw. sehr unwahrscheinlich.

Da die Route mit Sicherheit aus einzelnen Teilabschnitten besteht, kannst Du die bereits beschriebenen Verfahren für jede Teilstrecke verwenden und die Ergebnisse dann zusammenfassen.

Wenn Du jedoch keinen Zugang zu diesen Teilabschnitten hast, dann kannst Du keine Orte in einer maximalen Entfernung zu der aus Teilabschnitten bestehenden (beliebig verlaufenden) Route bestimmen.

(Darauf könnte man aber auch selbst kommen.)

Vielleicht hilft aber folgende Idee: Wenn Du vorher in keiner Weise an die Teilabschnitte oder wenigstens sich auf der Strecke befindliche Koordinaten herankommst, dann könntest Du, sofern das System mobil benutzt wird, interessante Orte (Sehenswürdigkeiten?) periodisch für den aktuellen Standort bestimmen, sofern Du wenigstens diesen kennst.

[DominikJ]

Hey,

also Teilabscnhitte sind bei mir halt weiter Punkte.

Für diese wird der hier beschriebene Schritt ausgeführt.

Das heisst bei 3 anzufahrenden Punkten wäre das die Suche nach anderen Punkten nahe StreckeAB sowie Punkte nahe StreckeBC.

Andere Teilabschnitte gibt es wie gesagt nicht.

Auch ein Beispiel von Hannover -> Berlin wird in der Realität nicht verwendet werden, da dies auch 2 verschiedene Gebiete sind.

Gruß Dominik