Verificar que dos segmentos de línea no se cruzan, o la intersección proyectada no se encuentra en ninguna de las líneas.

Question

No soy matemático, así que busco fórmulas concretas sin muchos símbolos ni jerga, a ser posible.

Tengo dos segmentos de línea y necesito determinar si se intersecan (verdadero o falso). Lo más cercano que he encontrado es esto: dadas las coordenadas del inicio y final de dos segmentos de recta que se intersecan ¿cómo encuentro las coordenadas de su intersección? donde el cartel original proporciona una solución para la intersección proyectada, y desde allí puedo comparar la intersección con los puntos extremos x,y de una de las líneas para ver si está dentro de un segmento de línea.

(a) ¿hay una manera más fácil de hacerlo en general? Sospecho que sólo podría crear una ecuación y = mx + b para ambos y resolver para un valor común x, y, pero estoy trabajando con coordenadas de pantalla en PowerPoint y no estoy seguro de qué hacer con el parámetro b ya que las líneas están en diferentes partes de la pantalla y no tengo un verdadero punto 'cero'. Además, las coordenadas se miden desde la esquina superior izquierda, que sólo se suma a mi confusión cuando se piensa en una fórmula tradicional línea.

(b) si tuviera que utilizar la ecuación en el post de referencia, ¿hay una manera más fácil de comprobar la intersección proyectada contra las líneas, aparte de simplemente comparar para ver si el punto está dentro del rango x e y de una de las líneas?

Gracias.

Answer 1

He aquí otro enfoque: algo similar al de Zen, pero más complicado.

Los segmentos $AB$ y $CD$ se cruzan si y sólo si ambos de las siguientes son verdaderas:

1. $A$ y $B$ se encuentran a distintos lados de la línea que pasa por $C$ y $D$
2. $C$ y $D$ se encuentran a distintos lados de la línea que pasa por $A$ y $B$

Estas dos condiciones pueden comprobarse utilizando la noción de producto cruzado escalar (fórmulas a continuación).

1. es verdadera si y sólo si los productos cruzados escalares $\vec{CA}\times \vec{CD}$ y $\vec{CB}\times \vec{CD}$ tienen signos opuestos.
2. es verdadera si y sólo si los productos cruzados escalares $\vec{AC}\times \vec{AB}$ y $\vec{AD}\times \vec{AB}$ tienen signos opuestos.

Fórmulas de productos cruzados escalares (en las que verás un patrón): $$ \begin{split} \vec{CA}\times \vec{CD} &= (x_A-x_C)(y_D-y_C)-(y_A-y_C)(x_D-x_C) \\ \vec{CB}\times \vec{CD} &= (x_B-x_C)(y_D-y_C)-(y_B-y_C)(x_D-x_C) \\ \vec{AC}\times \vec{AB} &= (x_C-x_A)(y_B-y_A)-(y_C-y_A)(x_B-x_A) \\ \vec{AD}\times \vec{AB} &= (x_D-x_A)(y_B-y_A)-(y_D-y_A)(x_B-x_A) \\ \end{split} $$ Conclusión: los segmentos de recta se cruzan si y sólo si ambos de los siguientes números son negativos: $$\big((x_A-x_C)(y_D-y_C)-(y_A-y_C)(x_D-x_C)\big)\big((x_B-x_C)(y_D-y_C)-(y_B-y_C)(x_D-x_C)\big)$$ $$\big((x_C-x_A)(y_B-y_A)-(y_C-y_A)(x_B-x_A)\big) \big((x_D-x_A)(y_B-y_A)-(y_D-y_A)(x_B-x_A)\big)$$

Answer 2

Dados dos líneas en $\mathbb{R}^2$ se cruzarán en un único punto si sus pendientes no son iguales.

El problema es más complicado si sólo se dispone de segmentos con los que trabajar. Supongamos que tenemos un segmento [AB] con puntos extremos $A(x_A,y_A)$ y $B(x_B,y_B)$ y un segmento [CD] con extremos $C(x_C,y_C)$ y $D(x_D,x_D)$ Si los segmentos se intersecan, entonces A y B estarán en lados opuestos del segmento CD (uno estará por encima y otro por debajo).

En primer lugar, compruebe si existe algún solapamiento (algún punto en común) en los intervalos $[x_A, x_B]$ y $[x_C,x_D]$ - si es así, procede, si no , no se cruzan.

Supongamos que A y C están (intuitivamente hablando) en el lado derecho del gráfico y B y D en el lado izquierdo. Calcule $(y_A-y_C)(y_B-y_D)$ con A, C, B, D en ese orden . Si el resultado es positivo, no se han cruzado. Si es negativo, se han cruzado.

Answer 3

¿Qué considera jerga? ¿Ha estudiado al menos álgebra lineal básica?
Si tienes dos líneas infinitamente largas en 2D, siempre se cruzan a menos que sean paralelas.
Es decir, existen unos valores de s y t que.
a+(b-a)t == c+(d-c)s
Donde sus puntos de línea son a & b y c & d como vectores 2d.
Esto es lo mismo que decir:
a-c+(b-a)t == (d-c)s
Que es un conjunto simple de dos ecuaciones lineales.
Si tanto s como t están entre 0 y 1, significa que ambos se intersecan, si no, entonces la intersección está en la prolongación de la recta.