我已经使用了这里发布的代码。这是代码：
from __future__ import division
def line(p1, p2):
A = (p1[1] - p2[1])
B = (p2[0] - p1[0])
C = (p1[0]*p2[1] - p2[0]*p1[1])
return A, B, -C
def intersection(L1, L2):
D = L1[0] * L2[1] - L1[1] * L2[0]
Dx = L1[2] * L2[1] - L1[1] * L2[2]
Dy = L1[0] * L2[2] - L1[2] * L2[0]
if D != 0:
x = Dx / D
y = Dy / D
return x,y
else:
return False
# Usage
L1 = line([0,1], [2,3])
L2 = line([2,3], [0,4])
R = intersection(L1, L2)
if R:
print "Intersection detected:", R
else:
print "No single intersection point detected"
它实现了 Cramer 规则（适用于线条；如果为两条给定线条构建的线性方程的行列式为 0，则线条不相交）。然而，我遇到的问题是它还检测到由于手头两条线的延续而导致的交叉点。这是我使用的一个图matplotlib，它演示了这个问题：
我还有一个Triangle包含 3 个Line对象的类，它进一步说明了这个问题，因为该类也有自己的intersect(...)函数，它接受另一个三角形并检查两个三角形的哪些边相交以及在哪里：
我想使用链接中的算法检测线段相交。上述线段没有交点。我怎么做？
我有两个类 -Point和Line- 用于以更易读的方式处理这些几何元素。我维护了上面的脚本并将其包裹起来（请参阅 参考资料Line.intersect(...)）：
class Point:
def __init__(self, x, y, z):
self.x = x
self.y = y
self.z = z
# Override __add__, __sub__ etc. to allow arithmetic operations with Point objects
# ...
class Line:
def __init__(self, p1, p2):
self.p1 = p1
self.p2 = p2
# ...
def intersect(self, l):
def line(p1, p2):
A = (p1.y - p2.y)
B = (p2.x - p1.x)
C = (p1.x*p2.y - p2.x*p1.y)
return A, B, -C
L1 = line(self.p1, self.p2)
L2 = line(l.p1, l.p2)
D = L1[0]*L2[1] - L1[1]*L2[0]
Dx = L1[2]*L2[1] - L1[1]*L2[2]
Dy = L1[0]*L2[2] - L1[2]*L2[0]
if D != 0:
x = Dx / D
y = Dy / D
p = Point(x, y)
return True, p
return False, None
#Usage
l1 = Line(Point(0, 0), Point(10, 4))
l2 = Line(Point(-4, -3), Point(-4, 10))
res, p = l1.intersect(l2)
if not res:
print('Lines don\'t intersect')
else:
print('Lines intersect at [%f, %f]' % (p.x, p.y))
我也在寻找一个最佳的（尽可能少的非成本操作和尽可能少的内存占用）解决方案。
一种可能的解决方案是通过使用欧几里德距离来确定这些点是否位于两个线段上，从而过滤掉结果的交点（不属于两个线段的交叉点）。如果不是，则相交是一条或两条线连续的结果，应视为无效。然而，这是一项代价高昂的操作，并且还涉及考虑所有交点（无论该点是否是两个段的一部分）。
更新：我以为我已经解决了这个问题，但是唉！下面有问题。在仔细查看评论后，我看到了@JerryCoffin 发表的评论，他指出这篇文章可能存在重复：
def intersect(self, l, contious=False):
# Before anything else check if lines have a mutual abcisses
interval_1 = [min(self.p1.x, self.p2.x), max(self.p1.x, self.p2.x)]
interval_2 = [min(l.p1.x, l.p2.x), max(l.p1.x, l.p2.x)]
interval = [
min(interval_1[1], interval_2[1]),
max(interval_1[0], interval_2[0])
]
if interval_1[1] < interval_2[0]:
print('No mutual abcisses!')
return False, None
# Try to compute interception
def line(p1, p2):
A = (p1.y - p2.y)
B = (p2.x - p1.x)
C = (p1.x*p2.y - p2.x*p1.y)
return A, B, -C
L1 = line(self.p1, self.p2)
L2 = line(l.p1, l.p2)
D = L1[0]*L2[1] - L1[1]*L2[0]
Dx = L1[2]*L2[1] - L1[1]*L2[2]
Dy = L1[0]*L2[2] - L1[2]*L2[0]
if D != 0:
x = Dx / D
y = Dy / D
p = Point(x, y)
if contiuous: # continuous parameter allows switching between line and line segment interception
return True, p
else:
if p.x < interval[1] or p.x > interval[0]:
print('Intersection out of bound')
return False, None
else:
return True, p
else:
print('Not intersecting')
return False, None
结果：
这看起来不错，正是我想要的。但是我添加了一条线（坐标或多或少是随机的，但我很容易在图上检查）即Line(Point(-4, 12), Point(12, -4)). 想象一下当我再次得到一个误报时我的惊讶：
如您所见，在我的线段开头的左上角检测到一个交叉点。它确实与垂直线的延续相交，但与实际线段不相交。似乎两条线段相同而一条线段是垂直的这一事实构成了一个问题。所以我仍然不知道如何解决这个问题。x