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

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


当前回答

省道和颤振的解决方法:

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

其他回答

和这个答案一样,只是用的是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

只是遇到了这个,我想我应该添加一个Lua实现。它假设点以表{x=xVal, y=yVal}给出,直线或线段由包含两个点的表给出(见下面的例子):

function distance( P1, P2 )
    return math.sqrt((P1.x-P2.x)^2 + (P1.y-P2.y)^2)
end

-- Returns false if the point lies beyond the reaches of the segment
function distPointToSegment( line, P )
    if line[1].x == line[2].x and line[1].y == line[2].y then
        print("Error: Not a line!")
        return false
    end

    local d = distance( line[1], line[2] )

    local t = ((P.x - line[1].x)*(line[2].x - line[1].x) + (P.y - line[1].y)*(line[2].y - line[1].y))/(d^2)

    local projection = {}
    projection.x = line[1].x + t*(line[2].x-line[1].x)
    projection.y = line[1].y + t*(line[2].y-line[1].y)

    if t >= 0 and t <= 1 then   -- within line segment?
        return distance( projection, {x=P.x, y=P.y} )
    else
        return false
    end
end

-- Returns value even if point is further down the line (outside segment)
function distPointToLine( line, P )
    if line[1].x == line[2].x and line[1].y == line[2].y then
        print("Error: Not a line!")
        return false
    end

    local d = distance( line[1], line[2] )

    local t = ((P.x - line[1].x)*(line[2].x - line[1].x) + (P.y - line[1].y)*(line[2].y - line[1].y))/(d^2)

    local projection = {}
    projection.x = line[1].x + t*(line[2].x-line[1].x)
    projection.y = line[1].y + t*(line[2].y-line[1].y)

    return distance( projection, {x=P.x, y=P.y} )
end

使用示例:

local P1 = {x = 0, y = 0}
local P2 = {x = 10, y = 10}
local line = { P1, P2 }
local P3 = {x = 7, y = 15}
print(distPointToLine( line, P3 ))  -- prints 5.6568542494924
print(distPointToSegment( line, P3 )) -- prints false

一个2D和3D的解决方案

考虑基底的变化,使得线段变成(0,0,0)-(d, 0,0)和点(u, v, 0)。在这个平面上,最短的距离由

    u ≤ 0 -> d(A, C)
0 ≤ u ≤ d -> |v|
d ≤ u     -> d(B, C)

(到其中一个端点或到支撑线的距离,取决于到该线的投影。等距轨迹由两个半圆和两条线段组成。)

式中,d为AB线段的长度,u、v分别为AB/d (AB方向的单位矢量)与AC的标量积和外积的模量。

AB.AC ≤ 0             -> |AC|
    0 ≤ AB.AC ≤ AB²   -> |ABxAC|/|AB|
          AB² ≤ AB.AC -> |BC|

这个答案是基于公认答案的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))

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)