Den Schnittpunkt zweier Strecken berechnen

[jfheins]

Ich habe zwei linien, beschrieben durch ax1, ay1, ax2, ay2 bzw. bx1, by1, bx2, by2 ...

sie gehen immer von 1(x1|y1) nach 2 (x2|y2)

Nun brächte ich die Info:

-Gibt es einen Schnittpunkt?

-Wenn ja, wo?

Ich habe beim SDC einen Code gefunden, der den Schnittpunkt berechnet, aber der Schnittpunkt dort kann auch ausserhalb der Linien liegen - bei mir darf er das nicht.

(Wenn die Linien also nicht parallel sind, heisst das noch lange nicht, dass es einen Schnittpunkt gibt ...)

Oder mathematisch: Der SDC berechnet den Schnittpunkt zweier Geraden, ich brauche aber den Schnittpunkt zweier Strecken ;)

Ach ja, performant sollte es auch noch sein ...

Danke schonmal ;)

[Alien426]

Eine Suche im Forum hilft mir bei den meisten meiner Delphi-Probleme.

Schnittpunkt zweier Strecken sollte dir helfen.

[jfheins]

Soweit ich das sehen kann, sind sie auch da nicht zu einer guten Lösung gekommen ...

Was ich gerne vermeiden würde ist das "Geradengleichung herausfinden, schnittpunkt herausfinden, gucken ob er auf der strecke liegt" weil ich z.B.

- u.u. waagerechte und senkrechte strecken habe

- den schnittpunkt berechne und dann sehe, dass er mich doch nichts bringt

- zuviel rechnerei ...

gibt es da kein kurzes verfahren ?

[BlackJack]

du behandelst beide strecken erstmal als geraden und rechnest den schnittpunkt aus. dann rechnest du für jede strecke aus, wie weit die beiden endpunkte auseinander liegen, und rechnest den abstand des schnittpunktes zu beiden punkten aus. wenn der Abstand Schnittpunkt/Endpunkt für alle Endpunkte kleiner als die jeweilige streckenlänge ist, dann liegt der schnittpunkt auf der strecke.
das wäre das erste was mir einfält, es geht sicher noch besser (ich hätte es z.b. direkt mit vektoren gemacht, aber ich weiss ja nicht wie weit du da so bewandert bist).

ach ja, da es ja nur um die relativen abstände geht, kannst du auch die quadrierten abstände betrachten, d.h. du kannst dir bei der Abstandsberechnung die Wurzel schenken (die ja der Pythagoras sonst mitgebracht hätte).

und den schnittpunkt wirst du so oder so berechnen müssen; aber das ist ja auch kein thema, das kannst du ja direkt alles in eine formel reinstecken.

[runger]

Hallo,

Geradengleichungen aufstellen,P(x0,y0),Q(x1,y1)
Schnittpunkt berechnen, S(xs,ys)
dann wenn gilt:
wenn x0<x1 --> x0<=xs<=x1 dann liegt Schnittpunkt vor
wenn x0>x1 --> x1<=xs<=x0 dann liegt Schnittpunkt vor

Nur für deckungsgleiche geraden und senkrechte musst du eine Sonderbehandlung vorsehen.
Die Berechnung dieser Dinge ist so einfach, dass ich mir das spare.

Rainer

[alzaimar]

Du kannst auch vor der Geradengleichung testen, ob es einen Schnittpunkt geben könnte, indem Du Dir einfach mal anschaust, unter welchen Bedingungen sich zwei Strecken überhaupt schneiden. Eine Strecke (P1-P2) hat ja ein umhüllendes Rechteck. Wenn sich diese Rechtecke gar nicht überlappen, gibts auch keinen Schnittpunkt. Damit könnstest Du viele Tests erstmal erschlagen.

Weiterhin kannst Du die Strecken in Quadranten unterteilen und nur die Strecken in Betracht ziehen, die in unmittelbarer Nachbarschaft des Quadranten der Strecke liegen, die Du prüfen willst. Wenn Du diese Quadranten dann noch indizierst, also eine sortierte Liste erstellst, musst Du aus den Abermillionen Strecken wirklich nur noch ein paar testen...

[jfheins]

Zitat:

Zitat von BlackJack

es geht sicher noch besser (ich hätte es z.b. direkt mit vektoren gemacht, aber ich weiss ja nicht wie weit du da so bewandert bist).

Das besser würde mich interessieren ;)
(Vektoren sind da jetzt auch kein Problem mehr)

[kalmi01]

kuckst Du hier
Bei ausreichendem Englisch solltest Du dort alles finden, was Dein Herz in Sachen Geometrie begehrt.

[runger]

Hallo,

es geht noch einfacher:
die Wertebereiche der x Werte müssen sich überdecken!
So kannst du entscheiden ob es überhaupt einen Schnittpunkt geben kann.

Rainer

[alzaimar]

Zitat:

Zitat von alzaimar

... Eine Strecke (P1-P2) hat ja ein umhüllendes Rechteck. Wenn sich diese Rechtecke gar nicht überlappen, gibts auch keinen Schnittpunkt. Damit könnstest Du viele Tests erstmal erschlagen. ...

Zitat:

Zitat von runger

...es geht noch einfacher:
die Wertebereiche der x Werte müssen sich überdecken!
So kannst du entscheiden ob es überhaupt einen Schnittpunkt geben kann.
Rainer

Sach ich doch. :zwinker:

[dizzy]

So wie hier mach ich es immer. Beachte den letzten Tip. Bei dir müssen ua und ub im Bereich 0..1 liegen, damit der Schnittpunkt auf beiden Strecken liegt.

\\edit: Der Tipp von runger ist übrigends hervorragend zum Performance sparen. Die Prüfung kann - wenn für x positiv verlaufen - noch für y gemacht werden. Dann ist es rech wahrscheinlich dass die Strecken sich schneiden.

[alzaimar]

Zitat:

Zitat von dizzy

\\edit: Der Tipp von runger ist übrigends hervorragend zum Performance sparen. Die Prüfung kann - wenn für x positiv verlaufen - noch für y gemacht werden. Dann ist es rech wahrscheinlich dass die Strecken sich schneiden.

Zitat:

Zitat von alzaimar

... Eine Strecke (P1-P2) hat ja ein umhüllendes Rechteck. Wenn sich diese Rechtecke gar nicht überlappen, gibts auch keinen Schnittpunkt. Damit könnstest Du viele Tests erstmal erschlagen. ...

Ich bin selten so missachtet worden :cry:

[dizzy]

Zitat:

Zitat von alzaimar

Ich bin selten so missachtet worden :cry:

:shock: schulligung... dein Posting war im Gegensatz zu rungers nicht im Bild als ich das schrieb. Keine Absicht :angel2:

[jfheins]

Ok ... ich prüfe gerade mal einen Ansatz mit Vektoren, aber sonst mache ich es so ...

[dizzy]

Da gibts kein entweder-oder ;). Die Variante mit der Box-Überlappung ist lediglich zur schnellen Vorentscheidung, ob du überhaupt einen Schnittpunkt errechnen musst. Das kann man machen um die Performance zu steigern. Bei der eigentlichen Berechnung des Schnittpunktes kommst du ohnehin dahinter, ob es einen gibt oder nicht. Ist halt nur kostspieliger, da du bereits den potentiellen Punkt errechnest.

[jfheins]

Ok, die Box-Überlappung kommt noch ...

Ich habe jetzt eine kleine Demo gemacht mit meinem Vektoren-Algo, das geht jetzt über den Sinussatz und Skalarprodukt :mrgreen:

Die Demo ist angehängt, ich würde mich freuen, wenn ihr ein paar Linien ziehen würdet und dann schaut, ob der Algo funktioniert ;)

Einfach im linken Fensterbereich zwei Linien durch klicken und ziehen malen und dann auf den Button klicken ;)

(Im Memo steht der Code ... falls ihn jemand will ^^)

Falls die Strecken sich überschneiden sollte eine Messagebox mit "intersecting" kommen ... ;)

Falls ihr einen deutlichen (= nicht im Pixelbereich) Fehler habt, dann bitte die Position der zwei Linien posten ...
(Wehe :twisted: )

Neue Demoi zeigt auch den Schnittpunkt an ...

[BlackJack]

hmm also wenn schon ein sinus drin vorkommt dann kann der ansatz ja nur langsam sein. warum setzt du nicht den Ansatz von rugner um, der kommt doch mit den grundrechenarten aus. und wenn du dann noch dann noch die linien wie alzaimar vorgeschlagen hat in einer Art kdTree oder Quadtree speicherst dann wird das ganze richtig, richtig schnell.

edit:
bei Wikipeda hast du es sogar schwarz auf weiss: "- Effiziente Kollisionserkennung (Collision Detection) im Zweidimensionalen" ;)