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

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


当前回答

在数学

它使用线段的参数描述,并将点投影到线段定义的直线中。当参数在线段内从0到1时,如果投影在这个范围之外,我们计算到相应端点的距离,而不是法线到线段的直线。

Clear["Global`*"];
 distance[{start_, end_}, pt_] := 
   Module[{param},
   param = ((pt - start).(end - start))/Norm[end - start]^2; (*parameter. the "."
                                                       here means vector product*)

   Which[
    param < 0, EuclideanDistance[start, pt],                 (*If outside bounds*)
    param > 1, EuclideanDistance[end, pt],
    True, EuclideanDistance[pt, start + param (end - start)] (*Normal distance*)
    ]
   ];  

策划的结果:

Plot3D[distance[{{0, 0}, {1, 0}}, {xp, yp}], {xp, -1, 2}, {yp, -1, 2}]

画出比截断距离更近的点:

等高线图:

其他回答

在数学

它使用线段的参数描述,并将点投影到线段定义的直线中。当参数在线段内从0到1时,如果投影在这个范围之外,我们计算到相应端点的距离,而不是法线到线段的直线。

Clear["Global`*"];
 distance[{start_, end_}, pt_] := 
   Module[{param},
   param = ((pt - start).(end - start))/Norm[end - start]^2; (*parameter. the "."
                                                       here means vector product*)

   Which[
    param < 0, EuclideanDistance[start, pt],                 (*If outside bounds*)
    param > 1, EuclideanDistance[end, pt],
    True, EuclideanDistance[pt, start + param (end - start)] (*Normal distance*)
    ]
   ];  

策划的结果:

Plot3D[distance[{{0, 0}, {1, 0}}, {xp, yp}], {xp, -1, 2}, {yp, -1, 2}]

画出比截断距离更近的点:

等高线图:

这是我最后写的代码。这段代码假设一个点以{x:5, y:7}的形式定义。注意,这不是绝对最有效的方法,但它是我能想到的最简单、最容易理解的代码。

// a, b, and c in the code below are all points

function distance(a, b)
{
    var dx = a.x - b.x;
    var dy = a.y - b.y;
    return Math.sqrt(dx*dx + dy*dy);
}

function Segment(a, b)
{
    var ab = {
        x: b.x - a.x,
        y: b.y - a.y
    };
    var length = distance(a, b);

    function cross(c) {
        return ab.x * (c.y-a.y) - ab.y * (c.x-a.x);
    };

    this.distanceFrom = function(c) {
        return Math.min(distance(a,c),
                        distance(b,c),
                        Math.abs(cross(c) / length));
    };
}

在javascript中使用几何:

var a = { x:20, y:20};//start segment    
var b = { x:40, y:30};//end segment   
var c = { x:37, y:14};//point   

// magnitude from a to c    
var ac = Math.sqrt( Math.pow( ( a.x - c.x ), 2 ) + Math.pow( ( a.y - c.y ), 2) );    
// magnitude from b to c   
var bc = Math.sqrt( Math.pow( ( b.x - c.x ), 2 ) + Math.pow( ( b.y - c.y ), 2 ) );    
// magnitude from a to b (base)     
var ab = Math.sqrt( Math.pow( ( a.x - b.x ), 2 ) + Math.pow( ( a.y - b.y ), 2 ) );    
 // perimeter of triangle     
var p = ac + bc + ab;    
 // area of the triangle    
var area = Math.sqrt( p/2 * ( p/2 - ac) * ( p/2 - bc ) * ( p/2 - ab ) );    
 // height of the triangle = distance    
var h = ( area * 2 ) / ab;    
console.log ("height: " + h);

Matlab代码,内置“自检”,如果他们调用函数没有参数:

function r = distPointToLineSegment( xy0, xy1, xyP )
% r = distPointToLineSegment( xy0, xy1, xyP )

if( nargin < 3 )
    selfTest();
    r=0;
else
    vx = xy0(1)-xyP(1);
    vy = xy0(2)-xyP(2);
    ux = xy1(1)-xy0(1);
    uy = xy1(2)-xy0(2);
    lenSqr= (ux*ux+uy*uy);
    detP= -vx*ux + -vy*uy;

    if( detP < 0 )
        r = norm(xy0-xyP,2);
    elseif( detP > lenSqr )
        r = norm(xy1-xyP,2);
    else
        r = abs(ux*vy-uy*vx)/sqrt(lenSqr);
    end
end


    function selfTest()
        %#ok<*NASGU>
        disp(['invalid args, distPointToLineSegment running (recursive)  self-test...']);

        ptA = [1;1]; ptB = [-1;-1];
        ptC = [1/2;1/2];  % on the line
        ptD = [-2;-1.5];  % too far from line segment
        ptE = [1/2;0];    % should be same as perpendicular distance to line
        ptF = [1.5;1.5];      % along the A-B but outside of the segment

        distCtoAB = distPointToLineSegment(ptA,ptB,ptC)
        distDtoAB = distPointToLineSegment(ptA,ptB,ptD)
        distEtoAB = distPointToLineSegment(ptA,ptB,ptE)
        distFtoAB = distPointToLineSegment(ptA,ptB,ptF)
        figure(1); clf;
        circle = @(x, y, r, c) rectangle('Position', [x-r, y-r, 2*r, 2*r], ...
            'Curvature', [1 1], 'EdgeColor', c);
        plot([ptA(1) ptB(1)],[ptA(2) ptB(2)],'r-x'); hold on;
        plot(ptC(1),ptC(2),'b+'); circle(ptC(1),ptC(2), 0.5e-1, 'b');
        plot(ptD(1),ptD(2),'g+'); circle(ptD(1),ptD(2), distDtoAB, 'g');
        plot(ptE(1),ptE(2),'k+'); circle(ptE(1),ptE(2), distEtoAB, 'k');
        plot(ptF(1),ptF(2),'m+'); circle(ptF(1),ptF(2), distFtoAB, 'm');
        hold off;
        axis([-3 3 -3 3]); axis equal;
    end

end

对于感兴趣的人,这里是Joshua的Javascript代码到Objective-C的简单转换:

- (double)distanceToPoint:(CGPoint)p fromLineSegmentBetween:(CGPoint)l1 and:(CGPoint)l2
{
    double A = p.x - l1.x;
    double B = p.y - l1.y;
    double C = l2.x - l1.x;
    double D = l2.y - l1.y;

    double dot = A * C + B * D;
    double len_sq = C * C + D * D;
    double param = dot / len_sq;

    double xx, yy;

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

    double dx = p.x - xx;
    double dy = p.y - yy;

    return sqrtf(dx * dx + dy * dy);
}

我需要这个解决方案与MKMapPoint一起工作,所以我将分享它,以防其他人需要它。只是一些小的改变,这将返回米为单位的距离:

- (double)distanceToPoint:(MKMapPoint)p fromLineSegmentBetween:(MKMapPoint)l1 and:(MKMapPoint)l2
{
    double A = p.x - l1.x;
    double B = p.y - l1.y;
    double C = l2.x - l1.x;
    double D = l2.y - l1.y;

    double dot = A * C + B * D;
    double len_sq = C * C + D * D;
    double param = dot / len_sq;

    double xx, yy;

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

    return MKMetersBetweenMapPoints(p, MKMapPointMake(xx, yy));
}