我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
当前回答
您可以尝试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);
其他回答
这个答案是基于公认答案的JavaScript解决方案。 它主要只是格式更好,函数名更长,当然函数语法更短,因为它是在ES6 + CoffeeScript中。
JavaScript版本(ES6)
distanceSquared = (v, w)=> Math.pow(v.x - w.x, 2) + Math.pow(v.y - w.y, 2);
distance = (v, w)=> Math.sqrt(distanceSquared(v, w));
distanceToLineSegmentSquared = (p, v, w)=> {
l2 = distanceSquared(v, w);
if (l2 === 0) {
return distanceSquared(p, v);
}
t = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / l2;
t = Math.max(0, Math.min(1, t));
return distanceSquared(p, {
x: v.x + t * (w.x - v.x),
y: v.y + t * (w.y - v.y)
});
}
distanceToLineSegment = (p, v, w)=> {
return Math.sqrt(distanceToLineSegmentSquared(p, v));
}
CoffeeScript版本
distanceSquared = (v, w)-> (v.x - w.x) ** 2 + (v.y - w.y) ** 2
distance = (v, w)-> Math.sqrt(distanceSquared(v, w))
distanceToLineSegmentSquared = (p, v, w)->
l2 = distanceSquared(v, w)
return distanceSquared(p, v) if l2 is 0
t = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / l2
t = Math.max(0, Math.min(1, t))
distanceSquared(p, {
x: v.x + t * (w.x - v.x)
y: v.y + t * (w.y - v.y)
})
distanceToLineSegment = (p, v, w)->
Math.sqrt(distanceToLineSegmentSquared(p, v, w))
在我自己的问题线程如何计算在C, c# / .NET 2.0或Java的所有情况下一个点和线段之间的最短2D距离?当我找到一个c#的答案时,我被要求把它放在这里:所以它是从http://www.topcoder.com/tc?d1=tutorials&d2=geometry1&module=Static修改的:
//Compute the dot product AB . BC
private double DotProduct(double[] pointA, double[] pointB, double[] pointC)
{
double[] AB = new double[2];
double[] BC = new double[2];
AB[0] = pointB[0] - pointA[0];
AB[1] = pointB[1] - pointA[1];
BC[0] = pointC[0] - pointB[0];
BC[1] = pointC[1] - pointB[1];
double dot = AB[0] * BC[0] + AB[1] * BC[1];
return dot;
}
//Compute the cross product AB x AC
private double CrossProduct(double[] pointA, double[] pointB, double[] pointC)
{
double[] AB = new double[2];
double[] AC = new double[2];
AB[0] = pointB[0] - pointA[0];
AB[1] = pointB[1] - pointA[1];
AC[0] = pointC[0] - pointA[0];
AC[1] = pointC[1] - pointA[1];
double cross = AB[0] * AC[1] - AB[1] * AC[0];
return cross;
}
//Compute the distance from A to B
double Distance(double[] pointA, double[] pointB)
{
double d1 = pointA[0] - pointB[0];
double d2 = pointA[1] - pointB[1];
return Math.Sqrt(d1 * d1 + d2 * d2);
}
//Compute the distance from AB to C
//if isSegment is true, AB is a segment, not a line.
double LineToPointDistance2D(double[] pointA, double[] pointB, double[] pointC,
bool isSegment)
{
double dist = CrossProduct(pointA, pointB, pointC) / Distance(pointA, pointB);
if (isSegment)
{
double dot1 = DotProduct(pointA, pointB, pointC);
if (dot1 > 0)
return Distance(pointB, pointC);
double dot2 = DotProduct(pointB, pointA, pointC);
if (dot2 > 0)
return Distance(pointA, pointC);
}
return Math.Abs(dist);
}
我不是要回答问题,而是要问问题,所以我希望我不会因为某些原因而得到数百万张反对票,而是批评。我只是想(并被鼓励)分享其他人的想法,因为这个帖子中的解决方案要么是用一些奇异的语言(Fortran, Mathematica),要么被某人标记为错误。对我来说唯一有用的(由Grumdrig编写)是用c++编写的,没有人标记它有错误。但是它缺少被调用的方法(dot等)。
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.
GLSL版:
// line (a -> b ) point p[enter image description here][1]
float distanceToLine(vec2 a, vec2 b, vec2 p) {
float aside = dot((p - a),(b - a));
if(aside< 0.0) return length(p-a);
float bside = dot((p - b),(a - b));
if(bside< 0.0) return length(p-b);
vec2 pointOnLine = (bside*a + aside*b)/pow(length(a-b),2.0);
return length(p - pointOnLine);
}
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);
}