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

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


当前回答

这是Javascript中最简单的完整代码。

(X, y)是目标点(x1, y)到(x2, y)是线段。

更新:修复了评论中0长度的行问题。

function pDistance(x, y, x1, y1, x2, y2) {

  var A = x - x1;
  var B = y - y1;
  var C = x2 - x1;
  var D = y2 - y1;

  var dot = A * C + B * D;
  var len_sq = C * C + D * D;
  var param = -1;
  if (len_sq != 0) //in case of 0 length line
      param = dot / len_sq;

  var xx, yy;

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

  var dx = x - xx;
  var dy = y - yy;
  return Math.sqrt(dx * dx + dy * dy);
}

更新:Kotlin版本

fun getDistance(x: Double, y: Double, x1: Double, y1: Double, x2: Double, y2: Double): Double {
    val a = x - x1
    val b = y - y1
    val c = x2 - x1
    val d = y2 - y1

    val lenSq = c * c + d * d
    val param = if (lenSq != .0) { //in case of 0 length line
        val dot = a * c + b * d
        dot / lenSq
    } else {
        -1.0
    }

    val (xx, yy) = when {
        param < 0 -> x1 to y1
        param > 1 -> x2 to y2
        else -> x1 + param * c to y1 + param * d
    }

    val dx = x - xx
    val dy = y - yy
    return hypot(dx, dy)
}

其他回答

对于感兴趣的人,这里是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));
}

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

这里它使用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#

改编自@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);
}

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.