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

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


当前回答

本想在GLSL中这样做,但如果可能的话,最好避免所有这些条件。使用clamp()可以避免两种端点情况:

// find closest point to P on line segment AB:
vec3 closest_point_on_line_segment(in vec3 P, in vec3 A, in vec3 B) {
    vec3 AP = P - A, AB = B - A;
    float l = dot(AB, AB);
    if (l <= 0.0000001) return A;    // A and B are practically the same
    return AP - AB*clamp(dot(AP, AB)/l, 0.0, 1.0);  // do the projection
}

如果您可以确定A和B彼此不会非常接近,则可以简化为删除If()。事实上,即使A和B是相同的,我的GPU仍然给出了这个无条件版本的正确结果(但这是使用pre-OpenGL 4.1,其中GLSL除零是未定义的):

// find closest point to P on line segment AB:
vec3 closest_point_on_line_segment(in vec3 P, in vec3 A, in vec3 B) {
    vec3 AP = P - A, AB = B - A;
    return AP - AB*clamp(dot(AP, AB)/dot(AB, AB), 0.0, 1.0);
}

计算距离是很简单的——GLSL提供了一个distance()函数,你可以在这个最近的点和P。

灵感来自Iñigo Quilez的胶囊距离函数代码

其他回答

这是一个为有限线段而做的实现,而不是像这里的大多数其他函数那样的无限线(这就是为什么我做这个)。

Paul Bourke的理论实施。

Python:

def dist(x1, y1, x2, y2, x3, y3): # x3,y3 is the point
    px = x2-x1
    py = y2-y1

    norm = px*px + py*py

    u =  ((x3 - x1) * px + (y3 - y1) * py) / float(norm)

    if u > 1:
        u = 1
    elif u < 0:
        u = 0

    x = x1 + u * px
    y = y1 + u * py

    dx = x - x3
    dy = y - y3

    # Note: If the actual distance does not matter,
    # if you only want to compare what this function
    # returns to other results of this function, you
    # can just return the squared distance instead
    # (i.e. remove the sqrt) to gain a little performance

    dist = (dx*dx + dy*dy)**.5

    return dist

AS3:

public static function segmentDistToPoint(segA:Point, segB:Point, p:Point):Number
{
    var p2:Point = new Point(segB.x - segA.x, segB.y - segA.y);
    var something:Number = p2.x*p2.x + p2.y*p2.y;
    var u:Number = ((p.x - segA.x) * p2.x + (p.y - segA.y) * p2.y) / something;

    if (u > 1)
        u = 1;
    else if (u < 0)
        u = 0;

    var x:Number = segA.x + u * p2.x;
    var y:Number = segA.y + u * p2.y;

    var dx:Number = x - p.x;
    var dy:Number = y - p.y;

    var dist:Number = Math.sqrt(dx*dx + dy*dy);

    return dist;
}

Java

private double shortestDistance(float x1,float y1,float x2,float y2,float x3,float y3)
    {
        float px=x2-x1;
        float py=y2-y1;
        float temp=(px*px)+(py*py);
        float u=((x3 - x1) * px + (y3 - y1) * py) / (temp);
        if(u>1){
            u=1;
        }
        else if(u<0){
            u=0;
        }
        float x = x1 + u * px;
        float y = y1 + u * py;

        float dx = x - x3;
        float dy = y - y3;
        double dist = Math.sqrt(dx*dx + dy*dy);
        return dist;

    }

这里它使用Swift

    /* Distance from a point (p1) to line l1 l2 */
func distanceFromPoint(p: CGPoint, toLineSegment l1: CGPoint, and l2: CGPoint) -> CGFloat {
    let A = p.x - l1.x
    let B = p.y - l1.y
    let C = l2.x - l1.x
    let D = l2.y - l1.y

    let dot = A * C + B * D
    let len_sq = C * C + D * D
    let param = dot / len_sq

    var xx, yy: CGFloat

    if param < 0 || (l1.x == l2.x && l1.y == l2.y) {
        xx = l1.x
        yy = l1.y
    } else if param > 1 {
        xx = l2.x
        yy = l2.y
    } else {
        xx = l1.x + param * C
        yy = l1.y + param * D
    }

    let dx = p.x - xx
    let dy = p.y - yy

    return sqrt(dx * dx + dy * dy)
}

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

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: 查找线段(不是整条线)与点之间的最小距离

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