我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。

编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。


当前回答

这是一个自成体系的Delphi / Pascal版本的函数,基于上面约书亚的答案。使用TPoint用于VCL屏幕图形,但应该易于根据需要进行调整。

function DistancePtToSegment( pt, pt1, pt2: TPoint): double;
var
   a, b, c, d: double;
   len_sq: double;
   param: double;
   xx, yy: double;
   dx, dy: double;
begin
   a := pt.x - pt1.x;
   b := pt.y - pt1.y;
   c := pt2.x - pt1.x;
   d := pt2.y - pt1.y;

   len_sq := (c * c) + (d * d);
   param := -1;

   if (len_sq <> 0) then
   begin
      param := ((a * c) + (b * d)) / len_sq;
   end;

   if param < 0 then
   begin
      xx := pt1.x;
      yy := pt1.y;
   end
   else if param > 1 then
   begin
      xx := pt2.x;
      yy := pt2.y;
   end
   else begin
      xx := pt1.x + param * c;
      yy := pt1.y + param * d;
   end;

   dx := pt.x - xx;
   dy := pt.y - yy;
   result := sqrt( (dx * dx) + (dy * dy))
end;

其他回答

伊莱,你选定的代码是错误的。在线段所在直线附近但远离线段一端的点将被错误地判断为接近线段。更新:上面提到的错误答案已不再被接受。

下面是一些正确的c++代码。它假设一个2d向量类vec2 {float x,y;},本质上,带有加法、subract、缩放等运算符,以及一个距离和点积函数(即x1 x2 + y1 y2)。

float minimum_distance(vec2 v, vec2 w, vec2 p) {
  // Return minimum distance between line segment vw and point p
  const float l2 = length_squared(v, w);  // i.e. |w-v|^2 -  avoid a sqrt
  if (l2 == 0.0) return distance(p, v);   // v == w case
  // Consider the line extending the segment, parameterized as v + t (w - v).
  // We find projection of point p onto the line. 
  // It falls where t = [(p-v) . (w-v)] / |w-v|^2
  // We clamp t from [0,1] to handle points outside the segment vw.
  const float t = max(0, min(1, dot(p - v, w - v) / l2));
  const vec2 projection = v + t * (w - v);  // Projection falls on the segment
  return distance(p, projection);
}

编辑:我需要一个Javascript实现,所以在这里,没有依赖关系(或注释,但它是一个直接的端口以上)。点被表示为具有x和y属性的对象。

function sqr(x) { return x * x }
function dist2(v, w) { return sqr(v.x - w.x) + sqr(v.y - w.y) }
function distToSegmentSquared(p, v, w) {
  var l2 = dist2(v, w);
  if (l2 == 0) return dist2(p, v);
  var t = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / l2;
  t = Math.max(0, Math.min(1, t));
  return dist2(p, { x: v.x + t * (w.x - v.x),
                    y: v.y + t * (w.y - v.y) });
}
function distToSegment(p, v, w) { return Math.sqrt(distToSegmentSquared(p, v, w)); }

编辑2:我需要一个Java版本,但更重要的是,我需要3d版本而不是2d版本。

float dist_to_segment_squared(float px, float py, float pz, float lx1, float ly1, float lz1, float lx2, float ly2, float lz2) {
  float line_dist = dist_sq(lx1, ly1, lz1, lx2, ly2, lz2);
  if (line_dist == 0) return dist_sq(px, py, pz, lx1, ly1, lz1);
  float t = ((px - lx1) * (lx2 - lx1) + (py - ly1) * (ly2 - ly1) + (pz - lz1) * (lz2 - lz1)) / line_dist;
  t = constrain(t, 0, 1);
  return dist_sq(px, py, pz, lx1 + t * (lx2 - lx1), ly1 + t * (ly2 - ly1), lz1 + t * (lz2 - lz1));
}

这里,在函数参数中,<px,py,pz>是问题点,线段有端点<lx1,ly1,lz1>和<lx2,ly2,lz2>。函数dist_sq(假定存在)求两点之间距离的平方。

在f#中,点c到a和b之间的线段的距离为:

let pointToLineSegmentDistance (a: Vector, b: Vector) (c: Vector) =
  let d = b - a
  let s = d.Length
  let lambda = (c - a) * d / s
  let p = (lambda |> max 0.0 |> min s) * d / s
  (a + p - c).Length

向量d沿着线段从a指向b。d/s与c-a的点积给出了无限直线与点c之间最接近点的参数。使用min和max函数将该参数钳制到范围0..s,使该点位于a和b之间。最后,a+p-c的长度是c到线段上最近点的距离。

使用示例:

pointToLineSegmentDistance (Vector(0.0, 0.0), Vector(1.0, 0.0)) (Vector(-1.0, 1.0))

2D坐标数组的Python Numpy实现:

import numpy as np


def dist2d(p1, p2, coords):
    ''' Distance from points to a finite line btwn p1 -> p2 '''
    assert coords.ndim == 2 and coords.shape[1] == 2, 'coords is not 2 dim'
    dp = p2 - p1
    st = dp[0]**2 + dp[1]**2
    u = ((coords[:, 0] - p1[0]) * dp[0] + (coords[:, 1] - p1[1]) * dp[1]) / st

    u[u > 1.] = 1.
    u[u < 0.] = 0.

    dx = (p1[0] + u * dp[0]) - coords[:, 0]
    dy = (p1[1] + u * dp[1]) - coords[:, 1]

    return np.sqrt(dx**2 + dy**2)


# Usage:
p1 = np.array([0., 0.])
p2 = np.array([0., 10.])

# List of coordinates
coords = np.array(
    [[0., 0.],
     [5., 5.],
     [10., 10.],
     [20., 20.]
     ])

d = dist2d(p1, p2, coords)

# Single coordinate
coord = np.array([25., 25.])
d = dist2d(p1, p2, coord[np.newaxis, :])

只是遇到了这个,我想我应该添加一个Lua实现。它假设点以表{x=xVal, y=yVal}给出,直线或线段由包含两个点的表给出(见下面的例子):

function distance( P1, P2 )
    return math.sqrt((P1.x-P2.x)^2 + (P1.y-P2.y)^2)
end

-- Returns false if the point lies beyond the reaches of the segment
function distPointToSegment( line, P )
    if line[1].x == line[2].x and line[1].y == line[2].y then
        print("Error: Not a line!")
        return false
    end

    local d = distance( line[1], line[2] )

    local t = ((P.x - line[1].x)*(line[2].x - line[1].x) + (P.y - line[1].y)*(line[2].y - line[1].y))/(d^2)

    local projection = {}
    projection.x = line[1].x + t*(line[2].x-line[1].x)
    projection.y = line[1].y + t*(line[2].y-line[1].y)

    if t >= 0 and t <= 1 then   -- within line segment?
        return distance( projection, {x=P.x, y=P.y} )
    else
        return false
    end
end

-- Returns value even if point is further down the line (outside segment)
function distPointToLine( line, P )
    if line[1].x == line[2].x and line[1].y == line[2].y then
        print("Error: Not a line!")
        return false
    end

    local d = distance( line[1], line[2] )

    local t = ((P.x - line[1].x)*(line[2].x - line[1].x) + (P.y - line[1].y)*(line[2].y - line[1].y))/(d^2)

    local projection = {}
    projection.x = line[1].x + t*(line[2].x-line[1].x)
    projection.y = line[1].y + t*(line[2].y-line[1].y)

    return distance( projection, {x=P.x, y=P.y} )
end

使用示例:

local P1 = {x = 0, y = 0}
local P2 = {x = 10, y = 10}
local line = { P1, P2 }
local P3 = {x = 7, y = 15}
print(distPointToLine( line, P3 ))  -- prints 5.6568542494924
print(distPointToSegment( line, P3 )) -- prints false

本想在GLSL中这样做,但如果可能的话,最好避免所有这些条件。使用clamp()可以避免两种端点情况:

// find closest point to P on line segment AB:
vec3 closest_point_on_line_segment(in vec3 P, in vec3 A, in vec3 B) {
    vec3 AP = P - A, AB = B - A;
    float l = dot(AB, AB);
    if (l <= 0.0000001) return A;    // A and B are practically the same
    return AP - AB*clamp(dot(AP, AB)/l, 0.0, 1.0);  // do the projection
}

如果您可以确定A和B彼此不会非常接近,则可以简化为删除If()。事实上,即使A和B是相同的,我的GPU仍然给出了这个无条件版本的正确结果(但这是使用pre-OpenGL 4.1,其中GLSL除零是未定义的):

// find closest point to P on line segment AB:
vec3 closest_point_on_line_segment(in vec3 P, in vec3 A, in vec3 B) {
    vec3 AP = P - A, AB = B - A;
    return AP - AB*clamp(dot(AP, AB)/dot(AB, AB), 0.0, 1.0);
}

计算距离是很简单的——GLSL提供了一个distance()函数,你可以在这个最近的点和P。

灵感来自Iñigo Quilez的胶囊距离函数代码