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

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


当前回答

快速实现http://paulbourke.net/geometry/pointlineplane/source.c

    static func magnitude(p1: CGPoint, p2: CGPoint) -> CGFloat {
        let vector = CGPoint(x: p2.x - p1.x, y: p2.y - p1.y)
        return sqrt(pow(vector.x, 2) + pow(vector.y, 2))
    }

    /// http://paulbourke.net/geometry/pointlineplane/
    /// http://paulbourke.net/geometry/pointlineplane/source.c
    static func pointDistanceToLine(point: CGPoint, lineStart: CGPoint, lineEnd: CGPoint) -> CGFloat? {

        let lineMag = magnitude(p1: lineEnd, p2: lineStart)
        let u = (((point.x - lineStart.x) * (lineEnd.x - lineStart.x)) +
                ((point.y - lineStart.y) * (lineEnd.y - lineStart.y))) /
                (lineMag * lineMag)

        if u < 0 || u > 1 {
            // closest point does not fall within the line segment
            return nil
        }

        let intersectionX = lineStart.x + u * (lineEnd.x - lineStart.x)
        let intersectionY = lineStart.y + u * (lineEnd.y - lineStart.y)

        return magnitude(p1: point, p2: CGPoint(x: intersectionX, y: intersectionY))
    }

其他回答

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

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;

    }
%Matlab solution by Tim from Cody
function ans=distP2S(x0,y0,x1,y1,x2,y2)
% Point is x0,y0
z=complex(x0-x1,y0-y1);
complex(x2-x1,y2-y1);
abs(z-ans*min(1,max(0,real(z/ans))));

WPF版本:

public class LineSegment
{
    private readonly Vector _offset;
    private readonly Vector _vector;

    public LineSegment(Point start, Point end)
    {
        _offset = (Vector)start;
        _vector = (Vector)(end - _offset);
    }

    public double DistanceTo(Point pt)
    {
        var v = (Vector)pt - _offset;

        // first, find a projection point on the segment in parametric form (0..1)
        var p = (v * _vector) / _vector.LengthSquared;

        // and limit it so it lays inside the segment
        p = Math.Min(Math.Max(p, 0), 1);

        // now, find the distance from that point to our point
        return (_vector * p - v).Length;
    }
}

公认的答案行不通 (例如,0,0和(-10,2,10,2)之间的距离应为2)。

下面是工作代码:

   def dist2line2(x,y,line):
     x1,y1,x2,y2=line
     vx = x1 - x
     vy = y1 - y
     ux = x2-x1
     uy = y2-y1
     length = ux * ux + uy * uy
     det = (-vx * ux) + (-vy * uy) #//if this is < 0 or > length then its outside the line segment
     if det < 0:
       return (x1 - x)**2 + (y1 - y)**2
     if det > length:
       return (x2 - x)**2 + (y2 - y)**2
     det = ux * vy - uy * vx
     return det**2 / length
   def dist2line(x,y,line): return math.sqrt(dist2line2(x,y,line))

基于Joshua Javascript的AutoHotkeys版本:

plDist(x, y, x1, y1, x2, y2) {
    A:= x - x1
    B:= y - y1
    C:= x2 - x1
    D:= y2 - y1

    dot:= A*C + B*D
    sqLen:= C*C + D*D
    param:= dot / sqLen

    if (param < 0 || ((x1 = x2) && (y1 = y2))) {
        xx:= x1
        yy:= y1
    } else if (param > 1) {
        xx:= x2
        yy:= y2
    } else {
        xx:= x1 + param*C
        yy:= y1 + param*D
    }

    dx:= x - xx
    dy:= y - yy

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