我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
当前回答
这里没有看到Java实现,所以我将Javascript函数从接受的答案转换为Java代码:
static double sqr(double x) {
return x * x;
}
static double dist2(DoublePoint v, DoublePoint w) {
return sqr(v.x - w.x) + sqr(v.y - w.y);
}
static double distToSegmentSquared(DoublePoint p, DoublePoint v, DoublePoint w) {
double l2 = dist2(v, w);
if (l2 == 0) return dist2(p, v);
double t = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / l2;
if (t < 0) return dist2(p, v);
if (t > 1) return dist2(p, w);
return dist2(p, new DoublePoint(
v.x + t * (w.x - v.x),
v.y + t * (w.y - v.y)
));
}
static double distToSegment(DoublePoint p, DoublePoint v, DoublePoint w) {
return Math.sqrt(distToSegmentSquared(p, v, w));
}
static class DoublePoint {
public double x;
public double y;
public DoublePoint(double x, double y) {
this.x = x;
this.y = y;
}
}
其他回答
使用arctangents的一行解决方案:
思路是将A移动到(0,0),并顺时针旋转三角形,使C位于X轴上, 当这种情况发生时,By就是距离。
a角= Atan(Cy - Ay, Cx - Ax); b角= Atan(By - Ay, Bx - Ax); AB长度=平方根((Bx - Ax)²+ (By - Ay)²) By = Sin (bAngle - aAngle) * ABLength
C#
public double Distance(Point a, Point b, Point c)
{
// normalize points
Point cn = new Point(c.X - a.X, c.Y - a.Y);
Point bn = new Point(b.X - a.X, b.Y - a.Y);
double angle = Math.Atan2(bn.Y, bn.X) - Math.Atan2(cn.Y, cn.X);
double abLength = Math.Sqrt(bn.X*bn.X + bn.Y*bn.Y);
return Math.Sin(angle)*abLength;
}
一行c#(要转换为SQL)
double distance = Math.Sin(Math.Atan2(b.Y - a.Y, b.X - a.X) - Math.Atan2(c.Y - a.Y, c.X - a.X)) * Math.Sqrt((b.X - a.X) * (b.X - a.X) + (b.Y - a.Y) * (b.Y - a.Y))
这个答案是基于公认答案的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(假定存在)求两点之间距离的平方。
和这个答案一样,只是用的是Visual Basic。使其可作为Microsoft Excel和VBA/宏中的用户定义函数使用。
函数返回点(x,y)到由(x1,y1)和(x2,y2)定义的线段的最近距离。
Function DistanceToSegment(x As Double, y As Double, x1 As Double, y1 As Double, x2 As Double, y2 As Double)
Dim A As Double
A = x - x1
Dim B As Double
B = y - y1
Dim C As Double
C = x2 - x1
Dim D As Double
D = y2 - y1
Dim dot As Double
dot = A * C + B * D
Dim len_sq As Double
len_sq = C * C + D * D
Dim param As Double
param = -1
If (len_sq <> 0) Then
param = dot / len_sq
End If
Dim xx As Double
Dim yy As Double
If (param < 0) Then
xx = x1
yy = y1
ElseIf (param > 1) Then
xx = x2
yy = y2
Else
xx = x1 + param * C
yy = y1 + param * D
End If
Dim dx As Double
dx = x - xx
Dim dy As Double
dy = y - yy
DistanceToSegment = Math.Sqr(dx * dx + dy * dy)
End Function
用Matlab直接实现Grumdrig
function ans=distP2S(px,py,vx,vy,wx,wy)
% [px py vx vy wx wy]
t=( (px-vx)*(wx-vx)+(py-vy)*(wy-vy) )/idist(vx,wx,vy,wy)^2;
[idist(px,vx,py,vy) idist(px,vx+t*(wx-vx),py,vy+t*(wy-vy)) idist(px,wx,py,wy) ];
ans(1+(t>0)+(t>1)); % <0 0<=t<=1 t>1
end
function d=idist(a,b,c,d)
d=abs(a-b+1i*(c-d));
end