Найдите, находится ли сегмент на расстоянии другого

Единичный вектор u и точка S₀ могут описывать преобразование любой точки P в точку P′:

P′_x =   (P_x − S_0x) · u_x + (P_{y< /sub> − S0y) · uy
    P′y = − (Px − S0x) · uy + (Py − S0y) · ux< /под>}

В этом преобразовании точками отрезка S являются:

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

Для преобразованных точек T′₀ и T′₁ компоненты y можно интерпретировать как расстояние со знаком до S. Теперь можно выполнить несколько тестов:

• Первый тест заключается в том, находятся ли T'₀ или T'₁ на расстоянии r от сегмента S или в пределах радиуса r из S₀′ или S₁′. Если да, то у нас есть хит.

• Следующий тест — пересекаются ли две прямые. Это может произойти только в том случае, если знаки T′_0y или T′_1y различны. Если да, то у нас есть хит.

• Для последнего теста мы обращаем первый тест, преобразовывая S в S'' в системе, где T выровнен по оси x. Затем проверьте, находится ли одна из преобразованных точек S′′₀ или S′′₁ в пределах r от T′′. Если да, то у нас есть попадание, иначе — промах.

Код Python ниже. Я также обновил свой JS Fiddle.

Заметки:

• Продольная переменная a и расстояние d в моем старом ответе фактически были такими же, как x' и y' здесь. Я думаю, что трансформация проще.

• Это решение проверяет только (1) находятся ли точки T на расстоянии r от S, (2) пересекаются ли прямые и (3) находятся ли точки S на расстоянии < em>r из T. Случай коллинеарных отрезков улавливается тестами (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