如何检查两个线段是否相交？
- 2025-02-13 08:36:00
- admin 原创
- 49
问题描述：
如何检查两个线段是否相交？
我有以下数据：
Segment1 [ {x1,y1}, {x2,y2} ]
Segment2 [ {x1,y1}, {x2,y2} ]
我需要用 Python 编写一个小算法来检测两条线是否相交。
解决方案 1：
用户 @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)
解决方案 2：
直线方程为：
f(x) = A*x + b = y
对于一个线段来说，它完全相同，只是 x 包含在区间 I 内。
如果有两个段，定义如下：
Segment1 = {(X1, Y1), (X2, Y2)}
Segment2 = {(X3, Y3), (X4, Y4)}
潜在交点（Xa，Ya）的横线Xa必须包含在区间I1和I2内，定义如下：
I1 = [min(X1,X2), max(X1,X2)]
I2 = [min(X3,X4), max(X3,X4)]
我们可以说 Xa 包含在内：
Ia = [max( min(X1,X2), min(X3,X4) ),
min( max(X1,X2), max(X3,X4) )]
现在，我们需要检查这个区间 Ia 是否存在：
if (max(X1,X2) < min(X3,X4)):
return False # There is no mutual abcisses
因此，我们有两个直线公式和一个相互间隔。您的直线公式是：
f1(x) = A1*x + b1 = y
f2(x) = A2*x + b2 = y
由于我们按线段获得两个点，因此我们能够确定 A1、A2、b1 和 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
如果线段平行，则 A1 == A2 ：
if (A1 == A2):
return False # Parallel segments
位于两条线上的点 (Xa,Ya) 必须验证公式 f1 和 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
最后要做的是检查 Xa 是否包含在 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
除此之外，您还可以在启动时检查提供的四个点中两个点是否相等，以避免所有测试。
解决方案 3：
您不必精确计算线段相交的位置，只需了解它们是否相交。这将简化解决方案。
这个想法是将一个线段视为“锚点”，并将第二个线段分成 2 个点。
现在，您必须找到每个点相对于“锚点”线段的相对位置（OnLeft、OnRight 或 Collinear）。对两个点执行此操作后，检查其中一个点是否在 OnLeft，另一个点是否在 OnRight（或者，如果您还希望包含不正确的
交点
，则可能包括 Collinear 位置）。
然后您必须以锚点和分离段的角色重复该过程。
当且仅当其中一个点在左点，另一个点在右点时，才存在交点。请参阅此链接，获取更详细的解释，其中包含每种可能情况的示例图像。
实现这种方法比实际实现寻找交点的方法要容易得多（考虑到您还必须处理的许多极端情况）。
更新
以下函数应该可以说明这个想法（来源：C 语言中的计算几何）。
备注：此示例假设使用整数。如果您改用某种浮点表示（这显然会使事情变得复杂），那么您应该确定某个 epsilon 值来表示“相等”（主要用于评估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);
}
当然，在使用这些函数时，必须记住检查每个线段是否位于另一个线段“之间”（因为这些是有限线段，而不是无限线）。
此外，使用这些功能，您可以了解交叉点是否正确或不正确。
正确：没有共线点。线段“从一边到另一边”相互交叉。
不正确：一个线段仅“接触”另一个线段（至少一个点与锚定线段共线）。
解决方案 4：
假设两个线段的端点分别为 A、B 和 C、D。确定交点的数值稳健方法是检查四个行列式的符号：
| 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 |
对于交点，左侧的每个行列式必须与右侧的行列式具有相反的符号，但两条线之间不需要有任何关系。您基本上是将一个线段的每个点与另一个线段进行对比，以确保它们位于另一个线段定义的线的相对侧。
请参阅：http: //www.cs.cmu.edu/~quake/robust.html
解决方案 5：
以下是使用点积的解决方案：
# 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 中的可视化效果：线段相交
解决方案 6：
使用Shapely库的方法检查线段是否相交非常容易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
解决方案 7：
这是我检查线交叉点和交叉点位置的方法。让我们使用 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.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))))
解决方案 8：
根据Liran和Grumdrig 的出色回答，这里有一个完整的 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 \n is_point_in_closed_segment(a, b, c) or is_point_in_closed_segment(a, b, d) or \n 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
解决方案 9：
这是另一个用于检查封闭线段是否相交的 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))
解决方案 10：
您有两条线段。用端点 A 和 B 定义一条线段，用端点 C 和 D 定义第二条线段。有一个很好的技巧可以表明它们必须在线段的边界内相交。（请注意，线本身可能会在线段的边界之外相交，因此您必须小心。好的代码也会注意平行线。）
诀窍在于测试点 A 和 B 必须位于线 CD 的相对两侧，并且点 C 和 D 必须位于线 AB 的相对两侧。
由于这是家庭作业，我不会给你一个明确的解决方案。但是，要查看一个点落在直线的哪一侧，可以使用点积。因此，对于给定的直线 CD，计算该直线的法向量（我将其称为 N_C）。现在，只需测试这两个结果的符号：
dot(A-C,N_C)
和
dot(B-C,N_C)
如果这些结果的符号相反，则 A 和 B 位于直线 CD 的对侧。现在对另一条直线 AB 进行同样的测试。它的法向量为 N_A。比较
dot(C-A,N_A)
和
dot(D-A,N_A)
我让你自己去弄清楚如何计算法向量。（在二维中，这很简单，但你的代码会担心 A 和 B 是否是不同的点吗？同样，C 和 D 是否不同？）
您仍然需要担心位于同一条无限线上的线段，或者一个点实际上是否落在另一条线段本身上。好的代码会解决所有可能的问题。
解决方案 11：
以下是 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));
}
解决方案 12：
到目前为止， Georgy的答案是最容易实现的。必须追查这个问题，因为 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))
解决方案 13：
对于线段 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
解决方案 14：
由于您没有提到要找到直线的交点，因此问题变得更容易解决。如果您需要交点，那么OMG_peanuts的答案是一种更快的方法。但是，如果您只是想找出直线是否相交，您可以使用直线方程 (ax + by + c = 0) 来做到这一点。方法如下：
让我们从两条线段开始：线段 1 和线段 2。
segment1 = [[x1,y1], [x2,y2]]
segment2 = [[x3,y3], [x4,y4]]
检查两条线段是否为非零长度线和不同的线段。
从这里开始，我假设这两条线段的长度不为零且不同。对于每条线段，计算直线的斜率，然后得到 ax + by + c = 0 形式的直线方程。现在，计算另一条线段的两个点的 f = ax + by + c 的值（对另一条线段也重复此操作）。
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);
现在剩下的就是不同的情况。如果任何一点的 f = 0，则两条线在一点相切。如果 f1_1 和 f1_2 相等或 f2_1 和 f2_2 相等，则线不相交。如果 f1_1 和 f1_2 不相等且f2_1 和 f2_2 不相等，则线段相交。根据您是否想将相切的线视为“相交”，您可以调整条件。
解决方案 15：
我们也可以利用向量来解决这个问题。
我们将线段定义为[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]]
从那里，我们可以通过计算 中的 t 和 u 来寻找交点p + t*r = u*q。在稍微调整一下方程之后，我们得到：
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]) \n if (q[0]*r[1] - q[1]*r[0]) != 0 \n else (q[1]*p[0] - q[0]*p[1])
u = (p[0] + t*r[0])/q[0] \n if q[0] != 0 \n else (p[1] + t*r[1])/q[1]
return t >= 0 and t <= 1 and u >= 0 and u <= 1
解决方案 16：
上面的一个解决方案非常有效，我决定使用 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()
解决方案 17：
使用OMG_Peanuts解决方案，我将其翻译成 SQL。（HANA 标量函数）
谢谢 OMG_Peanuts，效果很好。我使用的是圆形地球，但距离很小，所以我觉得没问题。
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;
解决方案 18：
挖掘旧线程并修改 Grumdrig 的代码......
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;
解决方案 19：
如果有人想用 C 语言快速查找多条线的交点，你可以使用这个numba代码python
笔记
epsilon 参数应该与你的线距离成正比。此外，导入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
解决方案 20：
计算线段上的线的交点（这基本上意味着求解线性方程组），然后检查它是否位于线段的起点和终点之间。
解决方案 21：
这是我对 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();
}
解决方案 22：
我想我应该贡献一个不错的 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
}
解决方案 23：
这里有一些 Python 代码，可以解决所有共线性边缘情况和舍入误差问题。
epsilon = 0.000001
def is_intersecting(x1, y1, x2, y2, x3, y3, x4, y4):
c_area = area(x1, y1, x2, y2, x3, y3)
d_area = area(x1, y1, x2, y2, x4, y4)
if abs(c_area) < epsilon:
if abs(x3-x1) < epsilon:
if min(y1,y2)-epsilon < y3 < max(y1,y2)+epsilon:
return True
else:
if min(x1,x2)-epsilon < x3 < max(x1,x2)+epsilon:
return True
if abs(d_area) > epsilon:
return False
if abs(d_area) < epsilon:
if abs(x4-x1) < epsilon:
if min(y1,y2)-epsilon < y4 < max(y1,y2)+epsilon:
return True
else:
if min(x1,x2)-epsilon < x4 < max(x1,x2)+epsilon:
return True
if abs(c_area) > epsilon:
return False
if abs(x3-x1) < epsilon:
return (y1 < y3) != (y1 < y4)
else:
return (x1 < x3) != (x1 < x4)
if (c_area > 0) == (d_area > 0):
return False
a_area = area(x3, y3, x4, y4, x1, y1)
b_area = area(x3, y3, x4, y4, x2, y2)
return (a_area > 0) != (b_area > 0)
def area(x1, y1, x2, y2, x3, y3):
return (x2-x1)*(y3-y1)-(x3-x1)*(y2-y1)
解决方案 24：
我尝试了这里前 3 个答案，但都不起作用，所以我用代数解决了这个问题，最终得到了以下结果。这是 Line 类中的一个方法，它检查自身是否与同一类的输入 Line 相交，所以不要介意将两者转换为元组的开始。
if self.p1.x < self.p2.x:
a = (self.p1, self.p2)
else:
a = (self.p2, self.p1)
# makes sure the first point is the left point for the inputted line
if b.p1.x < b.p2.x:
b = (b.p1, b.p2)
else:
b = (b.p2, b.p1)
# prevents infinite slopes with minor offsets
if a[0].x == a[1].x:
a[0].x -= 0.00000001
if b[0].x == b[1].x:
b[0].x -= 0.00000001
# finds the slopes
aSlope = (a[1].y - a[0].y) / (a[1].x - a[0].x)
bSlope = (b[1].y - b[0].y) / (b[1].x - b[0].x)
# finds the y-intercepts of both
aYint = a[1].y - aSlope*a[1].x
bYint = b[1].y - bSlope*b[1].x
if between(b[0].x,a[0].x,b[1].x) or between(b[0].x,a[1].x,b[1].x) or between(a[0].x,b[0].x,a[1].x) or between(a[0].x,b[1].x,a[1].x): # if the segments exist in the same x-range
if aSlope == bSlope: # if they are parallel then they never touch, unless they are the same line
return (aYint == bYint)
# finds the x location where the two lines intersect if they were unbounded
xLocation = (bYint - aYint)/(aSlope - bSlope)
# now we need to check if the xLocation is actually found on BOTH lines, if so, then they intersect, if not, then that means they have separate slopes, y-intercepts, and where they would overlap does exist at both lines.
return (between(b[0].x,xLocation,b[1].x) or between(b[0].x,xLocation,b[1].x)) and (between(a[0].x,xLocation,a[1].x) or between(a[0].x,xLocation,a[1].x))
解决方案 25：
如果你的数据定义了线，你只需要证明它们不是平行的。为此，你可以计算
alpha = float(y2 - y1) / (x2 - x1).
如果此系数对于 Line1 和 Line2 都相等，则表示该线是平行的。如果不相等，则表示它们将相交。
如果它们是平行的，那么你必须证明它们不相同。为此，你可以计算
beta = y1 - alpha*x1
如果 Line1 和 Line2 的 beta 值相同，则意味着它们相交
如果它们是线段，您仍然必须按照上述方法为每条线计算 alpha 和 beta。然后您必须检查 (beta1 - beta2) / (alpha1 - alpha2) 是否大于 Min(x1_line1, x2_line1) 且小于 Max(x1_line1, x2_line1)
解决方案 26：
用 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
解决方案 27：
已解决但为什么不使用 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
相关推荐
热门文章
项目管理软件有哪些？
热门标签
云禅道AD
