我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
当前回答
现在我的解决方案...... (Javascript)
这是非常快的,因为我试图避免任何数学。战俘的功能。
如你所见,在函数的最后,我得到了直线的距离。
代码来自lib http://www.draw2d.org/graphiti/jsdoc/#!/例子
/**
* Static util function to determine is a point(px,py) on the line(x1,y1,x2,y2)
* A simple hit test.
*
* @return {boolean}
* @static
* @private
* @param {Number} coronaWidth the accepted corona for the hit test
* @param {Number} X1 x coordinate of the start point of the line
* @param {Number} Y1 y coordinate of the start point of the line
* @param {Number} X2 x coordinate of the end point of the line
* @param {Number} Y2 y coordinate of the end point of the line
* @param {Number} px x coordinate of the point to test
* @param {Number} py y coordinate of the point to test
**/
graphiti.shape.basic.Line.hit= function( coronaWidth, X1, Y1, X2, Y2, px, py)
{
// Adjust vectors relative to X1,Y1
// X2,Y2 becomes relative vector from X1,Y1 to end of segment
X2 -= X1;
Y2 -= Y1;
// px,py becomes relative vector from X1,Y1 to test point
px -= X1;
py -= Y1;
var dotprod = px * X2 + py * Y2;
var projlenSq;
if (dotprod <= 0.0) {
// px,py is on the side of X1,Y1 away from X2,Y2
// distance to segment is length of px,py vector
// "length of its (clipped) projection" is now 0.0
projlenSq = 0.0;
} else {
// switch to backwards vectors relative to X2,Y2
// X2,Y2 are already the negative of X1,Y1=>X2,Y2
// to get px,py to be the negative of px,py=>X2,Y2
// the dot product of two negated vectors is the same
// as the dot product of the two normal vectors
px = X2 - px;
py = Y2 - py;
dotprod = px * X2 + py * Y2;
if (dotprod <= 0.0) {
// px,py is on the side of X2,Y2 away from X1,Y1
// distance to segment is length of (backwards) px,py vector
// "length of its (clipped) projection" is now 0.0
projlenSq = 0.0;
} else {
// px,py is between X1,Y1 and X2,Y2
// dotprod is the length of the px,py vector
// projected on the X2,Y2=>X1,Y1 vector times the
// length of the X2,Y2=>X1,Y1 vector
projlenSq = dotprod * dotprod / (X2 * X2 + Y2 * Y2);
}
}
// Distance to line is now the length of the relative point
// vector minus the length of its projection onto the line
// (which is zero if the projection falls outside the range
// of the line segment).
var lenSq = px * px + py * py - projlenSq;
if (lenSq < 0) {
lenSq = 0;
}
return Math.sqrt(lenSq)<coronaWidth;
};
其他回答
Lua解决方案
-- distance from point (px, py) to line segment (x1, y1, x2, y2)
function distPointToLine(px,py,x1,y1,x2,y2) -- point, start and end of the segment
local dx,dy = x2-x1,y2-y1
local length = math.sqrt(dx*dx+dy*dy)
dx,dy = dx/length,dy/length -- normalization
local p = dx*(px-x1)+dy*(py-y1)
if p < 0 then
dx,dy = px-x1,py-y1
return math.sqrt(dx*dx+dy*dy), x1, y1 -- distance, nearest point
elseif p > length then
dx,dy = px-x2,py-y2
return math.sqrt(dx*dx+dy*dy), x2, y2 -- distance, nearest point
end
return math.abs(dy*(px-x1)-dx*(py-y1)), x1+dx*p, y1+dy*p -- distance, nearest point
end
对于折线(有两条以上线段的线):
-- if the (poly-)line has several segments, just iterate through all of them:
function nearest_sector_in_line (x, y, line)
local x1, y1, x2, y2, min_dist
local ax,ay = line[1], line[2]
for j = 3, #line-1, 2 do
local bx,by = line[j], line[j+1]
local dist = distPointToLine(x,y,ax,ay,bx,by)
if not min_dist or dist < min_dist then
min_dist = dist
x1, y1, x2, y2 = ax,ay,bx,by
end
ax, ay = bx, by
end
return x1, y1, x2, y2
end
例子:
-- call it:
local x1, y1, x2, y2 = nearest_sector_in_line (7, 4, {0,0, 10,0, 10,10, 0,10})
伊莱,你选定的代码是错误的。在线段所在直线附近但远离线段一端的点将被错误地判断为接近线段。更新:上面提到的错误答案已不再被接受。
下面是一些正确的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(假定存在)求两点之间距离的平方。
上面的函数在垂直线上不起作用。这是一个工作正常的函数! 与点p1 p2相交。CheckPoint为p;
public float DistanceOfPointToLine2(PointF p1, PointF p2, PointF p)
{
// (y1-y2)x + (x2-x1)y + (x1y2-x2y1)
//d(P,L) = --------------------------------
// sqrt( (x2-x1)pow2 + (y2-y1)pow2 )
double ch = (p1.Y - p2.Y) * p.X + (p2.X - p1.X) * p.Y + (p1.X * p2.Y - p2.X * p1.Y);
double del = Math.Sqrt(Math.Pow(p2.X - p1.X, 2) + Math.Pow(p2.Y - p1.Y, 2));
double d = ch / del;
return (float)d;
}
对于懒人来说,以下是我在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));
}
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;
}