Jak ustalić, czy przecinają się 2 promienie?

Dec 03 2020

Otrzymujemy współrzędne 2D 2 punktów: pierwszy punkt to miejsce, w którym promień się zaczyna i przechodzi przez drugi punkt. W ten sam sposób otrzymujemy kolejny promień. Jak ustalimy, czy mają punkt przecięcia? Chciałbym poznać ogólny algorytm i jego wyjaśnienie, nie przejmować się skrajnymi przypadkami (np. Kiedy promienie mają ten sam punkt początkowy). PS Widziałem podobne pytanie na innej wymianie stosów, ale odpowiedzi nie były poparte wyjaśnieniami.

Odpowiedzi

2 BiswajitBanerjee Dec 03 2020 at 12:36

Nie jestem pewien, czy odpowiada na twoje pytanie, ale oto coś, co napisałem kilka lat temu dla artykułu.

Pozwolić $\mathbf{p}_0$ i $\mathbf{p}_1$ być punktami końcowymi pierwszego segmentu i niech $\mathbf{q}_0$ i $\mathbf{q}_1$być punktami końcowymi drugiego segmentu. Następnie równania parametryczne dwóch linii są$$ \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 \,. $$ W punkcie przecięcia $\mathbf{p} = \mathbf{q}$tj. $$ (1 - t_p) \mathbf{p}_0 + t_p \mathbf{p}_1 = (1 - t_q) \mathbf{q}_0 + t_q \mathbf{q}_1 \,. $$ Przekształcenie równania daje $$ \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} \,. $$ W związku z tym, $$ \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) $$ Kiedy już rozwiążemy problem $t_p$ i $t_q$z łatwością możemy znaleźć punkt przecięcia. Jeśli punkt przecięcia znajduje się poza$\mathbf{p}$ linia następnie $t_p \notin [0, 1]$. Podobnie w przypadku drugiego segmentu, jeśli punkt przecięcia znajduje się poza segmentem, to$t_q \notin [0, 1]$.

PhilipRoe Dec 04 2020 at 05:37

Ponieważ dowolne dwie nierównoległe proste muszą gdzieś się przecinać (według Euklidesa), wyobrażam sobie, że PO miał na celu nieco inne pytanie. Na przykład, czy promienie przecinają się w wypukłym kadłubie czterech podanych (naprawdę domniemanych) punktów? (wypukły kadłub to obszar otoczony elastyczną taśmą rozciągniętą dookoła wszystkich czterech punktów bez przecinania się). To jest problem rozwiązany przez Biswajita Banerjee. Musisz wiedzieć, gdzie jest skrzyżowanie.

causative Dec 03 2020 at 13:57

Jeśli chcesz tylko wiedzieć, czy promienie się przecinają, nie musisz znajdować punktu przecięcia. Poniższe może być bardziej stabilne i wydajne niż rozwiązywanie równań dla punktu przecięcia, ponieważ obejmuje tylko odejmowanie i iloczyn skalarny, bez dzielenia.

Masz swój pierwszy promień zaczynający się o $p_0$ i idąc w kierunku $p_1$ (i nieskończenie dalej $p_1$), a drugi promień zaczynający się o $q_0$ i idąc w kierunku $q_1$ (i nieskończenie dalej $q_1$). Pomyśl o tym wizualnie. Na stałe$p_0$, $p_1$, i $q_0$, których wartości $q_1$doprowadzić do skrzyżowania? Odpowiedź brzmi:$q_1$musi leżeć w obszarze samolotu w kształcie klina. Jedna strona klina to linia pomiędzy$q_0$ i $p_0$, a druga strona klina jest równoległa do pierwszego promienia. Na schemacie$q_1$ musi znajdować się w niebieskim obszarze, aby promienie się przecinały.

Mówiąc to, możemy wyrazić jedną stronę klina $q_1$ musi znajdować się po tej samej stronie $q_0$ do $p_0$ linia jak $p_1$jest. Gdyby$p_0 - q_0 = (l_x, l_y)$, wtedy możemy się obracać $(l_x, l_y)$ 90 stopni, aby uzyskać wektor prostopadły do ​​linii: $(-l_y, l_x)$. Potem żeby to sprawdzić$q_1$ i $p_1$ są po tej samej stronie, sprawdzamy to $(q_1 - q_0) \cdot (-l_y, l_x)$ ma taki sam znak jak $(p_1 - q_0) \cdot (-l_y, l_x)$.

Możemy wyrazić drugą stronę klina, patrząc na przechodzącą przez nią linię $q_0$ i $q_0 + (p_1 - p_0)$. $q_1$ i $p_1$musi znajdować się po tej samej stronie tej linii. Wektor równoległy do ​​prostej to$p_1 - p_0 = (m_x, m_y)$ które obrócimy o 90 stopni, aby uzyskać $(-m_y, m_x)$. Żeby to sprawdzić$q_1$ i $p_1$ są po tej samej stronie tej linii, sprawdzamy to $(p_1 - q_0) \cdot (-m_y, m_x)$ ma taki sam znak jak $(q_1 - q_0) \cdot (-m_y, m_x)$.

Podsumowując: dwa promienie przecinają się wtedy i tylko wtedy, gdy $(q_1 - q_0) \cdot (-l_y, l_x)$ ma taki sam znak jak $(p_1 - q_0) \cdot (-l_y, l_x)$, i $(p_1 - q_0) \cdot (-m_y, m_x)$ ma taki sam znak jak $(q_1 - q_0) \cdot (-m_y, m_x)$.