Bagaimana cara menentukan apakah 2 sinar berpotongan?
Kami diberi koordinat 2D dari 2 titik: titik pertama adalah tempat sinar dimulai dan melewati titik kedua. Kami diberi sinar lain dengan cara yang sama. Bagaimana kita menentukan apakah mereka memiliki titik perpotongan? Saya ingin mengetahui algoritma umum dan penjelasannya, tidak mempermasalahkan kasus-kasus ekstrim (misalnya ketika sinar memiliki titik awal yang sama). PS Saya melihat pertanyaan serupa di stack exchange lain, tetapi jawabannya tidak didukung oleh penjelasan.
Jawaban
Tidak yakin apakah itu menjawab pertanyaan Anda, tetapi ini adalah sesuatu yang saya tulis beberapa tahun yang lalu untuk sebuah makalah.
Membiarkan $\mathbf{p}_0$ dan $\mathbf{p}_1$ menjadi titik akhir dari segmen pertama dan biarkan $\mathbf{q}_0$ dan $\mathbf{q}_1$menjadi titik akhir dari segmen kedua. Maka persamaan parametrik dari kedua garis tersebut adalah$$ \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 \,. $$ Di titik persimpangan, $\mathbf{p} = \mathbf{q}$, yaitu, $$ (1 - t_p) \mathbf{p}_0 + t_p \mathbf{p}_1 = (1 - t_q) \mathbf{q}_0 + t_q \mathbf{q}_1 \,. $$ Penyusunan ulang persamaan memberi $$ \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} \,. $$ Karena itu, $$ \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) $$ Setelah kami memecahkan $t_p$ dan $t_q$kita dapat menemukan titik perpotongan dengan mudah. Jika titik potong berada di luar$\mathbf{p}$ baris kemudian $t_p \notin [0, 1]$. Begitu pula untuk ruas lainnya, jika titik potongnya berada di luar ruas tersebut, maka$t_q \notin [0, 1]$.
Karena dua garis non-paralel harus berpotongan di suatu tempat (menurut Euclid) saya membayangkan bahwa OP bermaksud pertanyaan yang sedikit berbeda. Misalnya, apakah sinar berpotongan di dalam lambung cembung dari empat titik yang diberikan (sebenarnya, tersirat)? (convex hull adalah daerah yang dikelilingi oleh karet gelang yang diregangkan mengelilingi keempat titik tanpa bersilangan.) Itulah masalah yang dipecahkan oleh Biswajit Banerjee. Anda perlu tahu di mana letak persimpangannya.
Jika Anda hanya perlu mengetahui apakah kedua sinar tersebut berpotongan, Anda tidak harus mencari titik perpotongannya. Berikut ini mungkin lebih stabil dan efisien daripada menyelesaikan persamaan untuk titik perpotongan, karena ini hanya melibatkan pengurangan dan perkalian titik, tanpa pembagian.
Anda memiliki sinar pertama Anda mulai pada $p_0$ dan menuju ke $p_1$ (dan lebih jauh lagi $p_1$), dan sinar kedua Anda mulai dari $q_0$ dan menuju ke $q_1$ (dan lebih jauh lagi $q_1$). Pikirkan tentang itu secara visual. Untuk tetap$p_0$, $p_1$, dan $q_0$, nilai yang mana $q_1$menghasilkan persimpangan? Jawabannya adalah itu$q_1$harus terletak di wilayah pesawat yang berbentuk baji. Satu sisi baji adalah garis di antaranya$q_0$ dan $p_0$, dan sisi lain dari baji sejajar dengan sinar pertama. Dalam diagram,$q_1$ harus berada di wilayah biru agar sinar berpotongan.
Kita bisa mengekspresikan satu sisi irisan dengan mengatakan itu $q_1$ harus berada di sisi yang sama dari $q_0$ untuk $p_0$ baris sebagai $p_1$aku s. Jika$p_0 - q_0 = (l_x, l_y)$, lalu kita bisa memutar $(l_x, l_y)$ 90 derajat untuk mendapatkan vektor tegak lurus dengan garis: $(-l_y, l_x)$. Lalu untuk memeriksanya$q_1$ dan $p_1$ berada di sisi yang sama, kami memeriksanya $(q_1 - q_0) \cdot (-l_y, l_x)$ memiliki tanda yang sama dengan $(p_1 - q_0) \cdot (-l_y, l_x)$.
Kita dapat mengekspresikan sisi lain dari irisan dengan melihat garis yang lewat $q_0$ dan $q_0 + (p_1 - p_0)$. $q_1$ dan $p_1$harus berada di sisi yang sama dari garis ini. Vektor yang sejajar dengan garis adalah$p_1 - p_0 = (m_x, m_y)$ yang kami putar 90 derajat untuk mendapatkan $(-m_y, m_x)$. Untuk memeriksanya$q_1$ dan $p_1$ berada di sisi yang sama dari garis ini, kami memeriksanya $(p_1 - q_0) \cdot (-m_y, m_x)$ memiliki tanda yang sama dengan $(q_1 - q_0) \cdot (-m_y, m_x)$.
Jadi untuk menyimpulkan: kedua sinar berpotongan jika dan hanya jika $(q_1 - q_0) \cdot (-l_y, l_x)$ memiliki tanda yang sama dengan $(p_1 - q_0) \cdot (-l_y, l_x)$, dan $(p_1 - q_0) \cdot (-m_y, m_x)$ memiliki tanda yang sama dengan $(q_1 - q_0) \cdot (-m_y, m_x)$.