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

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


当前回答

用t-sql编码

点为(@px, @py),线段从(@ax, @ay)到(@bx, @by)

create function fn_sqr (@NumberToSquare decimal(18,10)) 
returns decimal(18,10)
as 
begin
    declare @Result decimal(18,10)
    set @Result = @NumberToSquare * @NumberToSquare
    return @Result
end
go

create function fn_Distance(@ax decimal (18,10) , @ay decimal (18,10), @bx decimal(18,10),  @by decimal(18,10)) 
returns decimal(18,10)
as
begin
    declare @Result decimal(18,10)
    set @Result = (select dbo.fn_sqr(@ax - @bx) + dbo.fn_sqr(@ay - @by) )
    return @Result
end
go

create function fn_DistanceToSegmentSquared(@px decimal(18,10), @py decimal(18,10), @ax decimal(18,10), @ay decimal(18,10), @bx decimal(18,10), @by decimal(18,10)) 
returns decimal(18,10)
as 
begin
    declare @l2 decimal(18,10)
    set @l2 = (select dbo.fn_Distance(@ax, @ay, @bx, @by))
    if @l2 = 0
        return dbo.fn_Distance(@px, @py, @ax, @ay)
    declare @t decimal(18,10)
    set @t = ((@px - @ax) * (@bx - @ax) + (@py - @ay) * (@by - @ay)) / @l2
    if (@t < 0) 
        return dbo.fn_Distance(@px, @py, @ax, @ay);
    if (@t > 1) 
        return dbo.fn_Distance(@px, @py, @bx, @by);
    return dbo.fn_Distance(@px, @py,  @ax + @t * (@bx - @ax),  @ay + @t * (@by - @ay))
end
go

create function fn_DistanceToSegment(@px decimal(18,10), @py decimal(18,10), @ax decimal(18,10), @ay decimal(18,10), @bx decimal(18,10), @by decimal(18,10)) 
returns decimal(18,10)
as 
begin
    return sqrt(dbo.fn_DistanceToSegmentSquared(@px, @py , @ax , @ay , @bx , @by ))
end
go

--example execution for distance from a point at (6,1) to line segment that runs from (4,2) to (2,1)
select dbo.fn_DistanceToSegment(6, 1, 4, 2, 2, 1) 
--result = 2.2360679775

--example execution for distance from a point at (-3,-2) to line segment that runs from (0,-2) to (-2,1)
select dbo.fn_DistanceToSegment(-3, -2, 0, -2, -2, 1) 
--result = 2.4961508830

--example execution for distance from a point at (0,-2) to line segment that runs from (0,-2) to (-2,1)
select dbo.fn_DistanceToSegment(0,-2, 0, -2, -2, 1) 
--result = 0.0000000000

其他回答

特征c++版本的3D线段和点

// Return minimum distance between line segment: head--->tail and point
double MinimumDistance(Eigen::Vector3d head, Eigen::Vector3d tail,Eigen::Vector3d point)
{
    double l2 = std::pow((head - tail).norm(),2);
    if(l2 ==0.0) return (head - point).norm();// head == tail case

    // Consider the line extending the segment, parameterized as head + t (tail - point).
    // We find projection of point onto the line.
    // It falls where t = [(point-head) . (tail-head)] / |tail-head|^2
    // We clamp t from [0,1] to handle points outside the segment head--->tail.

    double t = max(0,min(1,(point-head).dot(tail-head)/l2));
    Eigen::Vector3d projection = head + t*(tail-head);

    return (point - projection).norm();
}

这是一个自成体系的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#实现。

Double Distance(Point a, Point b)
{
    double xdiff = a.X - b.X, ydiff = a.Y - b.Y;
    return Math.Sqrt((long)xdiff * xdiff + (long)ydiff * ydiff);
}

Boolean IsBetween(double x, double a, double b)
{
    return ((a <= b && x >= a && x <= b) || (a > b && x <= a && x >= b));
}

Double GetDistance(Point pt, Point pt1, Point pt2, out Point intersection)
{
    Double a, x, y, R;

    if (pt1.X != pt2.X) {
        a = (double)(pt2.Y - pt1.Y) / (pt2.X - pt1.X);
        x = (a * (pt.Y - pt1.Y) + a * a * pt1.X + pt.X) / (a * a + 1);
        y = a * x + pt1.Y - a * pt1.X; }
    else { x = pt1.X;  y = pt.Y; }

    if (IsBetween(x, pt1.X, pt2.X) && IsBetween(y, pt1.Y, pt2.Y)) {
        intersection = new Point((int)x, (int)y);
        R = Distance(intersection, pt); }
    else {
        double d1 = Distance(pt, pt1), d2 = Distance(pt, pt2);
        if (d1 < d2) { intersection = pt1; R = d1; }
        else { intersection = pt2; R = d2; }}

    return R;
}

本想在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的胶囊距离函数代码

这里是与c++答案相同的东西,但移植到pascal。点参数的顺序已经改变,以适应我的代码,但还是一样的东西。

function Dot(const p1, p2: PointF): double;
begin
  Result := p1.x * p2.x + p1.y * p2.y;
end;
function SubPoint(const p1, p2: PointF): PointF;
begin
  result.x := p1.x - p2.x;
  result.y := p1.y - p2.y;
end;

function ShortestDistance2(const p,v,w : PointF) : double;
var
  l2,t : double;
  projection,tt: PointF;
begin
  // Return minimum distance between line segment vw and point p
  //l2 := length_squared(v, w);  // i.e. |w-v|^2 -  avoid a sqrt
  l2 := Distance(v,w);
  l2 := MPower(l2,2);
  if (l2 = 0.0) then begin
    result:= Distance(p, v);   // v == w case
    exit;
  end;
  // 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
  t := Dot(SubPoint(p,v),SubPoint(w,v)) / l2;
  if (t < 0.0) then begin
    result := Distance(p, v);       // Beyond the 'v' end of the segment
    exit;
  end
  else if (t > 1.0) then begin
    result := Distance(p, w);  // Beyond the 'w' end of the segment
    exit;
  end;
  //projection := v + t * (w - v);  // Projection falls on the segment
  tt.x := v.x + t * (w.x - v.x);
  tt.y := v.y + t * (w.y - v.y);
  result := Distance(p, tt);
end;