Wie kann man feststellen, ob sich 2 Strahlen schneiden?
Wir erhalten die 2D-Koordinaten von 2 Punkten: Der erste Punkt ist der Punkt, an dem der Strahl beginnt und durch den zweiten Punkt geht. Auf die gleiche Weise erhalten wir einen weiteren Strahl. Wie bestimmen wir, ob sie einen Schnittpunkt haben? Ich würde gerne den allgemeinen Algorithmus und seine Erklärung kennen, ohne Rücksicht auf die Extremfälle (z. B. wenn die Strahlen den gleichen Ausgangspunkt haben). PS Ich habe eine ähnliche Frage bei einem anderen Stapelaustausch gesehen, aber die Antworten wurden nicht durch Erklärungen gestützt.
Antworten
Ich bin mir nicht sicher, ob es Ihre Frage beantwortet, aber hier ist etwas, das ich vor einigen Jahren für eine Arbeit geschrieben habe.
Lassen $\mathbf{p}_0$ und $\mathbf{p}_1$ seien Sie die Endpunkte des ersten Segments und lassen Sie $\mathbf{q}_0$ und $\mathbf{q}_1$seien Sie die Endpunkte des zweiten Segments. Dann sind die parametrischen Gleichungen der beiden Linien$$ \mathbf{p}(t_p) = (1 - t_p) \mathbf{p}_0 + t_p \mathbf{p}_1 \quad \text{and}\quad \mathbf{q}(t_q) = (1 - t_q) \mathbf{q}_0 + t_q \mathbf{q}_1 \,. $$ Am Schnittpunkt $\mathbf{p} = \mathbf{q}$dh $$ (1 - t_p) \mathbf{p}_0 + t_p \mathbf{p}_1 = (1 - t_q) \mathbf{q}_0 + t_q \mathbf{q}_1 \,. $$ Neuordnung der Gleichung ergibt $$ \mathbf{q}_0 - \mathbf{p}_0 = \begin{bmatrix}\mathbf{p}_1 - \mathbf{p}_0 & -(\mathbf{q}_1 - \mathbf{q}_0)\end{bmatrix} \begin{bmatrix} t_p \\ t_q \end{bmatrix} \,. $$ Deshalb, $$ \begin{bmatrix} t_p \\ t_q \end{bmatrix} = \begin{bmatrix}\mathbf{p}_1 - \mathbf{p}_0 & -(\mathbf{q}_1 - \mathbf{q}_0)\end{bmatrix}^{-1} (\mathbf{q}_0 - \mathbf{p}_0) $$ Sobald wir für gelöst haben $t_p$ und $t_q$wir können den Schnittpunkt leicht finden. Wenn der Schnittpunkt außerhalb von liegt$\mathbf{p}$ Linie dann $t_p \notin [0, 1]$. In ähnlicher Weise gilt für das andere Segment, wenn der Schnittpunkt außerhalb des Segments liegt,$t_q \notin [0, 1]$.
Da sich zwei nicht parallele Linien irgendwo schneiden müssen (laut Euklid), stelle ich mir vor, dass das OP eine etwas andere Frage beabsichtigte. Schneiden sich die Strahlen beispielsweise innerhalb der konvexen Hülle der vier gegebenen (wirklich implizierten) Punkte? (Die konvexe Hülle ist der Bereich, der von einem Gummiband umschlossen ist, das um alle vier Punkte gespannt ist, ohne sich zu kreuzen.) Dies ist das von Biswajit Banerjee gelöste Problem. Sie müssen wissen, wo sich die Kreuzung befindet.
Wenn Sie nur wissen müssen, ob sich die Strahlen schneiden, müssen Sie den Schnittpunkt nicht finden. Das Folgende kann stabiler und effizienter sein als das Lösen der Gleichungen für den Schnittpunkt, da es nur Subtraktions- und Punktprodukte ohne Division umfasst.
Du hast deinen ersten Strahl ab $p_0$ und in Richtung gehen $p_1$ (und unendlich darüber hinaus $p_1$) und dein zweiter Strahl beginnt bei $q_0$ und in Richtung gehen $q_1$ (und unendlich darüber hinaus $q_1$). Denken Sie visuell darüber nach. Für eine feste$p_0$, $p_1$, und $q_0$, welche Werte von $q_1$zu einer Kreuzung führen? Die Antwort ist das$q_1$muss in einem keilförmigen Bereich der Ebene liegen. Eine Seite des Keils ist die Linie zwischen$q_0$ und $p_0$und die andere Seite des Keils ist parallel zum ersten Strahl. Im Diagramm$q_1$ muss sich im blauen Bereich befinden, damit sich die Strahlen schneiden.
Wir können eine Seite des Keils ausdrücken, indem wir das sagen $q_1$ muss auf der gleichen Seite sein $q_0$ zu $p_0$ Linie als $p_1$ist. Wenn$p_0 - q_0 = (l_x, l_y)$, dann können wir drehen $(l_x, l_y)$ 90 Grad, um einen Vektor senkrecht zur Linie zu erhalten: $(-l_y, l_x)$. Dann, um das zu überprüfen$q_1$ und $p_1$ sind auf der gleichen Seite, wir überprüfen das $(q_1 - q_0) \cdot (-l_y, l_x)$ hat das gleiche Vorzeichen wie $(p_1 - q_0) \cdot (-l_y, l_x)$.
Wir können die andere Seite des Keils ausdrücken, indem wir auf die Linie schauen, die durch sie verläuft $q_0$ und $q_0 + (p_1 - p_0)$. $q_1$ und $p_1$muss auf der gleichen Seite dieser Linie sein. Ein Vektor parallel zur Linie ist$p_1 - p_0 = (m_x, m_y)$ die wir um 90 Grad drehen, um zu bekommen $(-m_y, m_x)$. Um das zu überprüfen$q_1$ und $p_1$ sind auf der gleichen Seite dieser Linie, wir überprüfen das $(p_1 - q_0) \cdot (-m_y, m_x)$ hat das gleiche Vorzeichen wie $(q_1 - q_0) \cdot (-m_y, m_x)$.
Zusammenfassend lässt sich sagen, dass sich die beiden Strahlen genau dann schneiden, wenn $(q_1 - q_0) \cdot (-l_y, l_x)$ hat das gleiche Vorzeichen wie $(p_1 - q_0) \cdot (-l_y, l_x)$, und $(p_1 - q_0) \cdot (-m_y, m_x)$ hat das gleiche Vorzeichen wie $(q_1 - q_0) \cdot (-m_y, m_x)$.