我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
当前回答
对于感兴趣的人,这里是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));
}
其他回答
看起来几乎每个人都在StackOverflow上贡献了一个答案(目前为止有23个答案),所以这里是我对c#的贡献。这主要是基于M. Katz的回答,而Katz的回答又基于Grumdrig的回答。
public struct MyVector
{
private readonly double _x, _y;
// Constructor
public MyVector(double x, double y)
{
_x = x;
_y = y;
}
// Distance from this point to another point, squared
private double DistanceSquared(MyVector otherPoint)
{
double dx = otherPoint._x - this._x;
double dy = otherPoint._y - this._y;
return dx * dx + dy * dy;
}
// Find the distance from this point to a line segment (which is not the same as from this
// point to anywhere on an infinite line). Also returns the closest point.
public double DistanceToLineSegment(MyVector lineSegmentPoint1, MyVector lineSegmentPoint2,
out MyVector closestPoint)
{
return Math.Sqrt(DistanceToLineSegmentSquared(lineSegmentPoint1, lineSegmentPoint2,
out closestPoint));
}
// Same as above, but avoid using Sqrt(), saves a new nanoseconds in cases where you only want
// to compare several distances to find the smallest or largest, but don't need the distance
public double DistanceToLineSegmentSquared(MyVector lineSegmentPoint1,
MyVector lineSegmentPoint2, out MyVector closestPoint)
{
// Compute length of line segment (squared) and handle special case of coincident points
double segmentLengthSquared = lineSegmentPoint1.DistanceSquared(lineSegmentPoint2);
if (segmentLengthSquared < 1E-7f) // Arbitrary "close enough for government work" value
{
closestPoint = lineSegmentPoint1;
return this.DistanceSquared(closestPoint);
}
// Use the magic formula to compute the "projection" of this point on the infinite line
MyVector lineSegment = lineSegmentPoint2 - lineSegmentPoint1;
double t = (this - lineSegmentPoint1).DotProduct(lineSegment) / segmentLengthSquared;
// Handle the two cases where the projection is not on the line segment, and the case where
// the projection is on the segment
if (t <= 0)
closestPoint = lineSegmentPoint1;
else if (t >= 1)
closestPoint = lineSegmentPoint2;
else
closestPoint = lineSegmentPoint1 + (lineSegment * t);
return this.DistanceSquared(closestPoint);
}
public double DotProduct(MyVector otherVector)
{
return this._x * otherVector._x + this._y * otherVector._y;
}
public static MyVector operator +(MyVector leftVector, MyVector rightVector)
{
return new MyVector(leftVector._x + rightVector._x, leftVector._y + rightVector._y);
}
public static MyVector operator -(MyVector leftVector, MyVector rightVector)
{
return new MyVector(leftVector._x - rightVector._x, leftVector._y - rightVector._y);
}
public static MyVector operator *(MyVector aVector, double aScalar)
{
return new MyVector(aVector._x * aScalar, aVector._y * aScalar);
}
// Added using ReSharper due to CodeAnalysis nagging
public bool Equals(MyVector other)
{
return _x.Equals(other._x) && _y.Equals(other._y);
}
public override bool Equals(object obj)
{
if (ReferenceEquals(null, obj)) return false;
return obj is MyVector && Equals((MyVector) obj);
}
public override int GetHashCode()
{
unchecked
{
return (_x.GetHashCode()*397) ^ _y.GetHashCode();
}
}
public static bool operator ==(MyVector left, MyVector right)
{
return left.Equals(right);
}
public static bool operator !=(MyVector left, MyVector right)
{
return !left.Equals(right);
}
}
这是一个小测试程序。
public static class JustTesting
{
public static void Main()
{
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
for (int i = 0; i < 10000000; i++)
{
TestIt(1, 0, 0, 0, 1, 1, 0.70710678118654757);
TestIt(5, 4, 0, 0, 20, 10, 1.3416407864998738);
TestIt(30, 15, 0, 0, 20, 10, 11.180339887498949);
TestIt(-30, 15, 0, 0, 20, 10, 33.541019662496844);
TestIt(5, 1, 0, 0, 10, 0, 1.0);
TestIt(1, 5, 0, 0, 0, 10, 1.0);
}
stopwatch.Stop();
TimeSpan timeSpan = stopwatch.Elapsed;
}
private static void TestIt(float aPointX, float aPointY,
float lineSegmentPoint1X, float lineSegmentPoint1Y,
float lineSegmentPoint2X, float lineSegmentPoint2Y,
double expectedAnswer)
{
// Katz
double d1 = DistanceFromPointToLineSegment(new MyVector(aPointX, aPointY),
new MyVector(lineSegmentPoint1X, lineSegmentPoint1Y),
new MyVector(lineSegmentPoint2X, lineSegmentPoint2Y));
Debug.Assert(d1 == expectedAnswer);
/*
// Katz using squared distance
double d2 = DistanceFromPointToLineSegmentSquared(new MyVector(aPointX, aPointY),
new MyVector(lineSegmentPoint1X, lineSegmentPoint1Y),
new MyVector(lineSegmentPoint2X, lineSegmentPoint2Y));
Debug.Assert(Math.Abs(d2 - expectedAnswer * expectedAnswer) < 1E-7f);
*/
/*
// Matti (optimized)
double d3 = FloatVector.DistanceToLineSegment(new PointF(aPointX, aPointY),
new PointF(lineSegmentPoint1X, lineSegmentPoint1Y),
new PointF(lineSegmentPoint2X, lineSegmentPoint2Y));
Debug.Assert(Math.Abs(d3 - expectedAnswer) < 1E-7f);
*/
}
private static double DistanceFromPointToLineSegment(MyVector aPoint,
MyVector lineSegmentPoint1, MyVector lineSegmentPoint2)
{
MyVector closestPoint; // Not used
return aPoint.DistanceToLineSegment(lineSegmentPoint1, lineSegmentPoint2,
out closestPoint);
}
private static double DistanceFromPointToLineSegmentSquared(MyVector aPoint,
MyVector lineSegmentPoint1, MyVector lineSegmentPoint2)
{
MyVector closestPoint; // Not used
return aPoint.DistanceToLineSegmentSquared(lineSegmentPoint1, lineSegmentPoint2,
out closestPoint);
}
}
如您所见,我试图衡量使用避免Sqrt()方法的版本与使用普通版本之间的差异。我的测试表明你可能可以节省2.5%,但我甚至不确定——各种测试运行中的变化是相同的数量级。我还试着测量了Matti发布的版本(加上一个明显的优化),该版本似乎比基于Katz/Grumdrig代码的版本慢了大约4%。
编辑:顺便说一句,我还尝试过测量一种方法,该方法使用叉乘(和平方根())来查找到无限直线(不是线段)的距离,它大约快32%。
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);
}
%Matlab solution by Tim from Cody
function ans=distP2S(x0,y0,x1,y1,x2,y2)
% Point is x0,y0
z=complex(x0-x1,y0-y1);
complex(x2-x1,y2-y1);
abs(z-ans*min(1,max(0,real(z/ans))));
对于懒人来说,以下是我在Objective-C语言中移植@Grumdrig的解决方案:
CGFloat sqr(CGFloat x) { return x*x; }
CGFloat dist2(CGPoint v, CGPoint w) { return sqr(v.x - w.x) + sqr(v.y - w.y); }
CGFloat distanceToSegmentSquared(CGPoint p, CGPoint v, CGPoint w)
{
CGFloat l2 = dist2(v, w);
if (l2 == 0.0f) return dist2(p, v);
CGFloat t = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / l2;
if (t < 0.0f) return dist2(p, v);
if (t > 1.0f) return dist2(p, w);
return dist2(p, CGPointMake(v.x + t * (w.x - v.x), v.y + t * (w.y - v.y)));
}
CGFloat distanceToSegment(CGPoint point, CGPoint segmentPointV, CGPoint segmentPointW)
{
return sqrtf(distanceToSegmentSquared(point, segmentPointV, segmentPointW));
}
Grumdrig的c++ /JavaScript实现对我来说非常有用,所以我提供了我正在使用的Python直接端口。完整的代码在这里。
class Point(object):
def __init__(self, x, y):
self.x = float(x)
self.y = float(y)
def square(x):
return x * x
def distance_squared(v, w):
return square(v.x - w.x) + square(v.y - w.y)
def distance_point_segment_squared(p, v, w):
# Segment length squared, |w-v|^2
d2 = distance_squared(v, w)
if d2 == 0:
# v == w, return distance to v
return distance_squared(p, v)
# Consider the line extending the segment, parameterized as v + t (w - v).
# We find projection of point p onto the line.
# It falls where t = [(p-v) . (w-v)] / |w-v|^2
t = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / d2;
if t < 0:
# Beyond v end of the segment
return distance_squared(p, v)
elif t > 1.0:
# Beyond w end of the segment
return distance_squared(p, w)
else:
# Projection falls on the segment.
proj = Point(v.x + t * (w.x - v.x), v.y + t * (w.y - v.y))
# print proj.x, proj.y
return distance_squared(p, proj)