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

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


当前回答

嘿,我昨天才写的。它在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

其他回答

如果它是一条无限大的直线,而不是一条线段,最简单的方法是这样(在ruby中),其中mx + b是直线,(x1, y1)是已知的点

(y1 - mx1 - b).abs / Math.sqrt(m**2 + 1)

用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

您可以尝试PHP geo-math-php的库

composer require rkondratuk/geo-math-php:^1

例子:

<?php

use PhpGeoMath\Model\GeoSegment;
use PhpGeoMath\Model\Polar3dPoint;

$polarPoint1 = new Polar3dPoint(
    40.758742779050706, -73.97855507715238, Polar3dPoint::EARTH_RADIUS_IN_METERS
);

$polarPoint2 = new Polar3dPoint(
    40.74843388072615, -73.98566565776102, Polar3dPoint::EARTH_RADIUS_IN_METERS
);

$polarPoint3 = new Polar3dPoint(
    40.74919365249446, -73.98133456388013, Polar3dPoint::EARTH_RADIUS_IN_METERS
);

$arcSegment = new GeoSegment($polarPoint1, $polarPoint2);
$nearestPolarPoint = $arcSegment->calcNearestPoint($polarPoint3);

// Shortest distance from point-3 to segment(point-1, point-2)
$geoDistance = $nearestPolarPoint->calcGeoDistanceToPoint($polarPoint3);

忍不住用python来编码:)

from math import sqrt, fabs
def pdis(a, b, c):
    t = b[0]-a[0], b[1]-a[1]           # Vector ab
    dd = sqrt(t[0]**2+t[1]**2)         # Length of ab
    t = t[0]/dd, t[1]/dd               # unit vector of ab
    n = -t[1], t[0]                    # normal unit vector to ab
    ac = c[0]-a[0], c[1]-a[1]          # vector ac
    return fabs(ac[0]*n[0]+ac[1]*n[1]) # Projection of ac to n (the minimum distance)

print pdis((1,1), (2,2), (2,0))        # Example (answer is 1.414)

fortran也是一样:)

real function pdis(a, b, c)
    real, dimension(0:1), intent(in) :: a, b, c
    real, dimension(0:1) :: t, n, ac
    real :: dd
    t = b - a                          ! Vector ab
    dd = sqrt(t(0)**2+t(1)**2)         ! Length of ab
    t = t/dd                           ! unit vector of ab
    n = (/-t(1), t(0)/)                ! normal unit vector to ab
    ac = c - a                         ! vector ac
    pdis = abs(ac(0)*n(0)+ac(1)*n(1))  ! Projection of ac to n (the minimum distance)
end function pdis


program test
    print *, pdis((/1.0,1.0/), (/2.0,2.0/), (/2.0,0.0/))   ! Example (answer is 1.414)
end program test

C#

改编自@Grumdrig

public static double MinimumDistanceToLineSegment(this Point p,
    Line line)
{
    var v = line.StartPoint;
    var w = line.EndPoint;

    double lengthSquared = DistanceSquared(v, w);

    if (lengthSquared == 0.0)
        return Distance(p, v);

    double t = Math.Max(0, Math.Min(1, DotProduct(p - v, w - v) / lengthSquared));
    var projection = v + t * (w - v);

    return Distance(p, projection);
}

public static double Distance(Point a, Point b)
{
    return Math.Sqrt(DistanceSquared(a, b));
}

public static double DistanceSquared(Point a, Point b)
{
    var d = a - b;
    return DotProduct(d, d);
}

public static double DotProduct(Point a, Point b)
{
    return (a.X * b.X) + (a.Y * b.Y);
}