我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了，所以我看到的例子让我很困惑，我很遗憾地承认。
当前回答
伊莱，你选定的代码是错误的。在线段所在直线附近但远离线段一端的点将被错误地判断为接近线段。更新:上面提到的错误答案已不再被接受。
下面是一些正确的c++代码。它假设一个2d向量类vec2 {float x,y;}，本质上，带有加法、subract、缩放等运算符，以及一个距离和点积函数(即x1 x2 + y1 y2)。
float minimum_distance(vec2 v, vec2 w, vec2 p) {
// Return minimum distance between line segment vw and point p
const float l2 = length_squared(v, w); // i.e. |w-v|^2 - avoid a sqrt
if (l2 == 0.0) return distance(p, v); // v == w case
// 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
// We clamp t from [0,1] to handle points outside the segment vw.
const float t = max(0, min(1, dot(p - v, w - v) / l2));
const vec2 projection = v + t * (w - v); // Projection falls on the segment
return distance(p, projection);
}
编辑:我需要一个Javascript实现，所以在这里，没有依赖关系(或注释，但它是一个直接的端口以上)。点被表示为具有x和y属性的对象。
function sqr(x) { return x * x }
function dist2(v, w) { return sqr(v.x - w.x) + sqr(v.y - w.y) }
function distToSegmentSquared(p, v, w) {
var l2 = dist2(v, w);
if (l2 == 0) return dist2(p, v);
var 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 dist2(p, { x: v.x + t * (w.x - v.x),
y: v.y + t * (w.y - v.y) });
}
function distToSegment(p, v, w) { return Math.sqrt(distToSegmentSquared(p, v, w)); }
编辑2:我需要一个Java版本，但更重要的是，我需要3d版本而不是2d版本。
float dist_to_segment_squared(float px, float py, float pz, float lx1, float ly1, float lz1, float lx2, float ly2, float lz2) {
float line_dist = dist_sq(lx1, ly1, lz1, lx2, ly2, lz2);
if (line_dist == 0) return dist_sq(px, py, pz, lx1, ly1, lz1);
float t = ((px - lx1) * (lx2 - lx1) + (py - ly1) * (ly2 - ly1) + (pz - lz1) * (lz2 - lz1)) / line_dist;
t = constrain(t, 0, 1);
return dist_sq(px, py, pz, lx1 + t * (lx2 - lx1), ly1 + t * (ly2 - ly1), lz1 + t * (lz2 - lz1));
}
这里，在函数参数中，<px,py,pz>是问题点，线段有端点<lx1,ly1,lz1>和<lx2,ly2,lz2>。函数dist_sq(假定存在)求两点之间距离的平方。
其他回答
对于感兴趣的人，这里是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));
}
在我自己的问题线程如何计算在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等)。
这个答案是基于公认答案的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++代码。它假设一个2d向量类vec2 {float x,y;}，本质上，带有加法、subract、缩放等运算符，以及一个距离和点积函数(即x1 x2 + y1 y2)。
float minimum_distance(vec2 v, vec2 w, vec2 p) {
// Return minimum distance between line segment vw and point p
const float l2 = length_squared(v, w); // i.e. |w-v|^2 - avoid a sqrt
if (l2 == 0.0) return distance(p, v); // v == w case
// 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
// We clamp t from [0,1] to handle points outside the segment vw.
const float t = max(0, min(1, dot(p - v, w - v) / l2));
const vec2 projection = v + t * (w - v); // Projection falls on the segment
return distance(p, projection);
}
编辑:我需要一个Javascript实现，所以在这里，没有依赖关系(或注释，但它是一个直接的端口以上)。点被表示为具有x和y属性的对象。
function sqr(x) { return x * x }
function dist2(v, w) { return sqr(v.x - w.x) + sqr(v.y - w.y) }
function distToSegmentSquared(p, v, w) {
var l2 = dist2(v, w);
if (l2 == 0) return dist2(p, v);
var 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 dist2(p, { x: v.x + t * (w.x - v.x),
y: v.y + t * (w.y - v.y) });
}
function distToSegment(p, v, w) { return Math.sqrt(distToSegmentSquared(p, v, w)); }
编辑2:我需要一个Java版本，但更重要的是，我需要3d版本而不是2d版本。
float dist_to_segment_squared(float px, float py, float pz, float lx1, float ly1, float lz1, float lx2, float ly2, float lz2) {
float line_dist = dist_sq(lx1, ly1, lz1, lx2, ly2, lz2);
if (line_dist == 0) return dist_sq(px, py, pz, lx1, ly1, lz1);
float t = ((px - lx1) * (lx2 - lx1) + (py - ly1) * (ly2 - ly1) + (pz - lz1) * (lz2 - lz1)) / line_dist;
t = constrain(t, 0, 1);
return dist_sq(px, py, pz, lx1 + t * (lx2 - lx1), ly1 + t * (ly2 - ly1), lz1 + t * (lz2 - lz1));
}
这里，在函数参数中，<px,py,pz>是问题点，线段有端点<lx1,ly1,lz1>和<lx2,ly2,lz2>。函数dist_sq(假定存在)求两点之间距离的平方。
用t-sql编码
点为(@px， @py)，线段从(@ax， @ay)到(@bx， @by)
create function fn_sqr (@NumberToSquare decimal(18,10))
returns decimal(18,10)
as
begin
declare @Result decimal(18,10)
set @Result = @NumberToSquare * @NumberToSquare
return @Result
end
go
create function fn_Distance(@ax decimal (18,10) , @ay decimal (18,10), @bx decimal(18,10), @by decimal(18,10))
returns decimal(18,10)
as
begin
declare @Result decimal(18,10)
set @Result = (select dbo.fn_sqr(@ax - @bx) + dbo.fn_sqr(@ay - @by) )
return @Result
end
go
create function fn_DistanceToSegmentSquared(@px decimal(18,10), @py decimal(18,10), @ax decimal(18,10), @ay decimal(18,10), @bx decimal(18,10), @by decimal(18,10))
returns decimal(18,10)
as
begin
declare @l2 decimal(18,10)
set @l2 = (select dbo.fn_Distance(@ax, @ay, @bx, @by))
if @l2 = 0
return dbo.fn_Distance(@px, @py, @ax, @ay)
declare @t decimal(18,10)
set @t = ((@px - @ax) * (@bx - @ax) + (@py - @ay) * (@by - @ay)) / @l2
if (@t < 0)
return dbo.fn_Distance(@px, @py, @ax, @ay);
if (@t > 1)
return dbo.fn_Distance(@px, @py, @bx, @by);
return dbo.fn_Distance(@px, @py, @ax + @t * (@bx - @ax), @ay + @t * (@by - @ay))
end
go
create function fn_DistanceToSegment(@px decimal(18,10), @py decimal(18,10), @ax decimal(18,10), @ay decimal(18,10), @bx decimal(18,10), @by decimal(18,10))
returns decimal(18,10)
as
begin
return sqrt(dbo.fn_DistanceToSegmentSquared(@px, @py , @ax , @ay , @bx , @by ))
end
go
--example execution for distance from a point at (6,1) to line segment that runs from (4,2) to (2,1)
select dbo.fn_DistanceToSegment(6, 1, 4, 2, 2, 1)
--result = 2.2360679775
--example execution for distance from a point at (-3,-2) to line segment that runs from (0,-2) to (-2,1)
select dbo.fn_DistanceToSegment(-3, -2, 0, -2, -2, 1)
--result = 2.4961508830
--example execution for distance from a point at (0,-2) to line segment that runs from (0,-2) to (-2,1)
select dbo.fn_DistanceToSegment(0,-2, 0, -2, -2, 1)
--result = 0.0000000000
