¿Cómo determinar si 2 segmentos de línea se cruzan?

Question

Dé dos segmentos de línea, cada uno definido por $2$ puntos en $x,y$ espacio, como $L_1 = (x_1,y_1)-(x_2,y_2)$ y $L_2 = (x_3-y_3)-(x_4,y_4)$ y que estos puntos son el resultado de datos muestreados (no son el resultado de funciones conocidas), ¿hay alguna manera de saber si los segmentos de línea $L_1$ y $L_2$ se cruzan entre sí (¿comparten un $x,y$ punto)? Se desea un resultado de sí o no, no necesariamente dónde (en qué coordenada) se cruzan.

Answer 1

Como los puntos proceden de datos muestreados, podemos ignorar los casos límite, como que tres de los cuatro puntos sean colineales.

Para un punto $(x,y)$ se puede calcular la expresión $$ f(x,y)=(x-x_1)(y_2-y_1)-(y-y_1)(x_2-x_1)$$ y esto cambia de signo precisamente cuando $(x,y)$ se mueve a través de la línea dada por $(x_1,y_1)$ y $(x_2,y_2)$ . Por lo tanto, si $f(x_3,y_3)$ y $f(x_4,y_4)$ tienen signos diferentes, los puntos finales del segundo segmento de línea están en lados diferentes de la primera línea (prolongada). Con una prueba similar, se puede comprobar si los puntos $(x_1,y_1)$ y $(x_2,y_2)$ están en lados diferentes de la segunda línea (prolongada). Si y sólo si estas dos pruebas se aprueban, entonces los dos segmentos de línea se cruzan.

Answer 2

Vemos que dos puntos $P_1$ , $P_2$ están en los mismos lados (opuestos) de la línea $QR$ si y sólo si el $\it{oriented}$ zonas $\text{Area}(P_1 QR) $ y $\text{Area}(P_2 QR)$ tienen el mismo signo (opuesto). Las expresiones que aparecen son simplemente determinantes .

Esto se puede generalizar fácilmente en $n$ -espacio, cuando se pregunta si dos puntos $P_1$ , $P_2$ están en el mismo lado o en lados opuestos del hiperplano determinado por $Q_1, \ldots Q_n$ .

Así que para el problema que nos ocupa, los segmentos $P_1 P_2$ y $P_3 P_4$ se cruzan si y sólo si \begin {eqnarray} \text {Area}(P_1 P_3 P_4)& \cdot & \text {Area}(P_2 P_3 P_4) \le 0 \ \ \text {y} \\ \text {Area}(P_3 P_1 P_2)& \cdot & \text {Area}(P_4 P_1 P_2) \le 0 \end {eqnarray}

Nota:
$$\text{Area}(P_1 P_2 P_3) = \frac{1}{2} \cdot \left | \begin{array}{ccc} 1 & x_1 &y_1 \\ 1 & x_2 &y_2 \\ 1 & x_3 &y_3 \end{array} \right| $$

Answer 3

dejar

$f(x,y)=(x-x_1)(y_2-y_1)-(y-y_1)(x_2-x_1)$

y

$g(x,y)=(x-x_3)(y_4-y_3)-(y-y_3)(x_4-x_3)$

entonces los segmentos se intersecan siempre que las dos afirmaciones siguientes sean correctas.

$$f(x_3, y_3)f(x_4, y_4) <0 $$ $$ g(x_1, y_1)g(x_2, y_2) <0$$

Answer 4

Estaba pensando que el punto de intersección de las líneas estaría dado por la coordenada X $x = (B_2-B_1) / (M_1 - M_2)$ donde $B_n$ y $M_n$ son el intercepto y la pendiente según $y = Mx + B$ y $n$ es el segmento de línea del que se habla (1 y 2). Entonces sería sencillo comprobar si ( $x$ se encuentra entre $X_1$ y $X_2$ ) y ( $x$ se encuentra entre $X_3$ y $X_4$ ). ¿Si? ¿No?

Answer 5

Enunciado verbalmente, tanto x como y deben estar entre sus respectivos puntos extremos para tener una intersección. Y simbólicamente

$$ (x-x_1)( x_2 -x) > 0,\NY \N, (y-y_1)(y_2-y) > 0 \NY \N,

(x-x_3)( x_4 -x) > 0,\Ny, (y-y_3)(y_4-y) > 0 $$

donde $ \ge $ signo válido si la intersección se produce en un extremo de una línea.

EDIT1

Y, de manera similar para la segunda línea.