algorithm - Verifique si dos segmentos de línea están chocando(solo verifique si se intersecan, no dónde)

math intersection

Question

Necesito un algoritmo rápido para verificar si dos líneas no infinitas se cruzan. Tiene que ser rápido porque funcionará mucho en un teléfono celular.

El algoritmo solo tiene que devolver sí o no, ¡no tiene que averiguar exactamente dónde se cruzan las líneas!

He mirado aquí: ¿Cómo detectas dónde se cruzan dos segmentos de línea? Pero ese hilo es una jungla, la gente sigue diciendo que "esta es la respuesta", pero otros dos dicen que es incorrecto debido a esto y ese error.

Por favor, ayúdame a encontrar un buen algoritmo de trabajo para esto.

Solo para ser claros: necesito una función que me das ...
lineApointAx
lineApointAy
lineApointBx
lineApointBy
lineBpointAx
lineBpointAy
lineBpointBx
lineBpointBy
... y eso devuelve verdadero o falso dependiendo de si las dos líneas se cruzan o no.

Agradecería que respondiera con (pseudo) código, no con fórmulas.

Answer 1

Es necesario y suficiente que los dos extremos de un segmento estén en lados diferentes del otro segmento, y viceversa. Para determinar en qué lado está un punto, simplemente tome un producto cruzado y vea si es positivo o negativo:

(B _x - A _x ) (P _y - B _y ) - (B _y - A _y ) (P _x - B _x )

EDITAR:
Para deletrear: suponga que está viendo dos segmentos de línea, [AB] y [CD]. Los segmentos se intersecan si y solo si ((A y B son de diferentes lados de [CD]) y (C y D están en diferentes lados de [AB])).

Para ver si dos puntos, P y Q, están en lados diferentes de un segmento de línea [EF], calcule dos productos cruzados, uno para P y otro para Q:

(F _x - E _x ) (P _y - F _y ) - (F _y - E _y ) (P _x - F _x )

(F _x - E _x ) (Q _y - F _y ) - (F _y - E _y ) (Q _x - F _x )

Si los resultados tienen el mismo signo (ambos positivos o negativos), entonces olvídelo, los puntos están en el mismo lado, los segmentos no se intersecan. Si uno es positivo y el otro negativo, entonces los puntos están en lados opuestos.

Answer 2

Si sus dos puntos dados son (X1, Y1) y (X2, Y2), imagine que ambas son líneas infinitas, no solo segmentos:

1. Determine la fórmula para ambos (ver: http://en.wikipedia.org/wiki/Linear_equation#Two-point_form )

2. Determine el punto de intersección de las dos líneas (consulte: http://zonalandeducation.com/mmts/intersections/intersectionOfTwoLines1/intersectionOfTwoLines1.html )

3. Si X1 <intersecciónX <X2 e Y1 <intersecciónY <Y2, entonces sí, los segmentos se intersecan.