如何检查两段是否相交？

这是我为 AS3准备的，我不太了解 python，但是它的概念就在那里

    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();
}

对于 AB 段和 CD 段，求出 CD 段的斜率

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

把 CD 延伸到 A 和 B 上，然后沿着直线向上走到 CD 的距离

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

检查他们是否在对立面

return dist1*dist2<0

User@i _ 4 _ got 通过 Python 中的一个非常有效的解决方案指向 这一页。我在这里复制它是为了方便(因为它会让我很高兴把它放在这里) :

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)

解决了，但为什么不用 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

这个:

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

产出:

True

还有这个:

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

产出:

False

用 JAVA 实现。然而，它似乎不工作的共线性线(又名线段存在于彼此 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;
}
}

到目前为止的产出是

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

下面是 C 代码，用于检查两个点是否在线段的相反两侧。使用这段代码，您可以检查两个段是否也相交。

// 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));

}

基于 Liran 的和 格兰德里格酒吧，这里有一个完整的 Python 代码来验证 关门了段是否相交。工程共线部分，部分平行于轴 Y，退化部分(魔鬼在细节)。假设整数坐标。浮点坐标需要修改点相等性测试。

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

由于你没有提到你想找到这条直线的交点，这个问题就变得更容易解决了。如果你需要交点，那么 天啊，花生的答案是一个更快的方法。但是，如果您只想知道两条直线是否相交，那么可以使用直线方程(ax + by + c = 0)。方法如下:

1. 让我们从两个线段开始: 段1和段2。

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

2. Check if the two line segments are non zero length line and distinct segments.

3. From hereon, I assume that the two segments are non-zero length and distinct. For each line segment, compute the slope of the line and then obtain the equation of a line in the form of ax + by + c = 0. Now, compute the value of f = ax + by + c for the two points of the other line segment (repeat this for the other line segment as well).

   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. Now all that is left is the different cases. If f = 0 for any point, then the two lines touch at a point. If f1_1 and f1_2 are equal or f2_1 and f2_2 are equal, then the lines do not intersect. If f1_1 and f1_2 are unequal and f2_1 and f2_2 are unequal, then the line segments intersect. Depending on whether you want to consider the lines which touch as "intersecting" or not, you can adapt your conditions.

下面是另一个用于检查闭合段是否相交的 Python 代码。它是 http://www.cdn.geeksforgeeks.org/check-if-two-given-line-segments-intersect/中 C + + 代码的重写版本。此实现涵盖所有特殊情况(例如，所有点共线)。

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

下面是一个测试函数，用于验证它是否工作。

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))

我想我可以提供一个很好的解决方案:

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


}

我们也可以利用向量来解决这个问题。

让我们将这些段定义为 [start, end]。给定两个具有非零长度的片段 [A, B]和 [C, D]，我们可以选择其中一个端点作为参考点，这样我们就得到了三个矢量:

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]]

从这里，我们可以通过在 p + t*r = u*q中计算 t 和 u 来寻找交叉点。在对这个方程稍作修改之后，我们得到:

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]

因此，函数是:

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

这是我检查线路交叉点和交叉点的方法。让我们使用 x1到 x4和 y1到 y4

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

然后我们需要一些矢量来表示它们

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

现在我们来看行列式

det = dx1 * dy2 - dx2 * dy1

如果行列式为0.0，则线段是平行的。这可能意味着他们有重叠。如果它们仅在端点处重叠，则存在一个交叉解。否则将会有无限的解决方案。对于无穷多个解，你的交点是什么？所以这是个有趣的特例。如果你提前知道这些线不能重叠，那么你可以检查一下 det == 0.0，如果是这样，就说它们没有相交，然后就完成了。否则，让我们继续

dx3 = X1 - X3
dy3 = Y1 - Y3


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

现在，如果 det，det1和 det2都是零，那么你的线条是共线的，可能会重叠。如果 det 为零，但 det1或 det2不是，那么它们不是共线的，而是平行的，所以没有交集。如果 det 为零，剩下的就是一维问题而不是二维问题。我们将需要检查两种方法中的一种，这取决于 dx1是否为零(因此我们可以避免除以零)。如果 dx1为零，那么只需使用 y 值而不是下面的 x 执行相同的逻辑。

s = X3 / dx1
t = X4 / dx1

它计算两个定标器，如果我们把向量(dx1，dy1)缩放为 s，我们得到点(x3，y3) ，通过 t，我们得到(x4，y4)。所以如果 s 或 t 介于0.0和1.0之间，那么点3或4位于第一行。负数意味着点位于矢量起点的后面，而 > 1.0则意味着点位于矢量终点的前面。0表示它在(x1，y1) ，1.0表示它在(x2，y2)。如果 s 和 t 都 < 0.0或者都 > 1.0，则它们不相交。处理平行线的特殊情况。

现在，如果 det != 0.0

s = det1 / det
t = det2 / det
if s < 0.0 or s > 1.0 or t < 0.0 or t > 1.0:
return false  # no intersect

这和我们上面所做的非常相似。现在，如果我们通过上面的测试，然后我们的线段相交，我们可以很容易地计算交点，像这样:

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

如果你想更深入地研究数学是怎么做的，看看克莱默定律。

编辑: 我已经修正了两个错误，所以现在应该是正确的。我现在已经学会了足够多的 python 来编写实际的代码。除了一些特殊情况，它还是可以工作的，尽管它可以正确地处理一些特殊情况。特殊情况下真的很难处理，我已经花了足够的时间在上面，并希望继续前进。如果有人要求更好，那么他们至少有一个良好的起点来尝试和改进它。

import math


def line_intersection(line1, line2):
x1, x2, x3, x4 = line1[0][0], line1[1][0], line2[0][0], line2[1][0]
y1, y2, y3, y4 = line1[0][1], line1[1][1], line2[0][1], line2[1][1]


dx1 = x2 - x1
dx2 = x4 - x3
dy1 = y2 - y1
dy2 = y4 - y3
dx3 = x1 - x3
dy3 = y1 - y3


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


if det == 0.0:  # lines are parallel
if det1 != 0.0 or det2 != 0.0:  # lines are not co-linear
return None  # so no solution


if dx1:
if x1 < x3 < x2 or x1 > x3 > x2:
return math.inf  # infinitely many solutions
else:
if y1 < y3 < y2 or y1 > y3 > y2:
return math.inf  # infinitely many solutions


if line1[0] == line2[0] or line1[1] == line2[0]:
return line2[0]
elif line1[0] == line2[1] or line1[1] == line2[1]:
return line2[1]


return None  # no intersection


s = det1 / det
t = det2 / det


if 0.0 < s < 1.0 and 0.0 < t < 1.0:
return x1 + t * dx1, y1 + t * dy1


print("one intersection")
print(line_intersection(((0.0,0.0), (6.0,6.0)),((0.0,9.0), (9.0,0.0))))
print(line_intersection(((-2, -2), (2, 2)), ((2, -2), (-2, 2))))
print(line_intersection(((0.5, 0.5), (1.5, 0.5)), ((1.0, 0.0), (1.0, 2.0))))
print(line_intersection(((0, -1), (0, 0)), ((0, 0), (0, 1))))
print(line_intersection(((-1, 0), (0, 0)), ((0, 0), (1, 0))))


print()
print("no intersection")
print(line_intersection(((-1, -1), (0, 0)), ((2, -4), (2, 4))))
print(line_intersection(((0.0,0.0), (0.0,9.0)),((9.0,0.0), (9.0,99.0))))
print(line_intersection(((0, 0), (1, 1)), ((1, 0), (2, 1))))
print(line_intersection(((-1, 1), (0, 1)), ((0, 0), (1, 0))))
print(line_intersection(((1, -1), (1, 0)), ((0, 0), (0, -1))))


print()
print("infinite intersection")
print(line_intersection(((-1, -1), (1, 1)), ((0, 0), (2, 2))))
print(line_intersection(((-1, 0), (1, 0)), ((0, 0), (2, 0))))
print(line_intersection(((0, -1), (0, 1)), ((0, 0), (0, 2))))
print(line_intersection(((-1, 0), (0, 0)), ((0, 0), (-1, 0))))
print(line_intersection(((1, 0), (0, 0)), ((0, 0), (1, 0))))

使用 intersects方法，用 很好库检查线段是否相交是非常容易的:

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

上面的一个解决方案非常有效，我决定使用 wxPython 编写一个完整的演示程序。您应该能够像下面这样运行这个程序: python“ 你的文件名”

# 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()

到目前为止，格奥尔基给出的答案是最容易实现的。不得不追溯到这个例子，因为 brycboe 的例子虽然简单，但是有共线性的问题。

测试代码:

#!/usr/bin/python
#
# Notes on intersection:
#
# https://bryceboe.com/2006/10/23/line-segment-intersection-algorithm/
#
# https://stackoverflow.com/questions/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))

下面是一个使用点积的解决方案:

# 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)

下面是 Desmos 中的可视化: 线段相交

使用 我的天啊，花生解决方案，我翻译成 SQL。 (HANA 标量函数)

谢谢 OMG _ 花生，它工作得很好。 我用的是圆形的地球，但是距离很小，所以我觉得没关系。

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;

挖出一条旧线索，修改格兰德里格的代码。

template <typename T>
struct Point {
T x;
T y;
Point(T x_, T y_) : x(x_), y(y_) {};
};


template <typename T>
inline T CrossProduct(const Point<T>& pt1, const Point<T>& pt2, const Point<T>& pt3)
{
// nb: watch out for overflow
return ((pt2.x - pt1.x) * (pt3.y - pt2.y) - (pt2.y - pt1.y) * (pt3.x - pt2.x));
}


template <typename T>
bool SegmentsIntersect(const Point<T>& a, const Point<T>& b,
const Point<T>& c, const Point<T>& d)
{
return
CrossProduct(a, c, d) * CrossProduct(b, c, d) < 0 &&
CrossProduct(c, a, b) * CrossProduct(d, a, b) < 0;
}


if (SegmentsIntersect(Point<int>(50, 0), Point<int>(50, 100),
Point<int>(0, 50), Point<int>(100, 50)))
std::cout << "it works!" << std::endl;

如果有人想做一个 C 样的速度查找多条线的交叉口，你可以使用这个代码完成的 numba和 python

注意

Ε 参数应该和你的直线距离成正比, 进口只有 import numba和 import numpy as np

@numba.njit('float64[:,::1], float64[::1], float64', fastmath=True)
def nb_isBetween(line_ab, c, epsilon):
"""


:param line_ab: like --> np.array([[731362.47087528, 9746708.78767337], [731297.282, 9746727.286]])
:param c: point to check like --> np.array([731362.47087528, 9746708.78767337])
:param epsilon:
:return: check if points is on line or not netween point a and b
"""


a, b = line_ab
a_x, a_y = a
b_x, b_y = b
c_x, c_y = c


crossproduct = (c_y - a_y) * (b_x - a_x) - (c_x - a_x) * (b_y - a_y)


# compare versus epsilon for floating point values, or != 0 if using integers
if abs(crossproduct) > epsilon:
return False


dotproduct = (c_x - a_x) * (b_x - a_x) + (c_y - a_y) * (b_y - a_y)
if dotproduct < 0:
return False


squaredlengthba = (b_x - a_x) * (b_x - a_x) + (b_y - a_y) * (b_y - a_y)
if dotproduct > squaredlengthba:
return False


return True


@numba.njit('float64[:,::1], float64[:,::1]', fastmath=True)
def nb_get_line_intersect(line_ab, line_cd):
"""


:param line_ab: like --> np.array([[731362.47087528, 9746708.78767337], [731297.282, 9746727.286]])
:param line_cd: like --> np.array([[731362.47087528, 9746708.78767337], [731297.282, 9746727.286]])
:return: get point of intersection, if the points in on line ab or cd returns the point if not retunrs 0
"""
A, B = line_ab
C, D = line_cd


# a1x + b1y = c1
a1 = B[1] - A[1]
b1 = A[0] - B[0]
c1 = a1 * (A[0]) + b1 * (A[1])


# a2x + b2y = c2
a2 = D[1] - C[1]
b2 = C[0] - D[0]
c2 = a2 * (C[0]) + b2 * (C[1])


# determinant
det = a1 * b2 - a2 * b1


# parallel line
if det == 0:
return np.array([np.nan, np.nan])


# intersect point(x,y)
x = ((b2 * c1) - (b1 * c2)) / det
y = ((a1 * c2) - (a2 * c1)) / det


#check if x and y area in the line segment interval
if nb_isBetween(line_ab, np.array([x, y]), epsilon=0.001) and nb_isBetween(line_cd, np.array([x, y]), epsilon=0.001):
return np.array([x, y])
else:
return np.array([np.nan, np.nan])


@numba.njit('float64[:, :, ::1], float64[:, :, ::1]', parallel=True,  fastmath=True)
def nb_get_line_intersect(m_ramales_lines, interference_lines):
"""


:param m_ramales_lines: like --> np.array([[[731362.47087528, 9746708.78767337], [731297.282, 9746727.286]] , [[731297.282, 9746727.286], [ 731290.048, 9746724.403]]])
:param interference_lines: like --> np.array([[[731362.47087528, 9746708.78767337], [731297.282, 9746727.286]] , [[731297.282, 9746727.286], [ 731290.048, 9746724.403]]])
:return: m_ramales_lines x interference_lines x 2
"""
#empty matrix to fill
m_ramales_interference = np.empty(shape=(len(m_ramales_lines), len(interference_lines), 2))
for pos1 in range(len(m_ramales_lines)):
line_ab = m_ramales_lines[pos1]
for pos2 in numba.prange(len(interference_lines)):
# interference line
line_cd = interference_lines[pos2].T
# get crossing point
cross_point = nb_get_line_intersect(line_ab.copy(), line_cd.copy())
#fill 2D array
m_ramales_interference[pos1, pos2] = cross_point
return m_ramales_interference