[Mathe] Entfernung Punkt zu Teilgerade

[Bububoomt]

Ich will wissen ob ein Punkt Q in einem Radius r einer Strecke ( PX) liegt.

Habe durch diese Seite
https://www.matheraum.de/forum/Entfernung_P_zu_Teilgeraden/t115615?v=t
schon mal den Abstand zu der Geraden.

(|(vq-vp) x (vx-vp)|) / (|(vx-vp)|)


Aber nun weiß ich noch nicht ob der Lotpunkt Q' innerhalb der Strecke PX liegt.

Auf der Seite ist zwar ein Ansatz, aber ich weiß nciht wie ich das machen muß. Vorallem ich brauche es für ein Programm.

Die Strecke berechne ich nun so:
((Qx-Px)*(Xy-Py) - (Qy-Py)*(Xx-Px)) / Wurzel( (Xx-Px)²+(Xy-Py)² )

Ich habe zwar einige Bedingungen, aber scheinbar stimmen die nicht.

 

[DaPhreak]

Aber nun weiß ich noch nicht ob der Lotpunkt Q' innerhalb der Strecke PX liegt.

Dafür hätte ich 'nen Ansatz. Und zwar so:

Alle Punkte auf der Strecke PX sind beschrieben durch:

für

, wobei

der Vektor zum Punkt X und

der Vektor zum Punkt P ist.

Jetzt musst Du nur das t berechnen, was genau dem Lotfußpunkt von Q auf die Gerade entspricht... ist es im Intervall [0,1] dann liegt der Lotfußpunkt innerhalb der Strecke.

Das geht z.B. so: Der Vektor vom Punkt Q zu

ist gegeben durch

. Bedingung an den Lotfußpunkt ist, dass dieser Vektor senkrecht zum Richtungsvektor der Geraden

ist.


Das ist dann erfüllt, wenn das Skalarprodukt null wird. Ich schreib das Skalarprodukt mal mit

(das bedeutet also ax*bx+ay*by):

ausmultiplizieren:

und damit die Lösung für t:

Plausibilitätsprüfung: wenn man für den variablen Punkt

einfach mal

einsetzt kommt 0 raus, bei

kommt 1 raus... scheint zu passen.

Obacht, die Lösung ist noch nicht vollständig.

* Wenn t in [0,1] ist, liegt der Lotfußpunkt innerhalb der Strecke.
* Damit hast Du den kürzesten Abstand zur Strecke. Ist dieser kleinergleich r, dann weißt Du das es passt, ist er größer, weißt Du das es nicht passt.
* Wenn der Lotfußpunkt außerhalb der Strecke liegt und das Lot länger als r ist, weißt Du auch, dass es nicht passt.
* Aber: Wenn der Lotfußpunkt außerhalb der Strecke liegt und das Lot kürzer als r ist, kann es trotzdm noch einen Punkt innerhalb der Strecke geben, der dicht genug dran ist. In dem Falle musst Du zusätzlich noch die Randpunkte P und X selbst prüfen!



*edit* Mal noch ein Bild um meinen letzten Punkt zu verdeutlichen:



In dem Beispiel liegt der Lotfußpunkt außerhalb der Gerade, aber da der Fußpunkt trotzdem wesentlich dichter an Q ist als r (siehe roter Kreis) ist die Strecke schon noch innerhalb des Radius. In dem Fall hätte man den Randpunkt P noch geprüft (t war negativ) und da er innerhalb des Kreises ist (also dichter als r) insgesamt trotzdem entschieden, dass der Punkt dicht genug an der Strecke ist.

 

[Bububoomt]

Hi,

danke dass werde ich gleich mal versuchen umzusetzen im Programm.

*edit*
das wohl genau der fall, den ich nicht berücksichtigt hatte. entfernung zu p und x, nur wenns auf der Gerden ist, also d=0 ist.

 

[Bububoomt]

Also entweder ich kann nicht rechnen der de darstellung in meinem Programm ist fehlerhaft.

Punkt 1.000.000,1.000.000

Geraden Punkte
980.000,1.100.000 und
970.000,1.090.000

liegt der im Radius von 100.000 ???
wäre doch 30.000²+90.000²<=100.000²
900000000+8100000000=9000000000
<=10000000000

somit ist der eine Punkt der Geraden ja innerhalb des radius oder bin ich nun voll daneben!?

 

[DaPhreak]

Korrekt, für Deine Werte liegt es innerhalb.

Für das t habe ich 4 bekommen, also liegt der Lotfußpunkt außerhalb der Gerade. Damit muss man die Randpunkte prüfen.

Distanz von Q zu P: 101'980,3 (etwas größer als 100'000).
Distanz von Q zu X: 94'868.3 (etwas kleiner als 100'000).

Damit liegt der Punkt nah genug dran.

Zur Probe: Distanz von Q zu X ist Wurzel(30'000[sup]2[/sup]+90000[sup]2[/sup]) = Wurzel(9*10[sup]9[/sup]) = 3*10[sup]4.5[/sup] und das ist etwa gleich 94'868,3.


Falls das mit dem Programm nicht hingehauen hat: Sind Dir eventuell die Werbebereiche übergelaufen? Wenn du 32 Bit Integers genommen hast funktionieren die nur bis 4294967296 oder 4.29*10[sup]9[/sup]. Hier kam mit 9*10[sup]9[/sup] eine Zahl vor die größer war. Da musst Du entweder 64 Bit Integers nehmen oder auf einen Fließkommadatentyp ausweichen.

Alternativ kannst Du auch alles mal durch 1000 teilen, die vielen Nullen brauchst Du doch gar nicht.

 

[Bububoomt]

Hi, also ein Überlaufproblem hatte ich, weilich zunächst unsigned in der db hatte, da habe ich für 900.000-920.000 nich -20.000 sonder irgendwas wie 146589393939 oder so bekommen. Das Problem habe ich gefixt indem ichs wieder geändert habe in normalen Int.

Also er hat mir ie Gerade als in der nähe genommen.

Ich zeichne die ganzen Linien. Wenn ich die Suche dann mache wird ein Kreis (umkreis) gezeichnet und die gefundenen linien werden gefärbt.

Somit ist also meine Zeichenroutine fehlerhaft. Ist wohl nen rundungsfehler.

Danke...