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

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


当前回答

Consider this modification to Grumdrig's answer above. Many times you'll find that floating point imprecision can cause problems. I'm using doubles in the version below, but you can easily change to floats. The important part is that it uses an epsilon to handle the "slop". In addition, you'll many times want to know WHERE the intersection happened, or if it happened at all. If the returned t is < 0.0 or > 1.0, no collision occurred. However, even if no collision occurred, many times you'll want to know where the closest point on the segment to P is, and thus I use qx and qy to return this location.

double PointSegmentDistanceSquared( double px, double py,
                                    double p1x, double p1y,
                                    double p2x, double p2y,
                                    double& t,
                                    double& qx, double& qy)
{
    static const double kMinSegmentLenSquared = 0.00000001;  // adjust to suit.  If you use float, you'll probably want something like 0.000001f
    static const double kEpsilon = 1.0E-14;  // adjust to suit.  If you use floats, you'll probably want something like 1E-7f
    double dx = p2x - p1x;
    double dy = p2y - p1y;
    double dp1x = px - p1x;
    double dp1y = py - p1y;
    const double segLenSquared = (dx * dx) + (dy * dy);
    if (segLenSquared >= -kMinSegmentLenSquared && segLenSquared <= kMinSegmentLenSquared)
    {
        // segment is a point.
        qx = p1x;
        qy = p1y;
        t = 0.0;
        return ((dp1x * dp1x) + (dp1y * dp1y));
    }
    else
    {
        // Project a line from p to the segment [p1,p2].  By considering the line
        // extending the segment, parameterized as p1 + (t * (p2 - p1)),
        // we find projection of point p onto the line. 
        // It falls where t = [(p - p1) . (p2 - p1)] / |p2 - p1|^2
        t = ((dp1x * dx) + (dp1y * dy)) / segLenSquared;
        if (t < kEpsilon)
        {
            // intersects at or to the "left" of first segment vertex (p1x, p1y).  If t is approximately 0.0, then
            // intersection is at p1.  If t is less than that, then there is no intersection (i.e. p is not within
            // the 'bounds' of the segment)
            if (t > -kEpsilon)
            {
                // intersects at 1st segment vertex
                t = 0.0;
            }
            // set our 'intersection' point to p1.
            qx = p1x;
            qy = p1y;
            // Note: If you wanted the ACTUAL intersection point of where the projected lines would intersect if
            // we were doing PointLineDistanceSquared, then qx would be (p1x + (t * dx)) and qy would be (p1y + (t * dy)).
        }
        else if (t > (1.0 - kEpsilon))
        {
            // intersects at or to the "right" of second segment vertex (p2x, p2y).  If t is approximately 1.0, then
            // intersection is at p2.  If t is greater than that, then there is no intersection (i.e. p is not within
            // the 'bounds' of the segment)
            if (t < (1.0 + kEpsilon))
            {
                // intersects at 2nd segment vertex
                t = 1.0;
            }
            // set our 'intersection' point to p2.
            qx = p2x;
            qy = p2y;
            // Note: If you wanted the ACTUAL intersection point of where the projected lines would intersect if
            // we were doing PointLineDistanceSquared, then qx would be (p1x + (t * dx)) and qy would be (p1y + (t * dy)).
        }
        else
        {
            // The projection of the point to the point on the segment that is perpendicular succeeded and the point
            // is 'within' the bounds of the segment.  Set the intersection point as that projected point.
            qx = p1x + (t * dx);
            qy = p1y + (t * dy);
        }
        // return the squared distance from p to the intersection point.  Note that we return the squared distance
        // as an optimization because many times you just need to compare relative distances and the squared values
        // works fine for that.  If you want the ACTUAL distance, just take the square root of this value.
        double dpqx = px - qx;
        double dpqy = py - qy;
        return ((dpqx * dpqx) + (dpqy * dpqy));
    }
}

其他回答

在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))

在数学

它使用线段的参数描述,并将点投影到线段定义的直线中。当参数在线段内从0到1时,如果投影在这个范围之外,我们计算到相应端点的距离,而不是法线到线段的直线。

Clear["Global`*"];
 distance[{start_, end_}, pt_] := 
   Module[{param},
   param = ((pt - start).(end - start))/Norm[end - start]^2; (*parameter. the "."
                                                       here means vector product*)

   Which[
    param < 0, EuclideanDistance[start, pt],                 (*If outside bounds*)
    param > 1, EuclideanDistance[end, pt],
    True, EuclideanDistance[pt, start + param (end - start)] (*Normal distance*)
    ]
   ];  

策划的结果:

Plot3D[distance[{{0, 0}, {1, 0}}, {xp, yp}], {xp, -1, 2}, {yp, -1, 2}]

画出比截断距离更近的点:

等高线图:

GLSL版:

// line (a -> b ) point p[enter image description here][1]
float distanceToLine(vec2 a, vec2 b, vec2 p) {
    float aside = dot((p - a),(b - a));
    if(aside< 0.0) return length(p-a);
    float bside = dot((p - b),(a - b));
    if(bside< 0.0) return length(p-b);
    vec2 pointOnLine = (bside*a + aside*b)/pow(length(a-b),2.0);
    return length(p - pointOnLine);
}

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

下面是一些正确的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(假定存在)求两点之间距离的平方。

这是我最后写的代码。这段代码假设一个点以{x:5, y:7}的形式定义。注意,这不是绝对最有效的方法,但它是我能想到的最简单、最容易理解的代码。

// a, b, and c in the code below are all points

function distance(a, b)
{
    var dx = a.x - b.x;
    var dy = a.y - b.y;
    return Math.sqrt(dx*dx + dy*dy);
}

function Segment(a, b)
{
    var ab = {
        x: b.x - a.x,
        y: b.y - a.y
    };
    var length = distance(a, b);

    function cross(c) {
        return ab.x * (c.y-a.y) - ab.y * (c.x-a.x);
    };

    this.distanceFrom = function(c) {
        return Math.min(distance(a,c),
                        distance(b,c),
                        Math.abs(cross(c) / length));
    };
}