Schneiden sich 2 Strecken?

[Florian H]

Hi,

wie kann ich herausfinden (mathematisch), ob sich 2 Strecken schneiden?

Ich habe die Koordinaten der Endpunkte.

grüße
flo

[Mirilin]

:hi:

z.B. die Geraden legen und schauen, ob die sich schneiden :)


mfg Tobias

[DelphiFreund]

Gleichsetzen, wenn die Gleichnung keine Lösun ghat, schneiden sie sich, wenn sie sich schneiden hast du auch gleich den Schnittpunkt.

Gruß DelphiFreund

[Robert Marquardt]

Das Intervall [X1min, X1max] muss sich mit dem Intervall [X2min, X2max] ueberschneiden *und* das selbe fuer die beiden Y-Intervalle.

[Florian H]

ok danke!

[Nikolas]

@ Delphifreund:
Achtung: Es geht um Strecken und nicht um Geraden !!

@ Robert:
Siehe Anhang, Ich glaub, der Ansatz geht nicht. (Blau sind die Intervalle [x.min-xmax] , rot entsprechend mit y)

[Robert Marquardt]

Hast recht. War auch nur ein Schnellschuss.
Ist also eine notwendige, aber nicht hinreichende Bedingung.

[DelphiFreund]

@Toxman: Das spielt keine Rolle, er braucht doch dann nur noch prüfen, ob der Schnittpunkt im richtigen Bereich liegt.

Gruß DelphiFreund

[rantanplan99]

Also, des wird jetzt länger *g*

Gegeben:
(x11,y11) und (x12,y12) die Anfangs- und Endpunkte deiner ersten Strecke
(x21,y21) und (x22,y22) die Anfangs- und Endpunkte deiner zweiten Strecken

Gesucht:
die Koordinaten (x,y) des Schnittpunkts P

Lösung:
Wir erweitern die Strecken zu geraden, und berechnen den Schnittpunkt der zwei Geraden
Zunächst brauchen wir die Steigung der 2 Geraden

m1 = (x11-x12)/(y11-y12) oder wenn wir es vom Schnittpunkt P aus berechnen
m1 = (x-x12)/(y-y12) (*2*)
Selbes für m2
m2 = (y21-y22)/(x21-x22) bzw.
m2 = (y-y22)/(x-x22) (*1*)

Dann stellen wir dir Formeln (*1*) und (*2*) wie folgt um:
m1 * (y-y12) + x12 = x (*3*)
m2 * (x-x22) + y22 = y (*4*)

Jetzt setzen wir y aus (*4*) ind Gleichung (*3*) ein:
m1 * ((m2 * (x-x22) + y22)-y12) + x12 = x (*5*)

Dann lösen wir Gleichung (*5*) nach x auf:
(Rechenweg spare ich mir)
x = (m1 * (m2*x22 - y22 + y12) - x12) / (m1*m2 - 1)

Und dann kannst du y ausrechnen, indem du x in Gleichung (*4*) einsetzt

So jetzt hast du den Schnittpunkt der 2 Geraden, und jetzt musst du folgende Bedingung prüfen:

Ein Strecke ist ja die Diagonale eines Rechtecks. Wenn der Schnittpunkt NICHT innerhalb BEIDER Rechtecke (das von der ersten Strecke UND dem der zweiten Strecke), dann schneiden sich wohl die Geraden, aber NICHT die Strecken.

Ok, nun zu den Einschränken die du am besten vorher abfangen musst:
1) Sind die Steigungen der Strecken/Geraden gleich, dann sind sie parallel, und haben keinen Schnittpunkt, oder sie liegen aufeinander und haben unendlich viele Schnittpunkte

2) Falls eine der Strecken parallel zur x-Achse ist, bekommst du bei der Berechnung der Steigung einen Division by Zero Fehler. Wäre günstig wenn du den Abfangen würdest und dir für diesen Sonderfall eine andere Schnittpunkt bestimmung machst.

Dann mal viel Spass dabei

[dizzy]

@delphifreund: Was allerdings nicht so einfach ist, und zu dem reichlich wenig performat. (Ich weiss zufällig, dass es hier um ein Spiel geht, gelle!? ;))

Ich schau mal, was meine Bücher so dazu sagen...