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

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


当前回答

忍不住用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

其他回答

如果它是一条无限大的直线,而不是一条线段,最简单的方法是这样(在ruby中),其中mx + b是直线,(x1, y1)是已知的点

(y1 - mx1 - b).abs / Math.sqrt(m**2 + 1)

省道和颤振的解决方法:

import 'dart:math' as math;
 class Utils {
   static double shortestDistance(Point p1, Point p2, Point p3){
      double px = p2.x - p1.x;
      double py = p2.y - p1.y;
      double temp = (px*px) + (py*py);
      double u = ((p3.x - p1.x)*px + (p3.y - p1.y)* py) /temp;
      if(u>1){
        u=1;
      }
      else if(u<0){
        u=0;
      }
      double x = p1.x + u*px;
      double y = p1.y + u*py;
      double dx = x - p3.x;
      double dy = y - p3.y;
      double dist = math.sqrt(dx*dx+dy*dy);
      return dist;
   }
}

class Point {
  double x;
  double y;
  Point(this.x, this.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等)。

c#版本

public static FP DistanceToLineSegment(FPVector3 a, FPVector3 b, FPVector3 point)
{
  var d = b - a;
  var s = d.SqrMagnitude;
  var ds = d / s;
  var lambda = FPVector3.Dot(point - a, ds);
  var p = FPMath.Clamp01(lambda) * d;
  return (a + p - point).Magnitude;
}

该算法基于求出指定直线与包含指定点的正交直线的交点,并计算其距离。在线段的情况下,我们必须检查交点是否在线段的点之间,如果不是这样,则最小距离是指定点与线段的一个端点之间的距离。这是一个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;
}