我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(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;
};
其他回答
这是一个自成体系的Delphi / Pascal版本的函数,基于上面约书亚的答案。使用TPoint用于VCL屏幕图形,但应该易于根据需要进行调整。
function DistancePtToSegment( pt, pt1, pt2: TPoint): double;
var
a, b, c, d: double;
len_sq: double;
param: double;
xx, yy: double;
dx, dy: double;
begin
a := pt.x - pt1.x;
b := pt.y - pt1.y;
c := pt2.x - pt1.x;
d := pt2.y - pt1.y;
len_sq := (c * c) + (d * d);
param := -1;
if (len_sq <> 0) then
begin
param := ((a * c) + (b * d)) / len_sq;
end;
if param < 0 then
begin
xx := pt1.x;
yy := pt1.y;
end
else if param > 1 then
begin
xx := pt2.x;
yy := pt2.y;
end
else begin
xx := pt1.x + param * c;
yy := pt1.y + param * d;
end;
dx := pt.x - xx;
dy := pt.y - yy;
result := sqrt( (dx * dx) + (dy * dy))
end;
对于感兴趣的人,这里是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));
}
这是一个基于向量数学的;这个解决方案也适用于更高的维度,并报告交点(在线段上)。
def dist(x1,y1,x2,y2,px,py):
a = np.array([[x1,y1]]).T
b = np.array([[x2,y2]]).T
x = np.array([[px,py]]).T
tp = (np.dot(x.T, b) - np.dot(a.T, b)) / np.dot(b.T, b)
tp = tp[0][0]
tmp = x - (a + tp*b)
d = np.sqrt(np.dot(tmp.T,tmp)[0][0])
return d, a+tp*b
x1,y1=2.,2.
x2,y2=5.,5.
px,py=4.,1.
d, inters = dist(x1,y1, x2,y2, px,py)
print (d)
print (inters)
结果是
2.1213203435596424
[[2.5]
[2.5]]
这里解释了数学
https://brilliant.org/wiki/distance-between-point-and-line/
上面的函数在垂直线上不起作用。这是一个工作正常的函数! 与点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;
}
用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