¿Cómo puedo comprobar si dos segmentos se cruzan?

¿Cómo puedo comprobar si se cruzan 2 segmentos?

Tengo los siguientes datos:

Segment1 [ {x1,y1}, {x2,y2} ]
Segment2 [ {x1,y1}, {x2,y2} ] 

Necesito escribir un pequeño algoritmo en Python para detectar si las 2 líneas se cruzan.

La ecuación de una línea es:

f(x) = A*x + b = y

Para un segmento, es exactamente lo mismo, excepto que x se incluye en un intervalo I.

Si tiene dos segmentos, definidos de la siguiente manera:

Segment1 = {(X1, Y1), (X2, Y2)}
Segment2 = {(X3, Y3), (X4, Y4)}

El abciso Xa del punto potencial de intersección (Xa, Ya) debe estar contenido tanto en el intervalo I1 como en I2, definido como sigue:

I1 = [min(X1,X2), max(X1,X2)]
I2 = [min(X3,X4), max(X3,X4)]

Y podríamos decir que Xa se incluye en:

Ia = [max( min(X1,X2), min(X3,X4) ),
      min( max(X1,X2), max(X3,X4) )]

Ahora, debemos comprobar que existe este intervalo Ia:

if (max(X1,X2) < min(X3,X4)):
    return False  # There is no mutual abcisses

Entonces, tenemos una fórmula de dos líneas y un intervalo mutuo. Sus fórmulas de línea son:

f1(x) = A1*x + b1 = y
f2(x) = A2*x + b2 = y

Como obtuvimos dos puntos por segmento, podemos determinar A1, A2, b1 y b2:

A1 = (Y1-Y2)/(X1-X2)  # Pay attention to not dividing by zero
A2 = (Y3-Y4)/(X3-X4)  # Pay attention to not dividing by zero
b1 = Y1-A1*X1 = Y2-A1*X2
b2 = Y3-A2*X3 = Y4-A2*X4

Si los segmentos son paralelos, entonces A1 == A2:

if (A1 == A2):
    return False  # Parallel segments

Un punto (Xa, Ya) que se encuentra en ambas líneas debe verificar ambas fórmulas f1 y f2:

Ya = A1 * Xa + b1
Ya = A2 * Xa + b2
A1 * Xa + b1 = A2 * Xa + b2
Xa = (b2 - b1) / (A1 - A2)   # Once again, pay attention to not dividing by zero

Lo último que debe hacer es verificar que Xa esté incluido en Ia:

if ( (Xa < max( min(X1,X2), min(X3,X4) )) or
     (Xa > min( max(X1,X2), max(X3,X4) )) ):
    return False  # intersection is out of bound
else:
    return True

Además de esto, puede verificar al inicio que dos de los cuatro puntos proporcionados no son iguales para evitar todas esas pruebas.

El usuario @ i_4_got apunta a esta página con una solución muy eficiente en Python. Lo reproduzco aquí por conveniencia (ya que me hubiera hecho feliz tenerlo aquí):

def ccw(A,B,C):
    return (C.y-A.y) * (B.x-A.x) > (B.y-A.y) * (C.x-A.x)

# Return true if line segments AB and CD intersect
def intersect(A,B,C,D):
    return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)

No tiene que calcular exactamente dónde se cruzan los segmentos, solo debe comprender si se cruzan en absoluto. Esto simplificará la solución.

La idea es tratar un segmento como el "ancla" y separar el segundo segmento en 2 puntos.
Ahora, tendrá que encontrar la posición relativa de cada punto al segmento "anclado" (OnLeft, OnRight o Collinear).
Después de hacerlo para ambos puntos, verifique que uno de los puntos esté en la izquierda y el otro en la derecha (o quizás incluya la posición colineal, si desea incluir también intersecciones incorrectas ).

Luego debe repetir el proceso con los roles de ancla y segmentos separados.

Existe una intersección si, y solo si, uno de los puntos es OnLeft y el otro es OnRight. Consulte este enlace para obtener una explicación más detallada con imágenes de ejemplo para cada posible caso.

La implementación de dicho método será mucho más fácil que la implementación de un método que encuentre el punto de intersección (dados los muchos casos de esquina que también tendrá que manejar).

Actualizar

Las siguientes funciones deberían ilustrar la idea (fuente: geometría computacional en C ).
Observación: esta muestra asume el uso de números enteros. Si está usando alguna representación de punto flotante en su lugar (lo que obviamente podría complicar las cosas), entonces debería determinar algún valor épsilon para indicar "igualdad" (principalmente para la IsCollinearevaluación).

// points "a" and "b" forms the anchored segment.
// point "c" is the evaluated point
bool IsOnLeft(Point a, Point b, Point c)
{
     return Area2(a, b, c) > 0;
}

bool IsOnRight(Point a, Point b, Point c)
{
     return Area2(a, b, c) < 0;
}

bool IsCollinear(Point a, Point b, Point c)
{
     return Area2(a, b, c) == 0;
}

// calculates the triangle's size (formed by the "anchor" segment and additional point)
int Area2(Point a, Point b, Point c)
{
     return (b.X - a.X) * (c.Y - a.Y) -
            (c.X - a.X) * (b.Y - a.Y);
}

Por supuesto, al usar estas funciones, uno debe recordar verificar que cada segmento se encuentre "entre" el otro segmento (ya que estos son segmentos finitos y no líneas infinitas).

Además, al usar estas funciones, puede comprender si tiene una intersección adecuada o incorrecta .

• Adecuado : No hay puntos colineales. Los segmentos se cruzan "de lado a lado".
• Incorrecto : Un segmento solo "toca" al otro (al menos uno de los puntos es colineal con el segmento anclado).

Suponga que los dos segmentos tienen extremos A, B y C, D. La forma numéricamente robusta de determinar la intersección es verificar el signo de los cuatro determinantes:

| Ax-Cx  Bx-Cx |    | Ax-Dx  Bx-Dx |
| Ay-Cy  By-Cy |    | Ay-Dy  By-Dy |

| Cx-Ax  Dx-Ax |    | Cx-Bx  Dx-Bx |
| Cy-Ay  Dy-Ay |    | Cy-By  Dy-By |

Para la intersección, cada determinante de la izquierda debe tener el signo opuesto del de la derecha, pero no es necesario que haya ninguna relación entre las dos líneas. Básicamente, está comparando cada punto de un segmento con el otro segmento para asegurarse de que estén en lados opuestos de la línea definida por el otro segmento.

Ver aquí: http://www.cs.cmu.edu/~quake/robust.html

Verificar si los segmentos de línea se cruzan es muy fácil con la biblioteca Shapely usando el intersectsmétodo:

from shapely.geometry import LineString

line = LineString([(0, 0), (1, 1)])
other = LineString([(0, 1), (1, 0)])
print(line.intersects(other))
# True

line = LineString([(0, 0), (1, 1)])
other = LineString([(0, 1), (1, 2)])
print(line.intersects(other))
# False

Basado en las excelentes respuestas de Liran y Grumdrig, aquí hay un código Python completo para verificar si los segmentos cerrados se cruzan. Funciona para segmentos colineales, segmentos paralelos al eje Y, segmentos degenerados (el diablo está en detalles). Asume coordenadas enteras. Las coordenadas de punto flotante requieren una modificación de la prueba de igualdad de puntos.

def side(a,b,c):
    """ Returns a position of the point c relative to the line going through a and b
        Points a, b are expected to be different
    """
    d = (c[1]-a[1])*(b[0]-a[0]) - (b[1]-a[1])*(c[0]-a[0])
    return 1 if d > 0 else (-1 if d < 0 else 0)

def is_point_in_closed_segment(a, b, c):
    """ Returns True if c is inside closed segment, False otherwise.
        a, b, c are expected to be collinear
    """
    if a[0] < b[0]:
        return a[0] <= c[0] and c[0] <= b[0]
    if b[0] < a[0]:
        return b[0] <= c[0] and c[0] <= a[0]

    if a[1] < b[1]:
        return a[1] <= c[1] and c[1] <= b[1]
    if b[1] < a[1]:
        return b[1] <= c[1] and c[1] <= a[1]

    return a[0] == c[0] and a[1] == c[1]

#
def closed_segment_intersect(a,b,c,d):
    """ Verifies if closed segments a, b, c, d do intersect.
    """
    if a == b:
        return a == c or a == d
    if c == d:
        return c == a or c == b

    s1 = side(a,b,c)
    s2 = side(a,b,d)

    # All points are collinear
    if s1 == 0 and s2 == 0:
        return \
            is_point_in_closed_segment(a, b, c) or is_point_in_closed_segment(a, b, d) or \
            is_point_in_closed_segment(c, d, a) or is_point_in_closed_segment(c, d, b)

    # No touching and on the same side
    if s1 and s1 == s2:
        return False

    s1 = side(c,d,a)
    s2 = side(c,d,b)

    # No touching and on the same side
    if s1 and s1 == s2:
        return False

    return True

Aquí hay una solución que usa productos punto:

# assumes line segments are stored in the format [(x0,y0),(x1,y1)]
def intersects(s0,s1):
    dx0 = s0[1][0]-s0[0][0]
    dx1 = s1[1][0]-s1[0][0]
    dy0 = s0[1][1]-s0[0][1]
    dy1 = s1[1][1]-s1[0][1]
    p0 = dy1*(s1[1][0]-s0[0][0]) - dx1*(s1[1][1]-s0[0][1])
    p1 = dy1*(s1[1][0]-s0[1][0]) - dx1*(s1[1][1]-s0[1][1])
    p2 = dy0*(s0[1][0]-s1[0][0]) - dx0*(s0[1][1]-s1[0][1])
    p3 = dy0*(s0[1][0]-s1[1][0]) - dx0*(s0[1][1]-s1[1][1])
    return (p0*p1<=0) & (p2*p3<=0)

Aquí hay una visualización en Desmos: Intersección de segmento de línea

Tienes dos segmentos de línea. Defina un segmento por los extremos A y B y el segundo segmento por los extremos C y D. Hay un buen truco para mostrar que deben cruzarse DENTRO de los límites de los segmentos. (Tenga en cuenta que las líneas mismas pueden cruzarse más allá de los límites de los segmentos, por lo que debe tener cuidado. Un buen código también observará las líneas paralelas).

El truco consiste en probar que los puntos A y B deben alinearse en lados opuestos de la línea CD, Y que los puntos C y D deben estar en lados opuestos de la línea AB.

Dado que esto es tarea, no te daré una solución explícita. Pero una prueba simple para ver en qué lado de una línea cae un punto es usar un producto escalar. Por lo tanto, para una línea CD determinada, calcule el vector normal a esa línea (lo llamaré N_C). Ahora, simplemente pruebe los signos de estos dos resultados:

dot(A-C,N_C)

y

dot(B-C,N_C)

Si esos resultados tienen signos opuestos, entonces A y B son lados opuestos de la línea CD. Ahora haz la misma prueba para la otra línea, AB. Tiene vector normal N_A. Compara los signos de

dot(C-A,N_A)

y

dot(D-A,N_A)

Dejaré que usted averigüe cómo calcular un vector normal. (En 2-d, eso es trivial, pero ¿su código se preocupará por si A y B son puntos distintos? Del mismo modo, ¿son C y D distintos?)

Aún debe preocuparse por los segmentos de línea que se encuentran a lo largo de la misma línea infinita, o si un punto realmente cae sobre el otro segmento de línea. Un buen código resolverá todos los problemas posibles.

Aquí está el código C para verificar si dos puntos están en los lados opuestos del segmento de línea. Con este código, puede verificar si dos segmentos también se cruzan.

// true if points p1, p2 lie on the opposite sides of segment s1--s2
bool oppositeSide (Point2f s1, Point2f s2, Point2f p1, Point2f p2) {

//calculate normal to the segment
Point2f vec = s1-s2;
Point2f normal(vec.y, -vec.x); // no need to normalize

// vectors to the points
Point2f v1 = p1-s1;
Point2f v2 = p2-s1;

// compare signs of the projections of v1, v2 onto the normal
float proj1 = v1.dot(normal);
float proj2 = v2.dot(normal);
if (proj1==0 || proj2==0)
        cout<<"collinear points"<<endl;

return(SIGN(proj1) != SIGN(proj2));

}

Aquí hay otro código de Python para verificar si los segmentos cerrados se cruzan. Es la versión reescrita del código C ++ en http://www.cdn.geeksforgeeks.org/check-if-two-given-line-segments-intersect/ . Esta implementación cubre todos los casos especiales (por ejemplo, todos los puntos colineales).

def on_segment(p, q, r):
    '''Given three colinear points p, q, r, the function checks if 
    point q lies on line segment "pr"
    '''
    if (q[0] <= max(p[0], r[0]) and q[0] >= min(p[0], r[0]) and
        q[1] <= max(p[1], r[1]) and q[1] >= min(p[1], r[1])):
        return True
    return False

def orientation(p, q, r):
    '''Find orientation of ordered triplet (p, q, r).
    The function returns following values
    0 --> p, q and r are colinear
    1 --> Clockwise
    2 --> Counterclockwise
    '''

    val = ((q[1] - p[1]) * (r[0] - q[0]) - 
            (q[0] - p[0]) * (r[1] - q[1]))
    if val == 0:
        return 0  # colinear
    elif val > 0:
        return 1   # clockwise
    else:
        return 2  # counter-clockwise

def do_intersect(p1, q1, p2, q2):
    '''Main function to check whether the closed line segments p1 - q1 and p2 
       - q2 intersect'''
    o1 = orientation(p1, q1, p2)
    o2 = orientation(p1, q1, q2)
    o3 = orientation(p2, q2, p1)
    o4 = orientation(p2, q2, q1)

    # General case
    if (o1 != o2 and o3 != o4):
        return True

    # Special Cases
    # p1, q1 and p2 are colinear and p2 lies on segment p1q1
    if (o1 == 0 and on_segment(p1, p2, q1)):
        return True

    # p1, q1 and p2 are colinear and q2 lies on segment p1q1
    if (o2 == 0 and on_segment(p1, q2, q1)):
        return True

    # p2, q2 and p1 are colinear and p1 lies on segment p2q2
    if (o3 == 0 and on_segment(p2, p1, q2)):
        return True

    # p2, q2 and q1 are colinear and q1 lies on segment p2q2
    if (o4 == 0 and on_segment(p2, q1, q2)):
        return True

    return False # Doesn't fall in any of the above cases

A continuación se muestra una función de prueba para verificar que funciona.

import matplotlib.pyplot as plt

def test_intersect_func():
    p1 = (1, 1)
    q1 = (10, 1)
    p2 = (1, 2)
    q2 = (10, 2)
    fig, ax = plt.subplots()
    ax.plot([p1[0], q1[0]], [p1[1], q1[1]], 'x-')
    ax.plot([p2[0], q2[0]], [p2[1], q2[1]], 'x-')
    print(do_intersect(p1, q1, p2, q2))

    p1 = (10, 0)
    q1 = (0, 10)
    p2 = (0, 0)
    q2 = (10, 10)
    fig, ax = plt.subplots()
    ax.plot([p1[0], q1[0]], [p1[1], q1[1]], 'x-')
    ax.plot([p2[0], q2[0]], [p2[1], q2[1]], 'x-')
    print(do_intersect(p1, q1, p2, q2))

    p1 = (-5, -5)
    q1 = (0, 0)
    p2 = (1, 1)
    q2 = (10, 10)
    fig, ax = plt.subplots()
    ax.plot([p1[0], q1[0]], [p1[1], q1[1]], 'x-')
    ax.plot([p2[0], q2[0]], [p2[1], q2[1]], 'x-')
    print(do_intersect(p1, q1, p2, q2))

    p1 = (0, 0)
    q1 = (1, 1)
    p2 = (1, 1)
    q2 = (10, 10)
    fig, ax = plt.subplots()
    ax.plot([p1[0], q1[0]], [p1[1], q1[1]], 'x-')
    ax.plot([p2[0], q2[0]], [p2[1], q2[1]], 'x-')
    print(do_intersect(p1, q1, p2, q2))

para los segmentos AB y CD, encuentre la pendiente de CD

slope=(Dy-Cy)/(Dx-Cx)

extienda CD sobre A y B, y tome la distancia hasta CD yendo directamente hacia arriba

dist1=slope*(Cx-Ax)+Ay-Cy
dist2=slope*(Dx-Ax)+Ay-Dy

comprobar si están en lados opuestos

return dist1*dist2<0

Como no menciona que desea encontrar el punto de intersección de la línea, el problema se vuelve más simple de resolver. Si necesita el punto de intersección, entonces la respuesta de OMG_peanuts es un enfoque más rápido. Sin embargo, si solo desea averiguar si las líneas se cruzan o no, puede hacerlo usando la ecuación de línea (ax + by + c = 0). El enfoque es el siguiente:

1. Comencemos con dos segmentos de línea: segmento 1 y segmento 2.

   segment1 = [[x1,y1], [x2,y2]]
   segment2 = [[x3,y3], [x4,y4]]
   

2. Compruebe si los dos segmentos de línea son líneas de longitud distinta de cero y segmentos distintos.

3. A partir de aquí, supongo que los dos segmentos tienen una longitud distinta de cero y son distintos. Para cada segmento de línea, calcule la pendiente de la línea y luego obtenga la ecuación de una línea en la forma de ax + por + c = 0. Ahora, calcule el valor de f = ax + por + c para los dos puntos del otro segmento de línea (repita esto también para el otro segmento de línea).

   a2 = (y3-y4)/(x3-x4);
   b1 = -1;
   b2 = -1;
   c1 = y1 - a1*x1;
   c2 = y3 - a2*x3;
   // using the sign function from numpy
   f1_1 = sign(a1*x3 + b1*y3 + c1);
   f1_2 = sign(a1*x4 + b1*y4 + c1);
   f2_1 = sign(a2*x1 + b2*y1 + c2);
   f2_2 = sign(a2*x2 + b2*y2 + c2);
   

4. Ahora todo lo que queda son los diferentes casos. Si f = 0 para cualquier punto, entonces las dos líneas se tocan en un punto. Si f1_1 y f1_2 son iguales o f2_1 y f2_2 son iguales, entonces las líneas no se cruzan. Si f1_1 y f1_2 son desiguales y f2_1 y f2_2 no son iguales, entonces los segmentos de línea se intersecan. Dependiendo de si desea considerar las líneas que se tocan como "intersectantes" o no, puede adaptar sus condiciones.

También podemos resolver esto utilizando vectores.

Definamos los segmentos como [start, end]. Dados dos de esos segmentos [A, B]y [C, D]que ambos tienen una longitud distinta de cero, podemos elegir uno de los puntos finales que se utilizará como punto de referencia para obtener tres vectores:

x = 0
y = 1
p = A-C = [C[x]-A[x], C[y]-A[y]]
q = B-A = [B[x]-A[x], B[y]-A[y]]
r = D-C = [D[x]-C[x], D[y]-C[y]]

A partir de ahí, podemos buscar una intersección calculando ty u en p + t*r = u*q. Después de jugar un poco con la ecuación, obtenemos:

t = (q[y]*p[x] - q[x]*p[y])/(q[x]*r[y] - q[y]*r[x])
u = (p[x] + t*r[x])/q[x]

Por tanto, la función es:

def intersects(a, b):
    p = [b[0][0]-a[0][0], b[0][1]-a[0][1]]
    q = [a[1][0]-a[0][0], a[1][1]-a[0][1]]
    r = [b[1][0]-b[0][0], b[1][1]-b[0][1]]

    t = (q[1]*p[0] - q[0]*p[1])/(q[0]*r[1] - q[1]*r[0]) \
        if (q[0]*r[1] - q[1]*r[0]) != 0 \
        else (q[1]*p[0] - q[0]*p[1])
    u = (p[0] + t*r[0])/q[0] \
        if q[0] != 0 \
        else (p[1] + t*r[1])/q[1]

    return t >= 0 and t <= 1 and u >= 0 and u <= 1

Esta es mi manera de verificar si hay cruces de línea y dónde ocurre la intersección. Usemos de x1 a x4 y de y1 a y4

Segment1 = {(X1, Y1), (X2, Y2)}
Segment2 = {(X3, Y3), (X4, Y4)}

Entonces necesitamos algunos vectores para representarlos.

dx1 = X2 - X1
dx2 = X4 - X4
dy1 = Y2 - Y1
dy2 = Y4 - Y3

Ahora miramos el determinante

det = dx1 * dy2 - dx2 * dy1

Si el determinante es 0.0, entonces los segmentos de línea son paralelos. Esto podría significar que se superponen. Si se superponen solo en los puntos finales, entonces hay una solución de intersección. De lo contrario, habrá infinitas soluciones. Con infinitas soluciones, ¿cuál es su punto de intersección? Así que es un caso especial interesante. Si sabe de antemano que las líneas no se pueden superponer, puede comprobar sidet == 0.0 es así y decir que no se cruzan y listo. De lo contrario, continuemos

dx3 = X3 - X1
dy3 = Y3 - Y1

det1 = dx1 * dy3 - dx3 * dy1
det2 = dx2 * dy3 - dx3 * dy2

Ahora, si det, det1 y det2 son todos cero, entonces sus líneas son colineales y podrían superponerse. Si det es cero pero det1 o det2 no lo son, entonces no son colineales, sino paralelos, por lo que no hay intersección. Entonces, lo que queda ahora si det es cero es un problema de 1D en lugar de 2D. Tendremos que verificar una de dos formas, dependiendo de si dx1 es cero o no (para evitar la división por cero). Si dx1 es cero, simplemente haga la misma lógica con valores de y en lugar de x a continuación.

s = X3 / dx1
t = X4 / dx1

Esto calcula dos escaladores, de modo que si escalamos el vector (dx1, dy1) por s, obtenemos el punto (x3, y3) y por t obtenemos (x4, y4). Entonces, si so t está entre 0.0 y 1.0, entonces el punto 3 o 4 se encuentra en nuestra primera línea. Negativo significaría que el punto está detrás del inicio de nuestro vector, mientras que> 1.0 significa que está más adelante del final de nuestro vector. 0.0 significa que está en (x1, y1) y 1.0 significa que está en (x2, y2). Si tanto s como t son <0.0 o ambos son> 1.0, entonces no se cruzan. Y eso maneja el caso especial de las líneas paralelas.

Ahora, si det != 0.0entonces

s = det1 / det
t = det2 / det
if (s < 0.0 || s > 1.0 || t < 0.0 || t > 1.0)
    return false  // no intersect

Esto es realmente similar a lo que estábamos haciendo arriba. Ahora, si pasamos la prueba anterior, entonces nuestros segmentos de línea se cruzan y podemos calcular la intersección con bastante facilidad así:

Ix = X1 + t * dx1
Iy = Y1 + t * dy1

Si desea profundizar en lo que hacen las matemáticas, consulte la regla de Cramer.

La respuesta de Georgy es la más limpia de implementar, con diferencia. Tuve que perseguir esto, ya que el ejemplo de brycboe, aunque simple también, tenía problemas con la colinealidad.

Código de prueba:

#!/usr/bin/python
#
# Notes on intersection:
#
# https://bryceboe.com/2006/10/23/line-segment-intersection-algorithm/
#
# /programming/3838329/how-can-i-check-if-two-segments-intersect

from shapely.geometry import LineString

class Point:
    def __init__(self,x,y):
        self.x = x
        self.y = y

def ccw(A,B,C):
    return (C.y-A.y)*(B.x-A.x) > (B.y-A.y)*(C.x-A.x)

def intersect(A,B,C,D):
    return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)


def ShapelyIntersect(A,B,C,D):
    return LineString([(A.x,A.y),(B.x,B.y)]).intersects(LineString([(C.x,C.y),(D.x,D.y)]))


a = Point(0,0)
b = Point(0,1)
c = Point(1,1)
d = Point(1,0)

'''
Test points:

b(0,1)   c(1,1)




a(0,0)   d(1,0)
'''

# F
print(intersect(a,b,c,d))

# T
print(intersect(a,c,b,d))
print(intersect(b,d,a,c))
print(intersect(d,b,a,c))

# F
print(intersect(a,d,b,c))

# same end point cases:
print("same end points")
# F - not intersected
print(intersect(a,b,a,d))
# T - This shows as intersected
print(intersect(b,a,a,d))
# F - this does not
print(intersect(b,a,d,a))
# F - this does not
print(intersect(a,b,d,a))

print("same end points, using shapely")
# T
print(ShapelyIntersect(a,b,a,d))
# T
print(ShapelyIntersect(b,a,a,d))
# T
print(ShapelyIntersect(b,a,d,a))
# T
print(ShapelyIntersect(a,b,d,a))

si sus datos definen una línea, solo tiene que demostrar que no son paralelos. Para hacer esto, puede calcular

alpha = float(y2 - y1) / (x2 - x1).

Si este coeficiente es igual para Line1 y Line2, significa que la línea es paralela. Si no, significa que se cruzarán.

Si son paralelos, debe demostrar que no son lo mismo. Para eso, calcula

beta = y1 - alpha*x1

Si beta es el mismo para Line1 y Line2, significa que la línea se cruza ya que son iguales

Si son segmentos, aún debe calcular alfa y beta como se describe anteriormente para cada línea. Luego, debes verificar que (beta1 - beta2) / (alpha1 - alpha2) sea mayor que Min (x1_line1, x2_line1) y menor que Max (x1_line1, x2_line1)

Calcula el punto de intersección de las líneas que se encuentran en tus segmentos (básicamente significa resolver un sistema de ecuaciones lineales), luego verifica si está entre los puntos inicial y final de tus segmentos.

Esto es lo que tengo para AS3, no sé mucho sobre Python pero el concepto está ahí.

    public function getIntersectingPointF($A:Point, $B:Point, $C:Point, $D:Point):Number {
        var A:Point = $A.clone();
        var B:Point = $B.clone();
        var C:Point = $C.clone();
        var D:Point = $D.clone();
        var f_ab:Number = (D.x - C.x) * (A.y - C.y) - (D.y - C.y) * (A.x - C.x);

        // are lines parallel
        if (f_ab == 0) { return Infinity };

        var f_cd:Number = (B.x - A.x) * (A.y - C.y) - (B.y - A.y) * (A.x - C.x);
        var f_d:Number = (D.y - C.y) * (B.x - A.x) - (D.x - C.x) * (B.y - A.y);
        var f1:Number = f_ab/f_d
        var f2:Number = f_cd / f_d
        if (f1 == Infinity || f1 <= 0 || f1 >= 1) { return Infinity };
        if (f2 == Infinity || f2 <= 0 || f2 >= 1) { return Infinity };
        return f1;
    }

    public function getIntersectingPoint($A:Point, $B:Point, $C:Point, $D:Point):Point
    {
        var f:Number = getIntersectingPointF($A, $B, $C, $D);
        if (f == Infinity || f <= 0 || f >= 1) { return null };

        var retPoint:Point = Point.interpolate($A, $B, 1 - f);
        return retPoint.clone();
    }

Implementado en JAVA. Sin embargo, parece que no funciona para líneas colineales (también conocidas como segmentos de línea que existen entre sí L1 (0,0) (10,10) L2 (1,1) (2,2)

public class TestCode
{

  public class Point
  {
    public double x = 0;
    public double y = 0;
    public Point(){}
  }

  public class Line
  {
    public Point p1, p2;
    public Line( double x1, double y1, double x2, double y2) 
    {
      p1 = new Point();
      p2 = new Point();
      p1.x = x1;
      p1.y = y1;
      p2.x = x2;
      p2.y = y2;
    }
  }

  //line segments
  private static Line s1;
  private static Line s2;

  public TestCode()
  {
    s1 = new Line(0,0,0,10);
    s2 = new Line(-1,0,0,10);
  }

  public TestCode(double x1, double y1, 
    double x2, double y2,
    double x3, double y3,
    double x4, double y4)
  {
    s1 = new Line(x1,y1, x2,y2);
    s2 = new Line(x3,y3, x4,y4);
  }

  public static void main(String args[])
  {
     TestCode code  = null;
////////////////////////////
     code = new TestCode(0,0,0,10,
                         0,1,0,5);
     if( intersect(code) )
     { System.out.println( "OK COLINEAR: INTERSECTS" ); }
     else
     { System.out.println( "ERROR COLINEAR: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,0,0,10,
                         0,1,0,10);
     if( intersect(code) )
     { System.out.println( "OK COLINEAR: INTERSECTS" ); }
     else
     { System.out.println( "ERROR COLINEAR: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,0,10,0,
                         5,0,15,0);
     if( intersect(code) )
     { System.out.println( "OK COLINEAR: INTERSECTS" ); }
     else
     { System.out.println( "ERROR COLINEAR: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,0,10,0,
                         0,0,15,0);
     if( intersect(code) )
     { System.out.println( "OK COLINEAR: INTERSECTS" ); }
     else
     { System.out.println( "ERROR COLINEAR: DO NOT INTERSECT" ); }

////////////////////////////
     code = new TestCode(0,0,10,10,
                         1,1,5,5);
     if( intersect(code) )
     { System.out.println( "OK COLINEAR: INTERSECTS" ); }
     else
     { System.out.println( "ERROR COLINEAR: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,0,0,10,
                         -1,-1,0,10);
     if( intersect(code) )
     { System.out.println( "OK SLOPE END: INTERSECTS" ); }
     else
     { System.out.println( "ERROR SLOPE END: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(-10,-10,10,10,
                         -10,10,10,-10);
     if( intersect(code) )
     { System.out.println( "OK SLOPE Intersect(0,0): INTERSECTS" ); }
     else
     { System.out.println( "ERROR SLOPE Intersect(0,0): DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(-10,-10,10,10,
                         -3,-2,50,-2);
     if( intersect(code) )
     { System.out.println( "OK SLOPE Line2 VERTIAL: INTERSECTS" ); }
     else
     { System.out.println( "ERROR SLOPE Line2 VERTICAL: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(-10,-10,10,10,
                         50,-2,-3,-2);
     if( intersect(code) )
     { System.out.println( "OK SLOPE Line2 (reversed) VERTIAL: INTERSECTS" ); }
     else
     { System.out.println( "ERROR SLOPE Line2 (reversed) VERTICAL: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,0,0,10,
                         1,0,1,10);
     if( intersect(code) )
     { System.out.println( "ERROR PARALLEL VERTICAL: INTERSECTS" ); }
     else
     { System.out.println( "OK PARALLEL VERTICAL: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,2,10,2,
                         0,10,10,10);
     if( intersect(code) )
     { System.out.println( "ERROR PARALLEL HORIZONTAL: INTERSECTS" ); }
     else
     { System.out.println( "OK PARALLEL HORIZONTAL: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,10,5,13.75,
                         0,18.75,10,15);
     if( intersect(code) )
     { System.out.println( "ERROR PARALLEL SLOPE=.75: INTERSECTS" ); }
     else
     { System.out.println( "OK PARALLEL SLOPE=.75: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,0,1,1,
                         2,-1,2,10);
     if( intersect(code) )
     { System.out.println( "ERROR SEPERATE SEGMENTS: INTERSECTS" ); }
     else
     { System.out.println( "OK SEPERATE SEGMENTS: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,0,1,1,
                         -1,-10,-5,10);
     if( intersect(code) )
     { System.out.println( "ERROR SEPERATE SEGMENTS 2: INTERSECTS" ); }
     else
     { System.out.println( "OK SEPERATE SEGMENTS 2: DO NOT INTERSECT" ); }
  }

  public static boolean intersect( TestCode code )
  {
    return intersect( code.s1, code.s2);
  }

  public static boolean intersect( Line line1, Line line2 )
  {
    double i1min = Math.min(line1.p1.x, line1.p2.x);
    double i1max = Math.max(line1.p1.x, line1.p2.x);
    double i2min = Math.min(line2.p1.x, line2.p2.x);
    double i2max = Math.max(line2.p1.x, line2.p2.x);

    double iamax = Math.max(i1min, i2min);
    double iamin = Math.min(i1max, i2max);

    if( Math.max(line1.p1.x, line1.p2.x) < Math.min(line2.p1.x, line2.p2.x) )
      return false;

    double m1 = (line1.p2.y - line1.p1.y) / (line1.p2.x - line1.p1.x );
    double m2 = (line2.p2.y - line2.p1.y) / (line2.p2.x - line2.p1.x );

    if( m1 == m2 )
        return false;

    //b1 = line1[0][1] - m1 * line1[0][0]
    //b2 = line2[0][1] - m2 * line2[0][0]
    double b1 = line1.p1.y - m1 * line1.p1.x;
    double b2 = line2.p1.y - m2 * line2.p1.x;
    double x1 = (b2 - b1) / (m1 - m2);
    if( (x1 < Math.max(i1min, i2min)) || (x1 > Math.min(i1max, i2max)) )
        return false;
    return true;
  }
}

La salida hasta ahora es

ERROR COLINEAR: DO NOT INTERSECT
ERROR COLINEAR: DO NOT INTERSECT
ERROR COLINEAR: DO NOT INTERSECT
ERROR COLINEAR: DO NOT INTERSECT
ERROR COLINEAR: DO NOT INTERSECT
OK SLOPE END: INTERSECTS
OK SLOPE Intersect(0,0): INTERSECTS
OK SLOPE Line2 VERTIAL: INTERSECTS
OK SLOPE Line2 (reversed) VERTIAL: INTERSECTS
OK PARALLEL VERTICAL: DO NOT INTERSECT
OK PARALLEL HORIZONTAL: DO NOT INTERSECT
OK PARALLEL SLOPE=.75: DO NOT INTERSECT
OK SEPERATE SEGMENTS: DO NOT INTERSECT
OK SEPERATE SEGMENTS 2: DO NOT INTERSECT

Pensé en contribuir con una buena solución Swift:

struct Pt {
    var x: Double
    var y: Double
}

struct LineSegment {
    var p1: Pt
    var p2: Pt
}

func doLineSegmentsIntersect(ls1: LineSegment, ls2: LineSegment) -> Bool {

    if (ls1.p2.x-ls1.p1.x == 0) { //handle vertical segment1
        if (ls2.p2.x-ls2.p1.x == 0) {
            //both lines are vertical and parallel
            return false
        }

        let x = ls1.p1.x

        let slope2 = (ls2.p2.y-ls2.p1.y)/(ls2.p2.x-ls2.p1.x)
        let c2 = ls2.p1.y-slope2*ls2.p1.x

        let y = x*slope2+c2 // y intersection point

        return (y > ls1.p1.y && x < ls1.p2.y) || (y > ls1.p2.y && y < ls1.p1.y) // check if y is between y1,y2 in segment1
    }

    if (ls2.p2.x-ls2.p1.x == 0) { //handle vertical segment2

        let x = ls2.p1.x

        let slope1 = (ls1.p2.y-ls1.p1.y)/(ls1.p2.x-ls1.p1.x)
        let c1 = ls1.p1.y-slope1*ls1.p1.x

        let y = x*slope1+c1 // y intersection point

        return (y > ls2.p1.y && x < ls2.p2.y) || (y > ls2.p2.y && y < ls2.p1.y) // validate that y is between y1,y2 in segment2

    }

    let slope1 = (ls1.p2.y-ls1.p1.y)/(ls1.p2.x-ls1.p1.x)
    let slope2 = (ls2.p2.y-ls2.p1.y)/(ls2.p2.x-ls2.p1.x)

    if (slope1 == slope2) { //segments are parallel
        return false
    }

    let c1 = ls1.p1.y-slope1*ls1.p1.x
    let c2 = ls2.p1.y-slope2*ls2.p1.x

    let x = (c2-c1)/(slope1-slope2)

    return (((x > ls1.p1.x && x < ls1.p2.x) || (x > ls1.p2.x && x < ls1.p1.x)) &&
        ((x > ls2.p1.x && x < ls2.p2.x) || (x > ls2.p2.x && x < ls2.p1.x)))
    //validate that x is between x1,x2 in both segments

}

Una de las soluciones anteriores funcionó tan bien que decidí escribir un programa de demostración completo usando wxPython. Debería poder ejecutar este programa así: python " su nombre de archivo "

# Click on the window to draw a line.
# The program will tell you if this and the other line intersect.

import wx

class Point:
    def __init__(self, newX, newY):
        self.x = newX
        self.y = newY

app = wx.App()
frame = wx.Frame(None, wx.ID_ANY, "Main")
p1 = Point(90,200)
p2 = Point(150,80)
mp = Point(0,0) # mouse point
highestX = 0


def ccw(A,B,C):
    return (C.y-A.y) * (B.x-A.x) > (B.y-A.y) * (C.x-A.x)

# Return true if line segments AB and CD intersect
def intersect(A,B,C,D):
    return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)

def is_intersection(p1, p2, p3, p4):
    return intersect(p1, p2, p3, p4)

def drawIntersection(pc):
    mp2 = Point(highestX, mp.y)
    if is_intersection(p1, p2, mp, mp2):
        pc.DrawText("intersection", 10, 10)
    else:
        pc.DrawText("no intersection", 10, 10)

def do_paint(evt):
    pc = wx.PaintDC(frame)
    pc.DrawLine(p1.x, p1.y, p2.x, p2.y)
    pc.DrawLine(mp.x, mp.y, highestX, mp.y)
    drawIntersection(pc)

def do_left_mouse(evt):
    global mp, highestX
    point = evt.GetPosition()
    mp = Point(point[0], point[1])
    highestX = frame.Size[0]
    frame.Refresh()

frame.Bind(wx.EVT_PAINT, do_paint)
frame.Bind(wx.EVT_LEFT_DOWN, do_left_mouse)
frame.Show()
app.MainLoop()

Usando la solución OMG_Peanuts , traduje a SQL. (Función escalar de HANA)

Gracias OMG_Peanuts, funciona muy bien. Estoy usando tierra redonda, pero las distancias son pequeñas, así que creo que está bien.

FUNCTION GA_INTERSECT" ( IN LAT_A1 DOUBLE,
         IN LONG_A1 DOUBLE,
         IN LAT_A2 DOUBLE,
         IN LONG_A2 DOUBLE,
         IN LAT_B1 DOUBLE,
         IN LONG_B1 DOUBLE,
         IN LAT_B2 DOUBLE,
         IN LONG_B2 DOUBLE) 
    
RETURNS RET_DOESINTERSECT DOUBLE
    LANGUAGE SQLSCRIPT
    SQL SECURITY INVOKER AS
BEGIN

    DECLARE MA DOUBLE;
    DECLARE MB DOUBLE;
    DECLARE BA DOUBLE;
    DECLARE BB DOUBLE;
    DECLARE XA DOUBLE;
    DECLARE MAX_MIN_X DOUBLE;
    DECLARE MIN_MAX_X DOUBLE;
    DECLARE DOESINTERSECT INTEGER;
    
    SELECT 1 INTO DOESINTERSECT FROM DUMMY;
    
    IF LAT_A2-LAT_A1 != 0 AND LAT_B2-LAT_B1 != 0 THEN
        SELECT (LONG_A2 - LONG_A1)/(LAT_A2 - LAT_A1) INTO MA FROM DUMMY; 
        SELECT (LONG_B2 - LONG_B1)/(LAT_B2 - LAT_B1) INTO MB FROM DUMMY;
        IF MA = MB THEN
            SELECT 0 INTO DOESINTERSECT FROM DUMMY;
        END IF;
    END IF;
    
    SELECT LONG_A1-MA*LAT_A1 INTO BA FROM DUMMY;
    SELECT LONG_B1-MB*LAT_B1 INTO BB FROM DUMMY;
    SELECT (BB - BA) / (MA - MB) INTO XA FROM DUMMY;
    
    -- Max of Mins
    IF LAT_A1 < LAT_A2 THEN         -- MIN(LAT_A1, LAT_A2) = LAT_A1
        IF LAT_B1 < LAT_B2 THEN        -- MIN(LAT_B1, LAT_B2) = LAT_B1
            IF LAT_A1 > LAT_B1 THEN       -- MAX(LAT_A1, LAT_B1) = LAT_A1
                SELECT LAT_A1 INTO MAX_MIN_X FROM DUMMY;
            ELSE                          -- MAX(LAT_A1, LAT_B1) = LAT_B1
                SELECT LAT_B1 INTO MAX_MIN_X FROM DUMMY;
            END IF;
        ELSEIF LAT_B2 < LAT_B1 THEN   -- MIN(LAT_B1, LAT_B2) = LAT_B2
            IF LAT_A1 > LAT_B2 THEN       -- MAX(LAT_A1, LAT_B2) = LAT_A1
                SELECT LAT_A1 INTO MAX_MIN_X FROM DUMMY;
            ELSE                          -- MAX(LAT_A1, LAT_B2) = LAT_B2
                SELECT LAT_B2 INTO MAX_MIN_X FROM DUMMY;
            END IF;
        END IF;
    ELSEIF LAT_A2 < LAT_A1 THEN     -- MIN(LAT_A1, LAT_A2) = LAT_A2
        IF LAT_B1 < LAT_B2 THEN        -- MIN(LAT_B1, LAT_B2) = LAT_B1
            IF LAT_A2 > LAT_B1 THEN       -- MAX(LAT_A2, LAT_B1) = LAT_A2
                SELECT LAT_A2 INTO MAX_MIN_X FROM DUMMY;
            ELSE                          -- MAX(LAT_A2, LAT_B1) = LAT_B1
                SELECT LAT_B1 INTO MAX_MIN_X FROM DUMMY;
            END IF;
        ELSEIF LAT_B2 < LAT_B1 THEN   -- MIN(LAT_B1, LAT_B2) = LAT_B2
            IF LAT_A2 > LAT_B2 THEN       -- MAX(LAT_A2, LAT_B2) = LAT_A2
                SELECT LAT_A2 INTO MAX_MIN_X FROM DUMMY;
            ELSE                          -- MAX(LAT_A2, LAT_B2) = LAT_B2
                SELECT LAT_B2 INTO MAX_MIN_X FROM DUMMY;
            END IF;
        END IF;
    END IF;
    
    -- Min of Max
    IF LAT_A1 > LAT_A2 THEN         -- MAX(LAT_A1, LAT_A2) = LAT_A1
        IF LAT_B1 > LAT_B2 THEN        -- MAX(LAT_B1, LAT_B2) = LAT_B1
            IF LAT_A1 < LAT_B1 THEN       -- MIN(LAT_A1, LAT_B1) = LAT_A1
                SELECT LAT_A1 INTO MIN_MAX_X FROM DUMMY;
            ELSE                          -- MIN(LAT_A1, LAT_B1) = LAT_B1
                SELECT LAT_B1 INTO MIN_MAX_X FROM DUMMY;
            END IF;
        ELSEIF LAT_B2 > LAT_B1 THEN   -- MAX(LAT_B1, LAT_B2) = LAT_B2
            IF LAT_A1 < LAT_B2 THEN       -- MIN(LAT_A1, LAT_B2) = LAT_A1
                SELECT LAT_A1 INTO MIN_MAX_X FROM DUMMY;
            ELSE                          -- MIN(LAT_A1, LAT_B2) = LAT_B2
                SELECT LAT_B2 INTO MIN_MAX_X FROM DUMMY;
            END IF;
        END IF;
    ELSEIF LAT_A2 > LAT_A1 THEN     -- MAX(LAT_A1, LAT_A2) = LAT_A2
        IF LAT_B1 > LAT_B2 THEN        -- MAX(LAT_B1, LAT_B2) = LAT_B1
            IF LAT_A2 < LAT_B1 THEN       -- MIN(LAT_A2, LAT_B1) = LAT_A2
                SELECT LAT_A2 INTO MIN_MAX_X FROM DUMMY;
            ELSE                          -- MIN(LAT_A2, LAT_B1) = LAT_B1
                SELECT LAT_B1 INTO MIN_MAX_X FROM DUMMY;
            END IF;
        ELSEIF LAT_B2 > LAT_B1 THEN   -- MAX(LAT_B1, LAT_B2) = LAT_B2
            IF LAT_A2 < LAT_B2 THEN       -- MIN(LAT_A2, LAT_B2) = LAT_A2
                SELECT LAT_A2 INTO MIN_MAX_X FROM DUMMY;
            ELSE                          -- MIN(LAT_A2, LAT_B2) = LAT_B2
                SELECT LAT_B2 INTO MIN_MAX_X FROM DUMMY;
            END IF;
        END IF;
    END IF;
        
    
    IF XA < MAX_MIN_X OR
       XA > MIN_MAX_X THEN  
       SELECT 0 INTO DOESINTERSECT FROM DUMMY;
    END IF;
    
    RET_DOESINTERSECT := :DOESINTERSECT;
END;

Resuelto pero aún por qué no con Python ... :)

def islineintersect(line1, line2):
    i1 = [min(line1[0][0], line1[1][0]), max(line1[0][0], line1[1][0])]
    i2 = [min(line2[0][0], line2[1][0]), max(line2[0][0], line2[1][0])]
    ia = [max(i1[0], i2[0]), min(i1[1], i2[1])]
    if max(line1[0][0], line1[1][0]) < min(line2[0][0], line2[1][0]):
        return False
    m1 = (line1[1][1] - line1[0][1]) * 1. / (line1[1][0] - line1[0][0]) * 1.
    m2 = (line2[1][1] - line2[0][1]) * 1. / (line2[1][0] - line2[0][0]) * 1.
    if m1 == m2:
        return False
    b1 = line1[0][1] - m1 * line1[0][0]
    b2 = line2[0][1] - m2 * line2[0][0]
    x1 = (b2 - b1) / (m1 - m2)
    if (x1 < max(i1[0], i2[0])) or (x1 > min(i1[1], i2[1])):
        return False
    return True

Esta:

print islineintersect([(15, 20), (100, 200)], [(210, 5), (23, 119)])

Salida:

True

Y esto:

print islineintersect([(15, 20), (100, 200)], [(-1, -5), (-5, -5)])

Salida:

False