提问人：Feliks 提问时间：5/31/2021 最后编辑：Feliks 更新时间：5/31/2021 访问量：1498
如何确定两条二维线段是否重叠？
How to determine if two 2D line segments are overlap?
问：
我正在处理一项任务（使用 python3），该任务需要检查 2 个线段是否重叠并可以返回 2 个端点。线段的坐标为 （x1， y1， x2， y2） 形式，其中 （x1，y1） 和 （x2，y2） 是其端点的坐标。 这两条线彼此非常接近，但可能不平行。您可以查看图片以了解哪种情况称为重叠。我认为重叠定义可以说是“如果一个点的投影位于另一条线的 2 个端点之间” 例：
overlap1 = numpy.array([[1,4,5,5], [7,7,3,5]])
overlap2 = numpy.array([[8,1,12,2], [9,2,11,3]])
non_overlap = numpy.array([[1,2,5,3], [6,3,9,4]])
我的目标是找到 4 个点中最远的 2 个点，如果它们重叠，如图中红色圆圈所示。目前我的想法是：
- 计算与所有点（AB、AC、AD、BC、BD、CD）的距离，以及 检查以查找最大距离，称为max_len
- 计算：test = len_AB + len_CD - max_len
- 如果测试> 0，则它们是重叠的，否则它们不是重叠的
这个 alg 可以很好地检查重叠条件，但很难返回 2 个最端点。
你怎么看这个问题？谢谢。
答：
0赞
Bruno Takara
5/31/2021
#1
看起来您只是使用 x 坐标，因此如果 A<C<B<D 或 A<C<D<B ir 重叠，否则不会（例如 A<B<C<D）
评论
0赞
Bruno Takara
5/31/2021
也许使用 [0][0] 表示 A，使用 [0][2] 表示 B，使用 [1][0] 表示 C，使用 [1][2] 表示 D，并进行这些不等式比较
0赞
Feliks
5/31/2021
谢谢！。这可能是一个需要考虑的问题，但我的问题似乎在垂直轴上有情况，所以我最好找到一种更通用的方法。
1赞
MBo
5/31/2021
#2
考虑下一个代码，用于计算点投影到线段上的相对位置。它使用点（标量）乘积。(xp, yp)(x1y1-x2y2)
当段实际上是一个点时返回None
当投影位于线段内时返回参数0..1
如果投影位于线段之外的线上，则返回此间隔外的值。所以负值 和 是你的红色圆圈点。> 1
（图片与另一个点名称）
def proj(x1, y1, x2, y2, xp, yp):
x12 = x2 - x1
y12 = y2 - y1
dotp = x12 * (xp - x1) + y12 * (yp - y1)
dot12 = x12 * x12 + y12 * y12
if dot12:
return dotp / dot12
else:
return None
评论
0赞
Feliks
5/31/2021
谢谢。使用直线点投影是我的第一个想法，但我犹豫了，因为在极端情况下，我需要找到所有 4 个点的投影。我已经在下面的答案中发布了我的解决方案。如果你有时间，我希望你能看一看，如果有什么问题，可以辩论一下。谢谢！
1赞
Feliks
5/31/2021
#3
感谢您阅读我的问题。我认为这更像是一个关于数学而不是编程的问题，但过了一段时间，我找到了一个很好的简单算法来处理它。我的解决方案主要基于 python 中的 numpy 数组进行高效计算。我不确定是否有更好的方法和更多的数学方法，但希望这个解决方案在未来仍然有用。
这个想法是找到与所有点组合的距离（从 6 个点有 4 个距离）。我创建了该组合的 numpy 数组，找到欧几里得距离，找到与该距离的最大距离，并按条件检查重叠：len_AB + len_CD - max（distance）。
import numpy as np
def check_overlap(line1, line2):
combination = np.array([line1,
line2,
[line1[0], line1[1], line2[0], line2[1]],
[line1[0], line1[1], line2[2], line2[3]],
[line1[2], line1[3], line2[0], line2[1]],
[line1[2], line1[3], line2[2], line2[3]]])
distance = np.sqrt((combination[:,0] - combination[:,2])**2 + (combination[:,1] - combination[:,3])**2)
max = np.amax(distance)
overlap = distance[0] + distance[1] - max
endpoint = combination[np.argmax(distance)]
return (overlap >= 0), endpoint
评论