Den Schnittpunkt zweier Strecken berechnen

[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...