如何确定两条二维线段是否重叠？

Question

我正在进行一项任务（使用python3），该任务需要检查两条线段是否重叠，并可以返回两个端点。线段具有（x1，y1，x2，y2）形式的坐标，其中（x1，y1）和（x2，y2）是其端点的坐标。 这两条线彼此非常接近，但可能不平行。您可以通过查看图片了解哪种情况称为重叠。我认为重叠定义可以说是“如果一个点的投影位于另一条线的两个端点之间” 例如：

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个点（如果它们重叠），如图中红色圆圈所示。目前我的想法是：

1. 计算到所有点（AB、AC、AD、BC、BD、CD）和 检查以找到最大距离，称为max_len
2. 计算：测试=长度AB+长度CD-最大长度
3. 如果测试>；0，则它们是重叠的，否则它们不是重叠的

这个alg可以很好地检查重叠情况，但很难返回最接近的两个端点

你对这个问题怎么看？多谢各位

Answer 1

考虑下一个计算点{^ }投影到^ {CD2>}线段相对位置的代码。它使用点（标量）积

当段实际上是一个点时返回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

Answer 2

看起来您只是在使用x坐标，因此如果A<；C<；B<；D或A<；C<；D<；B ir重叠，否则不会重叠（例如A<；B<；C<；D）

Answer 3

谢谢你阅读我的问题。我认为这更像是一个数学问题而不是编程问题，但过了一段时间，我找到了一个很好的简单算法来处理它。我的解决方案在很大程度上基于python中的numpy数组，以实现高效的计算。我不确定是否有更好的方法使用更多的数学方法，但希望这个解决方案在将来仍然有用

其思想是从所有点组合中找出距离（从4个点中找出6个距离）。我创建了一个组合的numpy数组，找到欧几里德距离，找到与它的最大距离，然后按条件检查重叠：len_AB+len_CD-max（距离）

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