Averiguar si dos segmentos de línea se cruzan entre sí

Question

Necesito saber si dos segmentos de recta se cruzan o no. Creo que la fórmula para ello es $y = mx + b$ pero no creo que eso funcione para lo que necesito; al menos, creo que necesito saber primero si los segmentos de la línea se intersecan, porque esa fórmula sólo da el punto en el que las dos líneas se intersecarán finalmente.

Por ejemplo, digamos que tengo dos segmentos de línea Línea $1$ tiene un punto de partida de $(15, 10)$ y su punto final es $(30, 17)$ . Línea $2$ tiene un punto de partida de $(29,5)$ y un punto final de $(33, 14)$ . Éstas no deberían cruzarse dentro de esas coordenadas, pero, utilizando $y = mx + b$ Encuentro que se cruzan aproximadamente en $(35, 19.5)$ .

¿Cómo puedo averiguar si estos segmentos de línea se cruzan entre sí?

Answer 1

La única razón por la que dos líneas no se cruzan es si son paralelas. Ser paralelas es lo mismo que tener la misma pendiente. Así, en tu ejemplo, la recta $1$ tiene pendiente

$$\frac{17 - 10}{30 - 15} = \frac{7}{15}.$$

Línea $2$ tiene pendiente

$$\frac{14 - 5}{33 - 29} = \frac{9}{4}.$$

Como estos dos números no son iguales, las líneas no son paralelas y se cruzan en alguna parte.

Ahora bien, si lo que estás considerando es sólo el segmento de línea entre los dos puntos, yo consideraría primero las pendientes como acabamos de hacer. Si son paralelas, entonces seguro que sabes que no se cruzan. Sin embargo, si las pendientes son diferentes, entonces se cruzarán en un punto. Entonces tienes que encontrar este punto, y ver si ocurre en los límites dados en el $x$ -valores.

Por lo tanto, cuando se encuentra que las líneas se cruzan en el punto $(35, 19.5)$ entonces esta intersección está fuera de los límites dados, ya que, por ejemplo, su primera línea sólo va desde $x = 15$ a $x = 30$ . Nunca llega a $x = 35$ .

Answer 2

Supongo que ya puedes comprobar la intersección de las líneas, ya que eso ya se ha contestado y parece que lo entiendes bien.

Los segmentos son $AB$ y $CD$ . Se cruzan si su punto de intersección se encuentra dentro del rectángulo central más oscuro (es decir, la zona del espacio que ambos ocupan). En otras palabras, si el punto de intersección es $(x,y)$ entonces $x$ debe ser menor que el valor más pequeño del lado derecho (el $x$ -coordinación de $AH$ aquí), y mayor que el valor más pequeño del lado izquierdo ( $GB$ ). Aquí la comprobación $x>GB_x$ falla, para que no se crucen. La idea es similar para $y$ y tiene que pasar los 4 pruebas (dos para $x$ y dos para $y$ ) antes de poder concluir que se cruzan.

Answer 3

Hay dos casos a considerar para determinar si dos segmentos de línea $AB$ y $CD$ se cruzan: (1) Los segmentos de la línea son no (2) los segmentos de línea son colineales (dos imágenes inferiores).

La norma $y = mx + b$ no suele ser útil, ya que omite las líneas verticales. En este caso, lo mejor es tener en cuenta lo siguiente función implícita $h(P)$ para una línea que pasa por $A$ y $B:$ $$h(P) = (B - A) \times (P - A)= 0$$ donde $U \times V = U_x \cdot V_y - U_y \cdot V_x.$ Tenga en cuenta que $h(P)$ define un medio espacio determinando dónde está el punto $P$ se encuentra en relación con la línea divisoria que pasa por $AB:$ $$\begin{array}{ll} h(P) > 0 & \mbox{$P$ in positive half-space} \\ h(P) = 0 & \mbox{$P$ on the line} \\ h(P) < 0 & \mbox{$P$ in negative half-space} \end{array}$$ Así sabemos si los puntos $C$ y $D$ a lo largo de la línea (infinita) que pasa por $AB$ si ambos $h(C)$ y $h(D)$ son distintos de cero y tienen signos opuestos. En el caso general, sabemos que los segmentos de línea $AB$ y $CD$ se cruzan si los puntos $C$ y $D$ a lo largo de la línea a través de $AB$ y los puntos $A$ y $B$ a lo largo de la línea a través de $CD.$

En primer lugar, debemos tratar el caso colineal en el que $h(C) = 0$ y $h(D) = 0.$ Aquí tenemos una intersección si $$\min(C_x,D_x) \leq max(A_x,B_x) \wedge \max(C_x,D_x) \geq \min(A_x,B_x)$$ y $$\min(C_y,D_y) \leq max(A_y,B_y) \wedge \max(C_y,D_y) \geq \min(A_y,B_y)$$

Por lo demás, en el caso general utilizamos nuestras ecuaciones de medio espacio. El semiespacio $g(x)$ definido por $CD$ es $$g(P) = (D - C) \times (P - C) = 0.$$ Tenemos una intersección donde $$(h(C) \cdot h(D) \leq 0) \wedge (g(A) \cdot g(B) \leq 0).$$

Si se desea conocer el punto de intersección real, se introduce el ecuación paramétrica $L(t)$ para una línea a través de $AB$ $$L(t) = (B - A)\cdot t + A, \ \ \ -\infty < t < \infty$$ en $g$ y resolver para $t:$ $$g(L(t)) = (D - C) \times (L(t) - C) = 0 \\ (D - C) \times ((B - A)\cdot t + A - C) = 0 \\ t = \frac{(C - A) \times (D - C)}{(D - C) \times (B - A)}$$ Introduzca este valor para $t$ de nuevo en $L(t)$ y tienes tu punto de intersección. Por supuesto, esto supone la advertencia de que $(D - C) \times (B - A) \neq 0$ donde las líneas son no paralelamente.

Otra gran explicación de esto se puede encontrar aquí .

Answer 4

Si dos rectas tienen pendiente desigual se cruzarán en un punto. Si dos rectas tienen igual pendiente, o bien son paralelas disjuntas y nunca se cruzan, o bien son la misma línea.

Answer 5

Una condición necesaria para comprobar el giro que realiza. Supongamos que $U$ y $V$ para ser los vectores de los segmentos donde $U=(u_{x_2} - u_{x_1}, u_{y_2}-u_{y_1})$ , igualmente para $V$ .

Si $((u_{x_1}, u_{y_2}) - (v_{x_1},v_{y_1}) ) * V < 0$ se cruzan. Si el producto escalar es positivo no se cruzan. En caso contrario, esta prueba rápida no se aplica.