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

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


当前回答

Grumdrig的c++ /JavaScript实现对我来说非常有用,所以我提供了我正在使用的Python直接端口。完整的代码在这里。

class Point(object):
  def __init__(self, x, y):
    self.x = float(x)
    self.y = float(y)

def square(x):
  return x * x

def distance_squared(v, w):
  return square(v.x - w.x) + square(v.y - w.y)

def distance_point_segment_squared(p, v, w):
  # Segment length squared, |w-v|^2
  d2 = distance_squared(v, w) 
  if d2 == 0: 
    # v == w, return distance to v
    return distance_squared(p, v)
  # 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 = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / d2;
  if t < 0:
    # Beyond v end of the segment
    return distance_squared(p, v)
  elif t > 1.0:
    # Beyond w end of the segment
    return distance_squared(p, w)
  else:
    # Projection falls on the segment.
    proj = Point(v.x + t * (w.x - v.x), v.y + t * (w.y - v.y))
    # print proj.x, proj.y
    return distance_squared(p, proj)

其他回答

看起来几乎每个人都在StackOverflow上贡献了一个答案(目前为止有23个答案),所以这里是我对c#的贡献。这主要是基于M. Katz的回答,而Katz的回答又基于Grumdrig的回答。

   public struct MyVector
   {
      private readonly double _x, _y;


      // Constructor
      public MyVector(double x, double y)
      {
         _x = x;
         _y = y;
      }


      // Distance from this point to another point, squared
      private double DistanceSquared(MyVector otherPoint)
      {
         double dx = otherPoint._x - this._x;
         double dy = otherPoint._y - this._y;
         return dx * dx + dy * dy;
      }


      // Find the distance from this point to a line segment (which is not the same as from this 
      //  point to anywhere on an infinite line). Also returns the closest point.
      public double DistanceToLineSegment(MyVector lineSegmentPoint1, MyVector lineSegmentPoint2,
                                          out MyVector closestPoint)
      {
         return Math.Sqrt(DistanceToLineSegmentSquared(lineSegmentPoint1, lineSegmentPoint2, 
                          out closestPoint));
      }


      // Same as above, but avoid using Sqrt(), saves a new nanoseconds in cases where you only want 
      //  to compare several distances to find the smallest or largest, but don't need the distance
      public double DistanceToLineSegmentSquared(MyVector lineSegmentPoint1, 
                                              MyVector lineSegmentPoint2, out MyVector closestPoint)
      {
         // Compute length of line segment (squared) and handle special case of coincident points
         double segmentLengthSquared = lineSegmentPoint1.DistanceSquared(lineSegmentPoint2);
         if (segmentLengthSquared < 1E-7f)  // Arbitrary "close enough for government work" value
         {
            closestPoint = lineSegmentPoint1;
            return this.DistanceSquared(closestPoint);
         }

         // Use the magic formula to compute the "projection" of this point on the infinite line
         MyVector lineSegment = lineSegmentPoint2 - lineSegmentPoint1;
         double t = (this - lineSegmentPoint1).DotProduct(lineSegment) / segmentLengthSquared;

         // Handle the two cases where the projection is not on the line segment, and the case where 
         //  the projection is on the segment
         if (t <= 0)
            closestPoint = lineSegmentPoint1;
         else if (t >= 1)
            closestPoint = lineSegmentPoint2;
         else 
            closestPoint = lineSegmentPoint1 + (lineSegment * t);
         return this.DistanceSquared(closestPoint);
      }


      public double DotProduct(MyVector otherVector)
      {
         return this._x * otherVector._x + this._y * otherVector._y;
      }

      public static MyVector operator +(MyVector leftVector, MyVector rightVector)
      {
         return new MyVector(leftVector._x + rightVector._x, leftVector._y + rightVector._y);
      }

      public static MyVector operator -(MyVector leftVector, MyVector rightVector)
      {
         return new MyVector(leftVector._x - rightVector._x, leftVector._y - rightVector._y);
      }

      public static MyVector operator *(MyVector aVector, double aScalar)
      {
         return new MyVector(aVector._x * aScalar, aVector._y * aScalar);
      }

      // Added using ReSharper due to CodeAnalysis nagging

      public bool Equals(MyVector other)
      {
         return _x.Equals(other._x) && _y.Equals(other._y);
      }

      public override bool Equals(object obj)
      {
         if (ReferenceEquals(null, obj)) return false;
         return obj is MyVector && Equals((MyVector) obj);
      }

      public override int GetHashCode()
      {
         unchecked
         {
            return (_x.GetHashCode()*397) ^ _y.GetHashCode();
         }
      }

      public static bool operator ==(MyVector left, MyVector right)
      {
         return left.Equals(right);
      }

      public static bool operator !=(MyVector left, MyVector right)
      {
         return !left.Equals(right);
      }
   }

这是一个小测试程序。

   public static class JustTesting
   {
      public static void Main()
      {
         Stopwatch stopwatch = new Stopwatch();
         stopwatch.Start();

         for (int i = 0; i < 10000000; i++)
         {
            TestIt(1, 0, 0, 0, 1, 1, 0.70710678118654757);
            TestIt(5, 4, 0, 0, 20, 10, 1.3416407864998738);
            TestIt(30, 15, 0, 0, 20, 10, 11.180339887498949);
            TestIt(-30, 15, 0, 0, 20, 10, 33.541019662496844);
            TestIt(5, 1, 0, 0, 10, 0, 1.0);
            TestIt(1, 5, 0, 0, 0, 10, 1.0);
         }

         stopwatch.Stop();
         TimeSpan timeSpan = stopwatch.Elapsed;
      }


      private static void TestIt(float aPointX, float aPointY, 
                                 float lineSegmentPoint1X, float lineSegmentPoint1Y, 
                                 float lineSegmentPoint2X, float lineSegmentPoint2Y, 
                                 double expectedAnswer)
      {
         // Katz
         double d1 = DistanceFromPointToLineSegment(new MyVector(aPointX, aPointY), 
                                              new MyVector(lineSegmentPoint1X, lineSegmentPoint1Y), 
                                              new MyVector(lineSegmentPoint2X, lineSegmentPoint2Y));
         Debug.Assert(d1 == expectedAnswer);

         /*
         // Katz using squared distance
         double d2 = DistanceFromPointToLineSegmentSquared(new MyVector(aPointX, aPointY), 
                                              new MyVector(lineSegmentPoint1X, lineSegmentPoint1Y), 
                                              new MyVector(lineSegmentPoint2X, lineSegmentPoint2Y));
         Debug.Assert(Math.Abs(d2 - expectedAnswer * expectedAnswer) < 1E-7f);
          */

         /*
         // Matti (optimized)
         double d3 = FloatVector.DistanceToLineSegment(new PointF(aPointX, aPointY), 
                                                new PointF(lineSegmentPoint1X, lineSegmentPoint1Y), 
                                                new PointF(lineSegmentPoint2X, lineSegmentPoint2Y));
         Debug.Assert(Math.Abs(d3 - expectedAnswer) < 1E-7f);
          */
      }

      private static double DistanceFromPointToLineSegment(MyVector aPoint, 
                                             MyVector lineSegmentPoint1, MyVector lineSegmentPoint2)
      {
         MyVector closestPoint;  // Not used
         return aPoint.DistanceToLineSegment(lineSegmentPoint1, lineSegmentPoint2, 
                                             out closestPoint);
      }

      private static double DistanceFromPointToLineSegmentSquared(MyVector aPoint, 
                                             MyVector lineSegmentPoint1, MyVector lineSegmentPoint2)
      {
         MyVector closestPoint;  // Not used
         return aPoint.DistanceToLineSegmentSquared(lineSegmentPoint1, lineSegmentPoint2, 
                                                    out closestPoint);
      }
   }

如您所见,我试图衡量使用避免Sqrt()方法的版本与使用普通版本之间的差异。我的测试表明你可能可以节省2.5%,但我甚至不确定——各种测试运行中的变化是相同的数量级。我还试着测量了Matti发布的版本(加上一个明显的优化),该版本似乎比基于Katz/Grumdrig代码的版本慢了大约4%。

编辑:顺便说一句,我还尝试过测量一种方法,该方法使用叉乘(和平方根())来查找到无限直线(不是线段)的距离,它大约快32%。

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

特征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();
}

I'm assuming you want to find the shortest distance between the point and a line segment; to do this, you need to find the line (lineA) which is perpendicular to your line segment (lineB) which goes through your point, determine the intersection between that line (lineA) and your line which goes through your line segment (lineB); if that point is between the two points of your line segment, then the distance is the distance between your point and the point you just found which is the intersection of lineA and lineB; if the point is not between the two points of your line segment, you need to get the distance between your point and the closer of two ends of the line segment; this can be done easily by taking the square distance (to avoid a square root) between the point and the two points of the line segment; whichever is closer, take the square root of that one.

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