查找段是否在另一个段的距离内

Question

我有一堆线段（我拥有的数据是构成线段 [x1,y1] 和 [x2, y2] 的 2 个点），我想根据它们的位置对它们进行分类。如果一个片段与另一个片段足够接近，那么我想将它们放在一起。如果我必须用一句话来描述它：我想找到距离该段的任何一点 5px 的所有邻居段。

规则与画图相似：

我正在研究不同的算法，但大多数算法都处理交点并预测线是否会相交。这对我来说真的不起作用，因为我不想将线条延伸到无穷大，我只想知道它们之间的距离是否在 5px 以内。

有谁知道我如何解决这个问题（而且速度相对较快）？您知道任何可以提供帮助的框架吗？（我正在寻找最近的邻居，但我找不到任何处理几何而不是点的框架）。

谢谢！

Answer 1

（我已经修改了我以前的答案。那个答案有一些缺点。我认为我的新答案显示了一个更简单和更强大的解决方案。）

你有两个线段，S 有点 S₀ 和 S₁ 和 T 有点 T₀ 和 T₁。当这些段在一点上的距离小于 r 时，就会检测到碰撞。

对于线段S，你得到方向向量Δs，线段长度s和归一化方向向量u.

Δs = S₁ − S₀
s = |Δs|
u = Δs / s

单位向量u和点S₀可以描述任意点P到点P′的变换：

P′_x = (P_x − S_0x) · u_x + (P_y − S_0y) · u_y
P′_y = − (P_x − S_0x) · u_y + (P_y − S_0y) · u_x

在此转换中，线段 S 的点为：

S′₀ = (0, 0)
S′₁ = (s, 0)

对于变换点T′₀和T′₁，y分量可以解释为到S的有符号距离。现在可以执行几个测试：

首先检验T′₀或T′₁是否在[=48的距离内=]r 线段 S 或在 S₀′ 或 S_{的 r 半径内1}′。如果是这样，我们就成功了。
接下来测试两条线是否相交。这只有在 T′_0y 或 T′_1y 的符号不同时才会发生。如果是这样，我们就成功了。
对于最后一个测试，我们通过在 T 与 x 轴对齐的系统中将 S 转换为 S'' 来反转第一个测试。然后测试其中一个变换点S′′₀或S′′₁是否在r内T''。如果是这样，我们就成功了，否则就是失败了。

Python 代码如下。我也更新了我的 JS Fiddle.

备注：

我旧答案中的纵向变量a和距离d实际上与x相同' 和 y' 在这里。我觉得改造比较简单
此解决方案仅测试 (1) T 的点是否在距 S 的 r 的距离内，(2) 线是否相交以及 ( 3）S的点是否在T的r距离内。共线线段的情况被测试（1）和（3）捕获。
下面的代码不处理零长度段（S₀ = S₁ 或 T₀ = T₁) 明确地，但是返回一个非空向量作为空向量的范数似乎可以解决问题——测试 (1) 和 ( 3) 抓住这些案例。

Python代码：

import math

class Point:
    """ A point P(x, y) in 2D space
    """

    def __init__(self, x, y):
        self.x = float(x)
        self.y = float(y)

class Vector:
    """ A vector v(x, y) in 2D space
    """

    def __init__(self, x, y):
        self.x = x
        self.y = y
    
    def mag(self):
        """ magnitude of the vector
        """
        
        return math.hypot(self.x, self.y)
    
    def norm(self):
        """ return the normalized vector or (0, 0)
        """
    
        a = self.mag()
        
        if a*a < 1.0e-16:
            return Vector(1, 0)
        
        return Vector(self.x / a, self.y / a)
    


def diff(p, q):
    """ difference vector (q - p)
    """

    return Vector(q.x - p.x, q.y - p.y)

def within(p, dx, r):
    """ Is p within r of point (dx, 0)?
    """

    x = p.x - dx
    y = p.y
    
    return x*x + y*y <= r*r

def rot(p, u):
    """ Rotate point p to a coordinate system aligned with u.
    """

    return Point(p.x * u.x + p.y * u.y,
                -p.x * u.y + p.y * u.x)

def collision(s, t, r):
    """ Do the line segments s and t collide with a radius r
    """

    ds = diff(s[0], s[1])
    ss = ds.mag()    
    u = ds.norm()
    
    a0 = rot(diff(s[0], t[0]), u)
    a1 = rot(diff(s[0], t[1]), u)

    # Test T0 and T1 against S
    
    if -r <= a0.y <= r and -r <= a0.x <= ss + r:
        if a0.x < 0: return within(a0, 0, r)
        if a0.x > ss: return within(a0, ss, r)
        return True    
    
    if -r <= a1.y <= r and -r <= a1.x <= ss + r:
        if a1.x < 0: return within(a1, 0, r)
        if a1.x > ss: return within(a1, ss, r)
        return True

    # Test intersection
    
    if a0.y * a1.y < -0.9 * r * r:
        a = -a0.y * (a1.x - a0.x) / (a1.y - a0.y) + a0.x
        
        if 0 <= a <= ss: return True

    # Test S0 and S1 against T
    
    dt = diff(t[0], t[1])
    tt = dt.mag()    
    v = dt.norm()
    
    b0 = rot(diff(t[0], s[0]), v)
    b1 = rot(diff(t[0], s[1]), v)

    if 0 <= b0.x <= tt and -r <= b0.y <= r: return True
    if 0 <= b1.x <= tt and -r <= b1.y <= r: return True
       
    return False

查找段是否在另一个段的距离内

Find if segment comes within distance of another one

python

algorithm

geometry

categorization