Den Schnittpunkt zweier Strecken berechnen

[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" ;)