python - también - ¿Cómo puedo verificar si dos segmentos se cruzan?
segmentos ordenados (17)
Aquí está el código C para verificar si dos puntos están en los lados opuestos del segmento de línea. Usando este código puedes verificar si dos segmentos se cruzan también.
// 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));
}
¿Cómo puedo verificar 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.
Actualizar:
Aquí hay otro código python para verificar si los segmentos cerrados se cruzan. Es la versión reescrita del código de 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 hay una función de prueba para verificar que funcione.
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))
Calcule el punto de intersección de las líneas de sus segmentos (básicamente, para resolver un sistema de ecuaciones lineales), luego verifique si se encuentra entre los puntos inicial y final de sus segmentos.
Como no mencionas que deseas 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 quiere saber si las líneas se cruzan o no, puede hacerlo utilizando la ecuación de línea (ax + by + c = 0). El enfoque es el siguiente:
Comencemos con dos segmentos de línea: segmento 1 y segmento 2.
segment1 = [[x1,y1], [x2,y2]] segment2 = [[x3,y3], [x4,y4]]Verifique si los dos segmentos de línea tienen una longitud distinta de cero y segmentos distintos.
A partir de ahora, supongo que los dos segmentos son de longitud distinta de cero y 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 + by + c = 0. Ahora, calcule el valor de f = ax + by + c para los dos puntos del otro segmento de línea (repita esto para el otro segmento de línea también).
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);Ahora todo lo que queda son los diferentes casos. Si f = 0 para cualquier punto, entonces las dos líneas 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 son desiguales, los segmentos de línea se cruzan. Dependiendo de si desea considerar las líneas que se tocan como "intersecantes" o no, puede adaptar sus condiciones.
En base a excelentes respuestas de y aquí está un código completo de Python 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 en 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
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 las líneas co-lineales (también conocidos 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 producción 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
La ecuación de una línea es:
f(x) = A*x + b = y
Para un segmento, es exactamente lo mismo, excepto que x está incluido 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 en ambos intervalos I1 e I2, definidos de la siguiente manera:
I1 = [min(X1,X2), max(X1,X2)]
I2 = [min(X3,X4), max(X3,X4)]
Y podríamos decir que Xa está incluido en:
Ia = [max( min(X1,X2), min(X3,X4) ),
min( max(X1,X2), max(X3,X4) )]
Ahora, necesitamos verificar que este intervalo Ia existe:
if (max(X1,X2) < min(X3,X4))
return false; // There is no mutual abcisses
Entonces, tenemos dos fórmulas de línea y un intervalo mutuo. Sus fórmulas de línea son:
f1(x) = A1*x + b1 = y
f2(x) = A2*x + b2 = y
Como conseguimos 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) parado 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 hay que hacer es verificar que Xa esté incluido en Ia:
if ( (Xa < max( min(X1,X2), min(X3,X4) )) ||
(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.
No tiene que calcular exactamente dónde se cruzan los segmentos, sino solo 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, deberá encontrar la posición relativa de cada punto en el segmento "anclado" (OnLeft, OnRight o Collinear).
Después de hacerlo para ambos puntos, verifique que uno de los puntos sea OnLeft y el otro sea OnRight (o tal vez incluya la posición Collinear, si también desea incluir intersecciones incorrectas ).
A continuación, debe repetir el proceso con los roles de delimitador y segmentos separados.
Existe una intersección si, y solo si, uno de los puntos es OnLeft y el otro es OnRight. Vea este enlace para una explicación más detallada con imágenes de ejemplo para cada posible caso.
Implementar dicho método será mucho más fácil que implementar un método que encuentre el punto de intersección (dado el número de 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á utilizando alguna representación de coma flotante (lo que obviamente podría complicar las cosas), entonces debe determinar algún valor épsilon para indicar "igualdad" (principalmente para la evaluación IsCollinear ).
// 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 comprobar que cada segmento establece "entre" el otro segmento (ya que estos son segmentos finitos, y no líneas infinitas).
Además, al usar estas funciones puedes entender si tienes una intersección adecuada o incorrecta .
- Correcto : 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 al segmento anclado).
Pensé en contribuir con una buena solución de 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
}
Resuelto, pero ¿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
Supongamos que los dos segmentos tienen puntos finales A, B y C, D. La forma numéricamente robusta para 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 al de la derecha, pero no es necesario que exista ninguna relación entre las dos líneas. Básicamente, se está comprobando cada punto de un segmento contra el otro segmento para asegurarse de que se encuentran en lados opuestos de la línea definida por el otro segmento.
Vea aquí: http://www.cs.cmu.edu/~quake/robust.html
También podemos resolver esto utilizando vectores.
Definamos los segmentos como [start, end] . Dado dos de tales segmentos [A, B] y [C, D] que tienen una longitud distinta de cero, podemos elegir uno de los puntos finales que se utilizarán 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]]
Desde allí, podemos buscar una intersección calculando t y 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 lo 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
Tienes dos segmentos de línea. Defina un segmento por puntos finales A y B y el segundo segmento por los puntos finales 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. El código bueno también observará las líneas paralelas).
El truco es 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.
Como esto es tarea, no te daré una solución explícita. Pero una prueba simple para ver de qué lado de una línea cae un punto, es usar un producto de puntos. Por lo tanto, para un CD de línea dado, 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 un vector normal N_A. Compara los signos de
dot(C-A,N_A)
y
dot(D-A,N_A)
Te dejaré que descubras cómo calcular un vector normal. (En 2-d, eso es trivial, pero ¿su código se preocupará si A y B son puntos distintos? Del mismo modo, ¿C y D son distintos?)
Todavía debe preocuparse por los segmentos de línea que se encuentran a lo largo de la misma línea infinita, o si un punto en realidad cae en el segmento de la otra línea. El buen código atenderá a todos los problemas posibles.
User @ i_4_got apunta a esta página con una solución muy eficiente en Python. La reproduzco aquí por conveniencia (ya que me hubiera alegrado tenerla 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)
para los segmentos AB y CD, encuentre la pendiente del CD
slope=(Dy-Cy)/(Dx-Cx)
extienda CD sobre A y B, y tome la distancia al CD que va hacia arriba
dist1=slope*(Cx-Ax)+Ay-Cy
dist2=slope*(Dx-Ax)+Ay-Dy
verificar si están en lados opuestos
return dist1*dist2<0
si sus datos definen la línea, solo tiene que demostrar que no son paralelos. Para hacer esto puedes 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, debes probar que no son lo mismo. Para eso, calcula
beta = y1 - alpha*x1
Si beta es la misma 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 describió anteriormente para cada línea. Luego debe verificar que (beta1 - beta2) / (alfa1 - alfa2) sea mayor que Min (x1_line1, x2_line1) y menor que Max (x1_line1, x2_line1)