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

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


当前回答

%Matlab solution by Tim from Cody
function ans=distP2S(x0,y0,x1,y1,x2,y2)
% Point is x0,y0
z=complex(x0-x1,y0-y1);
complex(x2-x1,y2-y1);
abs(z-ans*min(1,max(0,real(z/ans))));

其他回答

C#

改编自@Grumdrig

public static double MinimumDistanceToLineSegment(this Point p,
    Line line)
{
    var v = line.StartPoint;
    var w = line.EndPoint;

    double lengthSquared = DistanceSquared(v, w);

    if (lengthSquared == 0.0)
        return Distance(p, v);

    double t = Math.Max(0, Math.Min(1, DotProduct(p - v, w - v) / lengthSquared));
    var projection = v + t * (w - v);

    return Distance(p, projection);
}

public static double Distance(Point a, Point b)
{
    return Math.Sqrt(DistanceSquared(a, b));
}

public static double DistanceSquared(Point a, Point b)
{
    var d = a - b;
    return DotProduct(d, d);
}

public static double DotProduct(Point a, Point b)
{
    return (a.X * b.X) + (a.Y * b.Y);
}

Lua: 查找线段(不是整条线)与点之间的最小距离

function solveLinearEquation(A1,B1,C1,A2,B2,C2)
--it is the implitaion of a method of solving linear equations in x and y
  local f1 = B1*C2 -B2*C1
  local f2 = A2*C1-A1*C2
  local f3 = A1*B2 -A2*B1
  return {x= f1/f3, y= f2/f3}
end


function pointLiesOnLine(x,y,x1,y1,x2,y2)
  local dx1 = x-x1
  local  dy1 = y-y1
  local dx2 = x-x2
  local  dy2 = y-y2
  local crossProduct = dy1*dx2 -dx1*dy2

if crossProduct ~= 0  then  return  false
else
  if ((x1>=x) and (x>=x2)) or ((x2>=x) and (x>=x1)) then
    if ((y1>=y) and (y>=y2)) or ((y2>=y) and (y>=y1)) then
      return true
    else return false end
  else  return false end
end
end


function dist(x1,y1,x2,y2)
  local dx = x1-x2
  local dy = y1-y2
  return math.sqrt(dx*dx + dy* dy)
 end


function findMinDistBetnPointAndLine(x1,y1,x2,y2,x3,y3)
-- finds the min  distance between (x3,y3) and line (x1,y2)--(x2,y2)
   local A2,B2,C2,A1,B1,C1
   local dx = y2-y1
   local dy = x2-x1
   if dx == 0 then A2=1 B2=0 C2=-x3 A1=0 B1=1 C1=-y1 
   elseif dy == 0 then A2=0 B2=1 C2=-y3 A1=1 B1=0 C1=-x1
   else
      local m1 = dy/dx
      local m2 = -1/m1
      A2=m2 B2=-1 C2=y3-m2*x3 A1=m1 B1=-1 C1=y1-m1*x1
   end
 local intsecPoint= solveLinearEquation(A1,B1,C1,A2,B2,C2)
if pointLiesOnLine(intsecPoint.x, intsecPoint.y,x1,y1,x2,y2) then
   return dist(intsecPoint.x, intsecPoint.y, x3,y3)
 else
   return math.min(dist(x3,y3,x1,y1),dist(x3,y3,x2,y2))
end
end

这个答案是基于公认答案的JavaScript解决方案。 它主要只是格式更好,函数名更长,当然函数语法更短,因为它是在ES6 + CoffeeScript中。

JavaScript版本(ES6)

distanceSquared = (v, w)=> Math.pow(v.x - w.x, 2) + Math.pow(v.y - w.y, 2);
distance = (v, w)=> Math.sqrt(distanceSquared(v, w));

distanceToLineSegmentSquared = (p, v, w)=> {
    l2 = distanceSquared(v, w);
    if (l2 === 0) {
        return distanceSquared(p, v);
    }
    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 distanceSquared(p, {
        x: v.x + t * (w.x - v.x),
        y: v.y + t * (w.y - v.y)
    });
}
distanceToLineSegment = (p, v, w)=> {
    return Math.sqrt(distanceToLineSegmentSquared(p, v));
}

CoffeeScript版本

distanceSquared = (v, w)-> (v.x - w.x) ** 2 + (v.y - w.y) ** 2
distance = (v, w)-> Math.sqrt(distanceSquared(v, w))

distanceToLineSegmentSquared = (p, v, w)->
    l2 = distanceSquared(v, w)
    return distanceSquared(p, v) if l2 is 0
    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))
    distanceSquared(p, {
        x: v.x + t * (w.x - v.x)
        y: v.y + t * (w.y - v.y)
    })

distanceToLineSegment = (p, v, w)->
    Math.sqrt(distanceToLineSegmentSquared(p, v, w))

对于感兴趣的人,这里是Joshua的Javascript代码到Objective-C的简单转换:

- (double)distanceToPoint:(CGPoint)p fromLineSegmentBetween:(CGPoint)l1 and:(CGPoint)l2
{
    double A = p.x - l1.x;
    double B = p.y - l1.y;
    double C = l2.x - l1.x;
    double D = l2.y - l1.y;

    double dot = A * C + B * D;
    double len_sq = C * C + D * D;
    double param = dot / len_sq;

    double xx, yy;

    if (param < 0 || (l1.x == l2.x && l1.y == l2.y)) {
        xx = l1.x;
        yy = l1.y;
    }
    else if (param > 1) {
        xx = l2.x;
        yy = l2.y;
    }
    else {
        xx = l1.x + param * C;
        yy = l1.y + param * D;
    }

    double dx = p.x - xx;
    double dy = p.y - yy;

    return sqrtf(dx * dx + dy * dy);
}

我需要这个解决方案与MKMapPoint一起工作,所以我将分享它,以防其他人需要它。只是一些小的改变,这将返回米为单位的距离:

- (double)distanceToPoint:(MKMapPoint)p fromLineSegmentBetween:(MKMapPoint)l1 and:(MKMapPoint)l2
{
    double A = p.x - l1.x;
    double B = p.y - l1.y;
    double C = l2.x - l1.x;
    double D = l2.y - l1.y;

    double dot = A * C + B * D;
    double len_sq = C * C + D * D;
    double param = dot / len_sq;

    double xx, yy;

    if (param < 0 || (l1.x == l2.x && l1.y == l2.y)) {
        xx = l1.x;
        yy = l1.y;
    }
    else if (param > 1) {
        xx = l2.x;
        yy = l2.y;
    }
    else {
        xx = l1.x + param * C;
        yy = l1.y + param * D;
    }

    return MKMetersBetweenMapPoints(p, MKMapPointMake(xx, yy));
}

基于Joshua Javascript的AutoHotkeys版本:

plDist(x, y, x1, y1, x2, y2) {
    A:= x - x1
    B:= y - y1
    C:= x2 - x1
    D:= y2 - y1

    dot:= A*C + B*D
    sqLen:= C*C + D*D
    param:= dot / sqLen

    if (param < 0 || ((x1 = x2) && (y1 = y2))) {
        xx:= x1
        yy:= y1
    } else if (param > 1) {
        xx:= x2
        yy:= y2
    } else {
        xx:= x1 + param*C
        yy:= y1 + param*D
    }

    dx:= x - xx
    dy:= y - yy

    return sqrt(dx*dx + dy*dy)
}