如何判断两条二维线段是否重叠？

Question

我正在处理一项任务（使用 python3），它需要检查 2 条线段是否重叠并且可以 return 2 个端点。线段的坐标为 (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 个点，如图中红色圆圈所示。目前我的想法是：

计算与所有点（AB、AC、AD、BC、BD、CD）的距离和检查以找到最大距离，称为 max_len
计算：test = len_AB + len_CD - max_len
如果 test > 0，则它们是重叠的，否则它们不是

此算法非常适合检查重叠条件，但难以return 2 个最端点。

你怎么看待这个问题？谢谢。

Answer 1

看起来你只是使用x坐标，所以如果A

Answer 2

考虑下一个代码，用于计算点 (xp, yp) 投影到 (x1y1-x2y2) 线段的相对位置。它使用点（标量）积。

Returns None当段真的是一个点

Returns 参数 0..1 当投影位于段内时

如果投影位于线段之外的线上，则

Returns 值偏离此间隔。所以负值和 > 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 3

感谢您阅读我的问题。我认为这更多的是关于数学而不是编程问题，但过了一段时间，我找到了一个很好的简单算法来处理它。我的解决方案主要基于 python 中的 numpy 数组以进行高效计算。我不确定是否有更多数学方法的更好方法，但希望这个解决方案在未来仍然有用。

思路是求所有点组合的距离（4个点有6个距离）。我创建了一个该组合的 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

如何判断两条二维线段是否重叠？

How to determine if two 2D line segments are overlap?

python

language-agnostic

geometry

line