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

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


当前回答

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

其他回答

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

这是我最后写的代码。这段代码假设一个点以{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));
    };
}

您可以尝试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);

一个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中一个基于这个公式的更简洁的解决方案:

distToSegment: function (point, linePointA, linePointB){

    var x0 = point.X;
    var y0 = point.Y;

    var x1 = linePointA.X;
    var y1 = linePointA.Y;

    var x2 = linePointB.X;
    var y2 = linePointB.Y;

    var Dx = (x2 - x1);
    var Dy = (y2 - y1);

    var numerator = Math.abs(Dy*x0 - Dx*y0 - x1*y2 + x2*y1);
    var denominator = Math.sqrt(Dx*Dx + Dy*Dy);
    if (denominator == 0) {
        return this.dist2(point, linePointA);
    }

    return numerator/denominator;

}