我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
当前回答
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;
}
其他回答
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;
}
c#版本
public static FP DistanceToLineSegment(FPVector3 a, FPVector3 b, FPVector3 point)
{
var d = b - a;
var s = d.SqrMagnitude;
var ds = d / s;
var lambda = FPVector3.Dot(point - a, ds);
var p = FPMath.Clamp01(lambda) * d;
return (a + p - point).Magnitude;
}
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.
%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))));
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)