两个线段之间的最短距离

Question

我需要一个函数来找到两个线段之间的最短距离.线段由两个端点定义.因此,例如我的一个线段(AB)将由两个点A(x1,y1)和B(x2,y2)定义,而另一个(CD)将由两个点C(x1,y1)定义和D(x2,y2).

随意用您想要的任何语言编写解决方案,我可以将其翻译成javascript.请记住,我的几何技能非常生疏.我已经在这里看到了,我不知道如何将其转换为函数.非常感谢你的帮助.

Answer 1

这是我在python中的解决方案.使用3d点,你可以简化2d.

[编辑1]如果要将结果限制为线段,我添加了一个钳位选项

[编辑2]正如DA指出的那样,因为两条线是平行的并不意味着它们之间不能有距离.所以我编辑了代码来处理这种情况.我还使钳位条件更加通用,因此每个段都可以夹在两侧.

[编辑3]解决了一个错误jhutar指出,当两条线都有条件并且投影结果超出线段时可能会发生.

import numpy as np

def closestDistanceBetweenLines(a0,a1,b0,b1,clampAll=False,clampA0=False,clampA1=False,clampB0=False,clampB1=False):

    ''' Given two lines defined by numpy.array pairs (a0,a1,b0,b1)
        Return the closest points on each segment and their distance
    '''

    # If clampAll=True, set all clamps to True
    if clampAll:
        clampA0=True
        clampA1=True
        clampB0=True
        clampB1=True


    # Calculate denomitator
    A = a1 - a0
    B = b1 - b0
    magA = np.linalg.norm(A)
    magB = np.linalg.norm(B)

    _A = A / magA
    _B = B / magB

    cross = np.cross(_A, _B);
    denom = np.linalg.norm(cross)**2


    # If lines are parallel (denom=0) test if lines overlap.
    # If they don't overlap then there is a closest point solution.
    # If they do overlap, there are infinite closest positions, but there is a closest distance
    if not denom:
        d0 = np.dot(_A,(b0-a0))

        # Overlap only possible with clamping
        if clampA0 or clampA1 or clampB0 or clampB1:
            d1 = np.dot(_A,(b1-a0))

            # Is segment B before A?
            if d0 <= 0 >= d1:
                if clampA0 and clampB1:
                    if np.absolute(d0) < np.absolute(d1):
                        return a0,b0,np.linalg.norm(a0-b0)
                    return a0,b1,np.linalg.norm(a0-b1)


            # Is segment B after A?
            elif d0 >= magA <= d1:
                if clampA1 and clampB0:
                    if np.absolute(d0) < np.absolute(d1):
                        return a1,b0,np.linalg.norm(a1-b0)
                    return a1,b1,np.linalg.norm(a1-b1)


        # Segments overlap, return distance between parallel segments
        return None,None,np.linalg.norm(((d0*_A)+a0)-b0)



    # Lines criss-cross: Calculate the projected closest points
    t = (b0 - a0);
    detA = np.linalg.det([t, _B, cross])
    detB = np.linalg.det([t, _A, cross])

    t0 = detA/denom;
    t1 = detB/denom;

    pA = a0 + (_A * t0) # Projected closest point on segment A
    pB = b0 + (_B * t1) # Projected closest point on segment B


    # Clamp projections
    if clampA0 or clampA1 or clampB0 or clampB1:
        if clampA0 and t0 < 0:
            pA = a0
        elif clampA1 and t0 > magA:
            pA = a1

        if clampB0 and t1 < 0:
            pB = b0
        elif clampB1 and t1 > magB:
            pB = b1

        # Clamp projection A
        if (clampA0 and t0 < 0) or (clampA1 and t0 > magA):
            dot = np.dot(_B,(pA-b0))
            if clampB0 and dot < 0:
                dot = 0
            elif clampB1 and dot > magB:
                dot = magB
            pB = b0 + (_B * dot)

        # Clamp projection B
        if (clampB0 and t1 < 0) or (clampB1 and t1 > magB):
            dot = np.dot(_A,(pB-a0))
            if clampA0 and dot < 0:
                dot = 0
            elif clampA1 and dot > magA:
                dot = magA
            pA = a0 + (_A * dot)


    return pA,pB,np.linalg.norm(pA-pB)

测试示例与图片,以帮助可视化:)

a1=np.array([13.43, 21.77, 46.81])
a0=np.array([27.83, 31.74, -26.60])
b0=np.array([77.54, 7.53, 6.22])
b1=np.array([26.99, 12.39, 11.18])

closestDistanceBetweenLines(a0,a1,b0,b1,clampAll=True)
# Result: (15.826771412132246, array([ 19.85163563,  26.21609078,  14.07303667]), array([ 26.99,  12.39,  11.18])) # 
closestDistanceBetweenLines(a0,a1,b0,b1,clampAll=False)
# Result: (13.240709703623203, array([ 19.85163563,  26.21609078,  14.07303667]), array([ 18.40058604,  13.21580716,  12.02279907])) # 

Answer 2

从这个例子开始,它还附带了一个简单的解释,说明为什么它和VB代码一样好(比你需要的更多,所以我简化了,因为我翻译成了Python - 注意:我已经翻译了,但没有经过测试,所以一个错字可能已经滑落......):

def segments_distance(x11, y11, x12, y12, x21, y21, x22, y22):
  """ distance between two segments in the plane:
      one segment is (x11, y11) to (x12, y12)
      the other is   (x21, y21) to (x22, y22)
  """
  if segments_intersect(x11, y11, x12, y12, x21, y21, x22, y22): return 0
  # try each of the 4 vertices w/the other segment
  distances = []
  distances.append(point_segment_distance(x11, y11, x21, y21, x22, y22))
  distances.append(point_segment_distance(x12, y12, x21, y21, x22, y22))
  distances.append(point_segment_distance(x21, y21, x11, y11, x12, y12))
  distances.append(point_segment_distance(x22, y22, x11, y11, x12, y12))
  return min(distances)

def segments_intersect(x11, y11, x12, y12, x21, y21, x22, y22):
  """ whether two segments in the plane intersect:
      one segment is (x11, y11) to (x12, y12)
      the other is   (x21, y21) to (x22, y22)
  """
  dx1 = x12 - x11
  dy1 = y12 - y11
  dx2 = x22 - x21
  dy2 = y22 - y21
  delta = dx2 * dy1 - dy2 * dx1
  if delta == 0: return False  # parallel segments
  s = (dx1 * (y21 - y11) + dy1 * (x11 - x21)) / delta
  t = (dx2 * (y11 - y21) + dy2 * (x21 - x11)) / (-delta)
  return (0 <= s <= 1) and (0 <= t <= 1)

import math
def point_segment_distance(px, py, x1, y1, x2, y2):
  dx = x2 - x1
  dy = y2 - y1
  if dx == dy == 0:  # the segment's just a point
    return math.hypot(px - x1, py - y1)

  # Calculate the t that minimizes the distance.
  t = ((px - x1) * dx + (py - y1) * dy) / (dx * dx + dy * dy)

  # See if this represents one of the segment's
  # end points or a point in the middle.
  if t < 0:
    dx = px - x1
    dy = py - y1
  elif t > 1:
    dx = px - x2
    dy = py - y2
  else:
    near_x = x1 + t * dx
    near_y = y1 + t * dy
    dx = px - near_x
    dy = py - near_y

  return math.hypot(dx, dy)

Answer 3

这是我的解决方案。它是用Lua编程的。它非常简洁，所以也许会受到赞赏。请确保线段的长度不为0。

local eta = 1e-6
local function nearestPointsOnLineSegments(a0, a1, b0, b1)
    local r = b0 - a0
    local u = a1 - a0
    local v = b1 - b0

    local ru = r:Dot(u)
    local rv = r:Dot(v)
    local uu = u:Dot(u)
    local uv = u:Dot(v)
    local vv = v:Dot(v)

    local det = uu*vv - uv*uv
    local s, t

    if det < eta*uu*vv then
        s = math.clamp(ru/uu, 0, 1)
        t = 0
    else
        s = math.clamp((ru*vv - rv*uv)/det, 0, 1)
        t = math.clamp((ru*uv - rv*uu)/det, 0, 1)
    end

    local S = math.clamp((t*uv + ru)/uu, 0, 1)
    local T = math.clamp((s*uv - rv)/vv, 0, 1)

    local A = a0 + S*u
    local B = b0 + T*v
    return A, B, (B - A):Length()
end

Answer 4

这是2维吗？如果是这样,答案就是A点和线段CD,B和CD,C和AB或D和AB之间的距离最短.所以这是一个相当简单的"点和线之间的距离"计算(如果距离都相同,那么线是平行的).

该网站很好地解释了点与线之间距离的算法.

它在3个维度上稍微有点棘手,因为线条不一定在同一个平面上,但这似乎不是这里的情况？