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

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


当前回答

这是一个基于向量数学的;这个解决方案也适用于更高的维度,并报告交点(在线段上)。

def dist(x1,y1,x2,y2,px,py):
    a = np.array([[x1,y1]]).T
    b = np.array([[x2,y2]]).T
    x = np.array([[px,py]]).T
    tp = (np.dot(x.T, b) - np.dot(a.T, b)) / np.dot(b.T, b)
    tp = tp[0][0]
    tmp = x - (a + tp*b)
    d = np.sqrt(np.dot(tmp.T,tmp)[0][0])
    return d, a+tp*b

x1,y1=2.,2.
x2,y2=5.,5.
px,py=4.,1.

d, inters = dist(x1,y1, x2,y2, px,py)
print (d)
print (inters)

结果是

2.1213203435596424
[[2.5]
 [2.5]]

这里解释了数学

https://brilliant.org/wiki/distance-between-point-and-line/

其他回答

用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

现在我的解决方案...... (Javascript)

这是非常快的,因为我试图避免任何数学。战俘的功能。

如你所见,在函数的最后,我得到了直线的距离。

代码来自lib http://www.draw2d.org/graphiti/jsdoc/#!/例子

/**
 * Static util function to determine is a point(px,py) on the line(x1,y1,x2,y2)
 * A simple hit test.
 * 
 * @return {boolean}
 * @static
 * @private
 * @param {Number} coronaWidth the accepted corona for the hit test
 * @param {Number} X1 x coordinate of the start point of the line
 * @param {Number} Y1 y coordinate of the start point of the line
 * @param {Number} X2 x coordinate of the end point of the line
 * @param {Number} Y2 y coordinate of the end point of the line
 * @param {Number} px x coordinate of the point to test
 * @param {Number} py y coordinate of the point to test
 **/
graphiti.shape.basic.Line.hit= function( coronaWidth, X1, Y1,  X2,  Y2, px, py)
{
  // Adjust vectors relative to X1,Y1
  // X2,Y2 becomes relative vector from X1,Y1 to end of segment
  X2 -= X1;
  Y2 -= Y1;
  // px,py becomes relative vector from X1,Y1 to test point
  px -= X1;
  py -= Y1;
  var dotprod = px * X2 + py * Y2;
  var projlenSq;
  if (dotprod <= 0.0) {
      // px,py is on the side of X1,Y1 away from X2,Y2
      // distance to segment is length of px,py vector
      // "length of its (clipped) projection" is now 0.0
      projlenSq = 0.0;
  } else {
      // switch to backwards vectors relative to X2,Y2
      // X2,Y2 are already the negative of X1,Y1=>X2,Y2
      // to get px,py to be the negative of px,py=>X2,Y2
      // the dot product of two negated vectors is the same
      // as the dot product of the two normal vectors
      px = X2 - px;
      py = Y2 - py;
      dotprod = px * X2 + py * Y2;
      if (dotprod <= 0.0) {
          // px,py is on the side of X2,Y2 away from X1,Y1
          // distance to segment is length of (backwards) px,py vector
          // "length of its (clipped) projection" is now 0.0
          projlenSq = 0.0;
      } else {
          // px,py is between X1,Y1 and X2,Y2
          // dotprod is the length of the px,py vector
          // projected on the X2,Y2=>X1,Y1 vector times the
          // length of the X2,Y2=>X1,Y1 vector
          projlenSq = dotprod * dotprod / (X2 * X2 + Y2 * Y2);
      }
  }
    // Distance to line is now the length of the relative point
    // vector minus the length of its projection onto the line
    // (which is zero if the projection falls outside the range
    //  of the line segment).
    var lenSq = px * px + py * py - projlenSq;
    if (lenSq < 0) {
        lenSq = 0;
    }
    return Math.sqrt(lenSq)<coronaWidth;
};

嘿,我昨天才写的。它在Actionscript 3.0中,基本上是Javascript,尽管你可能没有相同的Point类。

//st = start of line segment
//b = the line segment (as in: st + b = end of line segment)
//pt = point to test
//Returns distance from point to line segment.  
//Note: nearest point on the segment to the test point is right there if we ever need it
public static function linePointDist( st:Point, b:Point, pt:Point ):Number
{
    var nearestPt:Point; //closest point on seqment to pt

    var keyDot:Number = dot( b, pt.subtract( st ) ); //key dot product
    var bLenSq:Number = dot( b, b ); //Segment length squared

    if( keyDot <= 0 )  //pt is "behind" st, use st
    {
        nearestPt = st  
    }
    else if( keyDot >= bLenSq ) //pt is "past" end of segment, use end (notice we are saving twin sqrts here cuz)
    {
        nearestPt = st.add(b);
    }
    else //pt is inside segment, reuse keyDot and bLenSq to get percent of seqment to move in to find closest point
    {
        var keyDotToPctOfB:Number = keyDot/bLenSq; //REM dot product comes squared
        var partOfB:Point = new Point( b.x * keyDotToPctOfB, b.y * keyDotToPctOfB );
        nearestPt = st.add(partOfB);
    }

    var dist:Number = (pt.subtract(nearestPt)).length;

    return dist;
}

此外,这里有一个关于这个问题的相当完整和可读的讨论:notejot.com

和这个答案一样,只是用的是Visual Basic。使其可作为Microsoft Excel和VBA/宏中的用户定义函数使用。

函数返回点(x,y)到由(x1,y1)和(x2,y2)定义的线段的最近距离。

Function DistanceToSegment(x As Double, y As Double, x1 As Double, y1 As Double, x2 As Double, y2 As Double)

  Dim A As Double
  A = x - x1
  Dim B As Double
  B = y - y1
  Dim C  As Double
  C = x2 - x1
  Dim D As Double
  D = y2 - y1

  Dim dot As Double
  dot = A * C + B * D
  Dim len_sq As Double
  len_sq = C * C + D * D
  Dim param As Double
  param = -1

  If (len_sq <> 0) Then
      param = dot / len_sq
  End If

  Dim xx As Double
  Dim yy As Double

  If (param < 0) Then
    xx = x1
    yy = y1
  ElseIf (param > 1) Then
    xx = x2
    yy = y2
  Else
    xx = x1 + param * C
    yy = y1 + param * D
  End If

  Dim dx As Double
  dx = x - xx
  Dim dy As Double
  dy = y - yy

  DistanceToSegment = Math.Sqr(dx * dx + dy * dy)

End Function

我制作了一个交互式Desmos图来演示如何实现这一点:

https://www.desmos.com/calculator/kswrm8ddum

红点是A点,绿点是B点,C点是蓝色点。 您可以拖动图形中的点来查看值的变化。 左边的值“s”是线段的参数(即s = 0表示点A, s = 1表示点B)。 值“d”是第三点到经过A和B的直线的距离。

编辑:

有趣的小见解:坐标(s, d)是坐标系中第三点C的坐标,AB是单位x轴,单位y轴垂直于AB。