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

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


当前回答

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);
}

其他回答

在我自己的问题线程如何计算在C, c# / .NET 2.0或Java的所有情况下一个点和线段之间的最短2D距离?当我找到一个c#的答案时,我被要求把它放在这里:所以它是从http://www.topcoder.com/tc?d1=tutorials&d2=geometry1&module=Static修改的:

//Compute the dot product AB . BC
private double DotProduct(double[] pointA, double[] pointB, double[] pointC)
{
    double[] AB = new double[2];
    double[] BC = new double[2];
    AB[0] = pointB[0] - pointA[0];
    AB[1] = pointB[1] - pointA[1];
    BC[0] = pointC[0] - pointB[0];
    BC[1] = pointC[1] - pointB[1];
    double dot = AB[0] * BC[0] + AB[1] * BC[1];

    return dot;
}

//Compute the cross product AB x AC
private double CrossProduct(double[] pointA, double[] pointB, double[] pointC)
{
    double[] AB = new double[2];
    double[] AC = new double[2];
    AB[0] = pointB[0] - pointA[0];
    AB[1] = pointB[1] - pointA[1];
    AC[0] = pointC[0] - pointA[0];
    AC[1] = pointC[1] - pointA[1];
    double cross = AB[0] * AC[1] - AB[1] * AC[0];

    return cross;
}

//Compute the distance from A to B
double Distance(double[] pointA, double[] pointB)
{
    double d1 = pointA[0] - pointB[0];
    double d2 = pointA[1] - pointB[1];

    return Math.Sqrt(d1 * d1 + d2 * d2);
}

//Compute the distance from AB to C
//if isSegment is true, AB is a segment, not a line.
double LineToPointDistance2D(double[] pointA, double[] pointB, double[] pointC, 
    bool isSegment)
{
    double dist = CrossProduct(pointA, pointB, pointC) / Distance(pointA, pointB);
    if (isSegment)
    {
        double dot1 = DotProduct(pointA, pointB, pointC);
        if (dot1 > 0) 
            return Distance(pointB, pointC);

        double dot2 = DotProduct(pointB, pointA, pointC);
        if (dot2 > 0) 
            return Distance(pointA, pointC);
    }
    return Math.Abs(dist);
} 

我不是要回答问题,而是要问问题,所以我希望我不会因为某些原因而得到数百万张反对票,而是批评。我只是想(并被鼓励)分享其他人的想法,因为这个帖子中的解决方案要么是用一些奇异的语言(Fortran, Mathematica),要么被某人标记为错误。对我来说唯一有用的(由Grumdrig编写)是用c++编写的,没有人标记它有错误。但是它缺少被调用的方法(dot等)。

忍不住用python来编码:)

from math import sqrt, fabs
def pdis(a, b, c):
    t = b[0]-a[0], b[1]-a[1]           # Vector ab
    dd = sqrt(t[0]**2+t[1]**2)         # Length of ab
    t = t[0]/dd, t[1]/dd               # unit vector of ab
    n = -t[1], t[0]                    # normal unit vector to ab
    ac = c[0]-a[0], c[1]-a[1]          # vector ac
    return fabs(ac[0]*n[0]+ac[1]*n[1]) # Projection of ac to n (the minimum distance)

print pdis((1,1), (2,2), (2,0))        # Example (answer is 1.414)

fortran也是一样:)

real function pdis(a, b, c)
    real, dimension(0:1), intent(in) :: a, b, c
    real, dimension(0:1) :: t, n, ac
    real :: dd
    t = b - a                          ! Vector ab
    dd = sqrt(t(0)**2+t(1)**2)         ! Length of ab
    t = t/dd                           ! unit vector of ab
    n = (/-t(1), t(0)/)                ! normal unit vector to ab
    ac = c - a                         ! vector ac
    pdis = abs(ac(0)*n(0)+ac(1)*n(1))  ! Projection of ac to n (the minimum distance)
end function pdis


program test
    print *, pdis((/1.0,1.0/), (/2.0,2.0/), (/2.0,0.0/))   ! Example (answer is 1.414)
end program test

用Matlab直接实现Grumdrig

function ans=distP2S(px,py,vx,vy,wx,wy)
% [px py vx vy wx wy]
  t=( (px-vx)*(wx-vx)+(py-vy)*(wy-vy) )/idist(vx,wx,vy,wy)^2;
  [idist(px,vx,py,vy) idist(px,vx+t*(wx-vx),py,vy+t*(wy-vy)) idist(px,wx,py,wy) ];
  ans(1+(t>0)+(t>1)); % <0 0<=t<=1 t>1     
 end

function d=idist(a,b,c,d)
 d=abs(a-b+1i*(c-d));
end

Lua解决方案

-- distance from point (px, py) to line segment (x1, y1, x2, y2)
function distPointToLine(px,py,x1,y1,x2,y2) -- point, start and end of the segment
    local dx,dy = x2-x1,y2-y1
    local length = math.sqrt(dx*dx+dy*dy)
    dx,dy = dx/length,dy/length -- normalization
    local p = dx*(px-x1)+dy*(py-y1)
    if p < 0 then
        dx,dy = px-x1,py-y1
        return math.sqrt(dx*dx+dy*dy), x1, y1 -- distance, nearest point
    elseif p > length then
        dx,dy = px-x2,py-y2
        return math.sqrt(dx*dx+dy*dy), x2, y2 -- distance, nearest point
    end
    return math.abs(dy*(px-x1)-dx*(py-y1)), x1+dx*p, y1+dy*p -- distance, nearest point
end

对于折线(有两条以上线段的线):

-- if the (poly-)line has several segments, just iterate through all of them:
function nearest_sector_in_line (x, y, line)
    local x1, y1, x2, y2, min_dist
    local ax,ay = line[1], line[2]
    for j = 3, #line-1, 2 do
        local bx,by = line[j], line[j+1]
        local dist = distPointToLine(x,y,ax,ay,bx,by)
        if not min_dist or dist < min_dist then
            min_dist = dist
            x1, y1, x2, y2 = ax,ay,bx,by
        end
        ax, ay = bx, by
    end
    return x1, y1, x2, y2
end

例子:

-- call it:
local x1, y1, x2, y2 = nearest_sector_in_line (7, 4, {0,0, 10,0, 10,10, 0,10})

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