我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
当前回答
用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
其他回答
忍不住用python来编码:)
from math import sqrt, fabs
def pdis(a, b, c):
t = b[0]-a[0], b[1]-a[1] # Vector ab
dd = sqrt(t[0]**2+t[1]**2) # Length of ab
t = t[0]/dd, t[1]/dd # unit vector of ab
n = -t[1], t[0] # normal unit vector to ab
ac = c[0]-a[0], c[1]-a[1] # vector ac
return fabs(ac[0]*n[0]+ac[1]*n[1]) # Projection of ac to n (the minimum distance)
print pdis((1,1), (2,2), (2,0)) # Example (answer is 1.414)
fortran也是一样:)
real function pdis(a, b, c)
real, dimension(0:1), intent(in) :: a, b, c
real, dimension(0:1) :: t, n, ac
real :: dd
t = b - a ! Vector ab
dd = sqrt(t(0)**2+t(1)**2) ! Length of ab
t = t/dd ! unit vector of ab
n = (/-t(1), t(0)/) ! normal unit vector to ab
ac = c - a ! vector ac
pdis = abs(ac(0)*n(0)+ac(1)*n(1)) ! Projection of ac to n (the minimum distance)
end function pdis
program test
print *, pdis((/1.0,1.0/), (/2.0,2.0/), (/2.0,0.0/)) ! Example (answer is 1.414)
end program test
用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
下面是devnullicus转换为c#的c++版本。对于我的实现,我需要知道交叉点,并找到他的解决方案。
public static bool PointSegmentDistanceSquared(PointF point, PointF lineStart, PointF lineEnd, out double distance, out PointF intersectPoint)
{
const double kMinSegmentLenSquared = 0.00000001; // adjust to suit. If you use float, you'll probably want something like 0.000001f
const double kEpsilon = 1.0E-14; // adjust to suit. If you use floats, you'll probably want something like 1E-7f
double dX = lineEnd.X - lineStart.X;
double dY = lineEnd.Y - lineStart.Y;
double dp1X = point.X - lineStart.X;
double dp1Y = point.Y - lineStart.Y;
double segLenSquared = (dX * dX) + (dY * dY);
double t = 0.0;
if (segLenSquared >= -kMinSegmentLenSquared && segLenSquared <= kMinSegmentLenSquared)
{
// segment is a point.
intersectPoint = lineStart;
t = 0.0;
distance = ((dp1X * dp1X) + (dp1Y * dp1Y));
}
else
{
// Project a line from p to the segment [p1,p2]. By considering the line
// extending the segment, parameterized as p1 + (t * (p2 - p1)),
// we find projection of point p onto the line.
// It falls where t = [(p - p1) . (p2 - p1)] / |p2 - p1|^2
t = ((dp1X * dX) + (dp1Y * dY)) / segLenSquared;
if (t < kEpsilon)
{
// intersects at or to the "left" of first segment vertex (lineStart.X, lineStart.Y). If t is approximately 0.0, then
// intersection is at p1. If t is less than that, then there is no intersection (i.e. p is not within
// the 'bounds' of the segment)
if (t > -kEpsilon)
{
// intersects at 1st segment vertex
t = 0.0;
}
// set our 'intersection' point to p1.
intersectPoint = lineStart;
// Note: If you wanted the ACTUAL intersection point of where the projected lines would intersect if
// we were doing PointLineDistanceSquared, then intersectPoint.X would be (lineStart.X + (t * dx)) and intersectPoint.Y would be (lineStart.Y + (t * dy)).
}
else if (t > (1.0 - kEpsilon))
{
// intersects at or to the "right" of second segment vertex (lineEnd.X, lineEnd.Y). If t is approximately 1.0, then
// intersection is at p2. If t is greater than that, then there is no intersection (i.e. p is not within
// the 'bounds' of the segment)
if (t < (1.0 + kEpsilon))
{
// intersects at 2nd segment vertex
t = 1.0;
}
// set our 'intersection' point to p2.
intersectPoint = lineEnd;
// Note: If you wanted the ACTUAL intersection point of where the projected lines would intersect if
// we were doing PointLineDistanceSquared, then intersectPoint.X would be (lineStart.X + (t * dx)) and intersectPoint.Y would be (lineStart.Y + (t * dy)).
}
else
{
// The projection of the point to the point on the segment that is perpendicular succeeded and the point
// is 'within' the bounds of the segment. Set the intersection point as that projected point.
intersectPoint = new PointF((float)(lineStart.X + (t * dX)), (float)(lineStart.Y + (t * dY)));
}
// return the squared distance from p to the intersection point. Note that we return the squared distance
// as an optimization because many times you just need to compare relative distances and the squared values
// works fine for that. If you want the ACTUAL distance, just take the square root of this value.
double dpqX = point.X - intersectPoint.X;
double dpqY = point.Y - intersectPoint.Y;
distance = ((dpqX * dpqX) + (dpqY * dpqY));
}
return true;
}
在数学
它使用线段的参数描述,并将点投影到线段定义的直线中。当参数在线段内从0到1时,如果投影在这个范围之外,我们计算到相应端点的距离,而不是法线到线段的直线。
Clear["Global`*"];
distance[{start_, end_}, pt_] :=
Module[{param},
param = ((pt - start).(end - start))/Norm[end - start]^2; (*parameter. the "."
here means vector product*)
Which[
param < 0, EuclideanDistance[start, pt], (*If outside bounds*)
param > 1, EuclideanDistance[end, pt],
True, EuclideanDistance[pt, start + param (end - start)] (*Normal distance*)
]
];
策划的结果:
Plot3D[distance[{{0, 0}, {1, 0}}, {xp, yp}], {xp, -1, 2}, {yp, -1, 2}]
画出比截断距离更近的点:
等高线图:
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;
}