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: