Hi! Vielleicht hat jemand schon mal sowas gemacht und ich kann etwas Zeit und Nerven sparen bevor ich selbst lange Überlegungen anstelle wie das am schnellsten geht. Gegeben sind die Koordinaten zweier Punkte A und B, die mit einer geraden Strecke verbunden sind. 1. Wie krieg ich am schnellsten raus, ob sich ein weiterer Punkt C auf dieser Strecke befindet? 2. Wie krieg ich am schnellsten raus, ob diese Strecke von einer weiteren Strecke zwischen zwei Punkten C und D geschnitten wird? Wenn jemand was weiß, danke schonmal!
Man definiert die Strecken als Geraden und dann als lineare Funktion y=a*x+b, (a=Steigung, b=Verschiebung/Konstante), Anfangs- und Endpunkt bilden den Wertebereich. Um den Kreuzungspunkt zu finden, setzt man beide Gleichungen gleich, d.h. wenn es einen Kreuzungspunkt gibt, gehört der (innerhalb beider Werteberiche) zur Ergebnismenge beider Gleichungen ...
Mein Ansatz wäre ganz simpel nach dem Matheunterricht der 7. Klasse. Die paar Rechnungen sollte ein µC/PC im Schlaf machen. 1. lin. Funktionsgleichung y=m*x+t aufstellen und C einsetzen. Zusätzlich noch prüfen, ob x_C zwischen x_A und x_B liegt. Die Formeln für m und t findest Du in Deinem Matheheft;-) 2. beide Funktionsgleichungen (y1 und y2) aufstellen, gleichsetzen (y1 = y2) und ebenfalls prüfen, ob das somit ermittelte x zwischen x_A und x_B liegt. <edit> Mist, zu langsam... </edit>
zu 1) Das dürfte sich in zwei Schritte Gliedern. Als erstes setzt du von deinem Punkt die X-Koordinate in die Gradengleichung ein. Im zweiten Schritt vergleichst du das resultierende Y mit der Y-Koordinate des Punktes. Sind sie "gleich" (Achtung: Float und Co nie auf Gleichheit prüfen sondern ein Toleranzband definieren) liegt der Punkt auf der Graden, ansonsten liegt er daneben. zu 2) Ähnlich wie 1). Schnittpunkt berechnen und prüfen wo er auf der Graden liegt. Eigentlich Grundlagen der Geometrie. Wo genau liegt dein Problem?
>Wo genau liegt dein Problem?
Wahrscheinlich in der temporären Faulheit.
>1. Wie krieg ich am schnellsten raus, ob sich ein weiterer Punkt C auf >dieser Strecke befindet? überhaupt nicht! du kannst nur ausrechnen wie weit er weg ist.. und definieren ab welchem Abstand (z.b. 0,000000001) das als "auf der Linie" gilt...
PS. Die Geradengleichung y = kx + d ist so nicht so prächtig dafür geeignet, weil sie einen Sonderfall hat, nämlich eine 'senkrechte' und dann wird das k unendlich. Aber die Normel-Form a*x + b*y + c = 0 eignet sich wunderbar. und hat auch keine Sonderfälle. Hast du erst mal a, b, c bestimmt, dann setzt du x bzw. y vom Punkt ein. Die Gleichung liefert dir unmittelbar den Abstand des Punktes von der Geraden. Ist der 0 bzw. nahezu 0, dann liegt der Punkt auf der Geraden. http://de.wikipedia.org/wiki/Geradengleichung#Normalform
>Gegeben sind die Koordinaten zweier Punkte A und B, die mit einer >geraden Strecke verbunden sind. Ok. A = ( xa ya ) B = ( xb yb ) >1. Wie krieg ich am schnellsten raus, ob sich ein weiterer Punkt C auf >dieser Strecke befindet? C = ( xc yc ) Die Strecke beschreibst Du so: x xa dx ( ) = ( ) + N *( )* t y ya dy dx = xa - xb dy = ya - yb N = 1/SQRT( dx^2 + dy^2 ) t ist deine Laufvariable. N normiert die Laufvariable auf dieselbe Einheit wie das Koordinatensystem.N kannst Du auch weglassen. Wenn C auf der Strecke liegt, muss gelten: xc ( ) = ... yc Du bekommst zwei Gleichungen mit der Unbekannten t. Wenn t bei beiden identisch ist, liegt C auf der Strecke. >2. Wie krieg ich am schnellsten raus, ob diese Strecke von einer >weiteren Strecke zwischen zwei Punkten C und D geschnitten wird? Wenn es nur darum geht, ob sich die Strecken schneiden (nicht wo), dann reicht es, zu Prüfen, ob diese nicht parallel sind. Das geht über den Anstieg. Oben mit dx und dy bezeichnet: dx1 = xa - xb & dx2 = xc - xd dy1 = ya - yb & dy2 = yc - yd müssen unterschiedlich sein. Wenn der Schnittpunkt auch interessiert: In die Gleichungen einsetzen. Es entstehen vier Gleichungen mit vier Unbekannten.
Da muss ich doch mal ganz blöd fragen: Bezieht sich die Fragestellung auf den 2-Dimensionalen oder den 3-Dimensionalen Raum? Bei 3D musst Du hier vermutlich mit Vektorrechnung arbeiten. Gruß, Kamikater
Kamikater schrieb: > Da muss ich doch mal ganz blöd fragen: > > Bezieht sich die Fragestellung auf den 2-Dimensionalen oder den > 3-Dimensionalen Raum? Wahrscheinlich 2D > Bei 3D musst Du hier vermutlich mit Vektorrechnung arbeiten. Es ist auch im 2D am einfachsten mit Vektoren an die Sache ranzugehen. Ganz im Gegenteil: wer 2D Geometrie mit sin/cos angeht, hat meistens schon verloren. Die Genauigkeit, die Geschwindigkeit ist Scheisse und komplizierter ist es meistens auch. (die Geradengleichung y = k*x+d lebt davon, dass k im Prinzip der Tangens der Steigung ist. Mit allen Problem: in der Nähe von 90° wächst er rasend schnell um bei 90° ins Unendliche zu gehen - nicht zu gebrauchen). Man muss sich nur auf Vektoren erst mal einlassen. Kreuzprodukt, Skalarprodukt und was sie geometrisch bedeuten, dazu noch ein paar Basisformeln wie zb Gramm-Schmidt und schon verliert das alles seinen Schrecken. Und nebenbei: Auch wenn die Formeln kompliziert aussehen, die sich ergebende Mathe ist meist ganz simpel.
Folgendes sollte recht schnell zu berechnen sein, da keine Divisionen und erst recht keine Wurzeln oder Winkelfunktionen verwendet werden:
1 | def c_liegt_auf_ab(xa, ya, xb, yb, xc, yc): |
2 | # C wird als auf A liegend angesehen, wenn der Abstand von C zu AB |
3 | # maximal |AB|·eps ist. |
4 | |
5 | eps = 1e-6 |
6 | |
7 | dxb = xb - xa |
8 | dyb = yb - ya |
9 | dxc = xc - xa |
10 | dyc = yc - ya |
11 | |
12 | # s2 ist |AB|² |
13 | s2 = dxb*dxb + dyb*dyb |
14 | |
15 | # u/|AB| ist der Abstand von C zu A in Richtung von AB. |
16 | u = dxb*dxc + dyb*dyc |
17 | |
18 | # v/|AB| ist der Abstand von C zu AB. |
19 | v = dxb*dyc - dxc*dyb |
20 | |
21 | # u/|AB| muss im Bereich 0..|AB| und v/|AB| im Bereich ±eps·|AB| liegen. |
22 | return 0 <= u <= s2 and abs(v) <= eps*s2 |
23 | |
24 | |
25 | def ab_schneidet_cd(xa, ya, xb, yb, xc, yc, xd, yd): |
26 | def ccw(x1, y1, x2, y2, x3, y3): |
27 | # ccw liefert einen Wert |
28 | # > 0, wenn P1, P2 und P3 im Gegenuhrzeigersinn liegen |
29 | # = 0, wenn P1, P2 und P3 auf einer Geraden liegen |
30 | # < 0, wenn P1, P2 und P3 im Uhrzeigersinn liegen |
31 | return (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1) |
32 | |
33 | ca = ccw(xa, ya, xc, yc, xd, yd) |
34 | cb = ccw(xb, yb, xc, yc, xd, yd) |
35 | cc = ccw(xc, yc, xa, ya, xb, yb) |
36 | cd = ccw(xd, yd, xa, ya, xb, yb) |
37 | |
38 | # ca und cb müssen unterschiedliche Vorzeichen haben, oder eins von |
39 | # beiden muss gleich 0 sein. Entsprechendes muss für cc und cd gelten. |
40 | # Unter Verwendung von Multiplikationen lässt sich die Anzahl der |
41 | # erforderlichen Vergleiche stark reduzieren, was für PC-Prozessoren |
42 | # vorteilhaft ist. |
43 | return ca*cb <= 0 and cc*cd <= 0 |
Vorsicht: Das Ganze habe habe ich gerade erst hingeschrieben und nur mit wenigen Beispielen getestet. Evtl. sind also noch kleinere Fehler drin. Die prinzipiellen Ansätze sollten aber richtig sein.
Yalu X. schrieb: > Folgendes Nett -- werde ich mir mal bookmarken. Wobei ersteres ja auch von http://www.geometrictools.com/ Beitrag "Re: Fangfunktion" abgedeckt wird.
Ich würde das so machen: Seien a, b, c die Ortsvektoren der Punkte A, B, C. Dann befindet sich C auf der Geraden durch a und b, wenn (a-b) und (a-c) linear abhängig sind. Das ist genau dann der Fall, wenn das Kreuzprodukt der beiden null ist.
Sven B. schrieb: > Dann befindet sich C auf der Geraden durch a und b, Ich denke es ging hier eher um eine Strecke.
Ja, dann ist noch ein zusätzlicher Schritt nötig. Das ist aber eine einfache "Ist x in einem Rechteck"-Überprüfung, die keine Schwierigkeiten machen sollte. ;)
Die Geschwindigkeit ist mein Kriterium, nicht die Machbarkeit. Danke euch für eure Antworten!
Yalu X. schrieb: > Folgendes sollte recht schnell zu berechnen sein, Autor: Salewski, Stefan (Gast) schrieb am Datum: 26.02.2013 18:06 >Nett -- werde ich mir mal bookmarken. Deine Mühen in allen Ehren, aber ich werde wohl doch den Code von http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect genauer gesagt den C Code von iMalc http://stackoverflow.com/posts/14795484/revisions verwenden. Scheint in meiner Ruby-Version soweit zu funktionieren und ist wohl recht optimal. Leider gibt vom gleichen Autor davon auch eine fehlerhafte Version auf http://cboard.cprogramming.com/c-programming/154196-check-if-two-line-segments-intersect.html die ich dummerweise zuerst probiert hatte.
Hallo Karl Heinz Buchegger. > > Aber die Normal-Form > > a*x + b*y + c = 0 > > eignet sich wunderbar. und hat auch keine Sonderfälle. Hast du erst mal > a, b, c bestimmt, dann setzt du x bzw. y vom Punkt ein. Die Gleichung > liefert dir unmittelbar den Abstand des Punktes von der Geraden. Ist der > 0 bzw. nahezu 0, dann liegt der Punkt auf der Geraden. > > http://de.wikipedia.org/wiki/Geradengleichung#Normalform In dem Zusammenhang die Hesse-Normalform nicht vergessen. Manchmal ist die noch handlicher. http://de.wikipedia.org/wiki/Hesse-Normalform Mit freundlichem Gruß: Bernd Wiebus alias dl1eic http://www.dl0dg.de
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.