我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
当前回答
特征c++版本的3D线段和点
// Return minimum distance between line segment: head--->tail and point
double MinimumDistance(Eigen::Vector3d head, Eigen::Vector3d tail,Eigen::Vector3d point)
{
double l2 = std::pow((head - tail).norm(),2);
if(l2 ==0.0) return (head - point).norm();// head == tail case
// Consider the line extending the segment, parameterized as head + t (tail - point).
// We find projection of point onto the line.
// It falls where t = [(point-head) . (tail-head)] / |tail-head|^2
// We clamp t from [0,1] to handle points outside the segment head--->tail.
double t = max(0,min(1,(point-head).dot(tail-head)/l2));
Eigen::Vector3d projection = head + t*(tail-head);
return (point - projection).norm();
}
其他回答
这是一个为有限线段而做的实现,而不是像这里的大多数其他函数那样的无限线(这就是为什么我做这个)。
Paul Bourke的理论实施。
Python:
def dist(x1, y1, x2, y2, x3, y3): # x3,y3 is the point
px = x2-x1
py = y2-y1
norm = px*px + py*py
u = ((x3 - x1) * px + (y3 - y1) * py) / float(norm)
if u > 1:
u = 1
elif u < 0:
u = 0
x = x1 + u * px
y = y1 + u * py
dx = x - x3
dy = y - y3
# Note: If the actual distance does not matter,
# if you only want to compare what this function
# returns to other results of this function, you
# can just return the squared distance instead
# (i.e. remove the sqrt) to gain a little performance
dist = (dx*dx + dy*dy)**.5
return dist
AS3:
public static function segmentDistToPoint(segA:Point, segB:Point, p:Point):Number
{
var p2:Point = new Point(segB.x - segA.x, segB.y - segA.y);
var something:Number = p2.x*p2.x + p2.y*p2.y;
var u:Number = ((p.x - segA.x) * p2.x + (p.y - segA.y) * p2.y) / something;
if (u > 1)
u = 1;
else if (u < 0)
u = 0;
var x:Number = segA.x + u * p2.x;
var y:Number = segA.y + u * p2.y;
var dx:Number = x - p.x;
var dy:Number = y - p.y;
var dist:Number = Math.sqrt(dx*dx + dy*dy);
return dist;
}
Java
private double shortestDistance(float x1,float y1,float x2,float y2,float x3,float y3)
{
float px=x2-x1;
float py=y2-y1;
float temp=(px*px)+(py*py);
float u=((x3 - x1) * px + (y3 - y1) * py) / (temp);
if(u>1){
u=1;
}
else if(u<0){
u=0;
}
float x = x1 + u * px;
float y = y1 + u * py;
float dx = x - x3;
float dy = y - y3;
double dist = Math.sqrt(dx*dx + dy*dy);
return dist;
}
用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
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;
}
特征c++版本的3D线段和点
// Return minimum distance between line segment: head--->tail and point
double MinimumDistance(Eigen::Vector3d head, Eigen::Vector3d tail,Eigen::Vector3d point)
{
double l2 = std::pow((head - tail).norm(),2);
if(l2 ==0.0) return (head - point).norm();// head == tail case
// Consider the line extending the segment, parameterized as head + t (tail - point).
// We find projection of point onto the line.
// It falls where t = [(point-head) . (tail-head)] / |tail-head|^2
// We clamp t from [0,1] to handle points outside the segment head--->tail.
double t = max(0,min(1,(point-head).dot(tail-head)/l2));
Eigen::Vector3d projection = head + t*(tail-head);
return (point - projection).norm();
}
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})