我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
当前回答
JavaScript中一个基于这个公式的更简洁的解决方案:
distToSegment: function (point, linePointA, linePointB){
var x0 = point.X;
var y0 = point.Y;
var x1 = linePointA.X;
var y1 = linePointA.Y;
var x2 = linePointB.X;
var y2 = linePointB.Y;
var Dx = (x2 - x1);
var Dy = (y2 - y1);
var numerator = Math.abs(Dy*x0 - Dx*y0 - x1*y2 + x2*y1);
var denominator = Math.sqrt(Dx*Dx + Dy*Dy);
if (denominator == 0) {
return this.dist2(point, linePointA);
}
return numerator/denominator;
}
其他回答
这是我最后写的代码。这段代码假设一个点以{x:5, y:7}的形式定义。注意,这不是绝对最有效的方法,但它是我能想到的最简单、最容易理解的代码。
// a, b, and c in the code below are all points
function distance(a, b)
{
var dx = a.x - b.x;
var dy = a.y - b.y;
return Math.sqrt(dx*dx + dy*dy);
}
function Segment(a, b)
{
var ab = {
x: b.x - a.x,
y: b.y - a.y
};
var length = distance(a, b);
function cross(c) {
return ab.x * (c.y-a.y) - ab.y * (c.x-a.x);
};
this.distanceFrom = function(c) {
return Math.min(distance(a,c),
distance(b,c),
Math.abs(cross(c) / length));
};
}
在我自己的问题线程如何计算在C, c# / .NET 2.0或Java的所有情况下一个点和线段之间的最短2D距离?当我找到一个c#的答案时,我被要求把它放在这里:所以它是从http://www.topcoder.com/tc?d1=tutorials&d2=geometry1&module=Static修改的:
//Compute the dot product AB . BC
private double DotProduct(double[] pointA, double[] pointB, double[] pointC)
{
double[] AB = new double[2];
double[] BC = new double[2];
AB[0] = pointB[0] - pointA[0];
AB[1] = pointB[1] - pointA[1];
BC[0] = pointC[0] - pointB[0];
BC[1] = pointC[1] - pointB[1];
double dot = AB[0] * BC[0] + AB[1] * BC[1];
return dot;
}
//Compute the cross product AB x AC
private double CrossProduct(double[] pointA, double[] pointB, double[] pointC)
{
double[] AB = new double[2];
double[] AC = new double[2];
AB[0] = pointB[0] - pointA[0];
AB[1] = pointB[1] - pointA[1];
AC[0] = pointC[0] - pointA[0];
AC[1] = pointC[1] - pointA[1];
double cross = AB[0] * AC[1] - AB[1] * AC[0];
return cross;
}
//Compute the distance from A to B
double Distance(double[] pointA, double[] pointB)
{
double d1 = pointA[0] - pointB[0];
double d2 = pointA[1] - pointB[1];
return Math.Sqrt(d1 * d1 + d2 * d2);
}
//Compute the distance from AB to C
//if isSegment is true, AB is a segment, not a line.
double LineToPointDistance2D(double[] pointA, double[] pointB, double[] pointC,
bool isSegment)
{
double dist = CrossProduct(pointA, pointB, pointC) / Distance(pointA, pointB);
if (isSegment)
{
double dot1 = DotProduct(pointA, pointB, pointC);
if (dot1 > 0)
return Distance(pointB, pointC);
double dot2 = DotProduct(pointB, pointA, pointC);
if (dot2 > 0)
return Distance(pointA, pointC);
}
return Math.Abs(dist);
}
我不是要回答问题,而是要问问题,所以我希望我不会因为某些原因而得到数百万张反对票,而是批评。我只是想(并被鼓励)分享其他人的想法,因为这个帖子中的解决方案要么是用一些奇异的语言(Fortran, Mathematica),要么被某人标记为错误。对我来说唯一有用的(由Grumdrig编写)是用c++编写的,没有人标记它有错误。但是它缺少被调用的方法(dot等)。
对于感兴趣的人,这里是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));
}
用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
Lua: 查找线段(不是整条线)与点之间的最小距离
function solveLinearEquation(A1,B1,C1,A2,B2,C2)
--it is the implitaion of a method of solving linear equations in x and y
local f1 = B1*C2 -B2*C1
local f2 = A2*C1-A1*C2
local f3 = A1*B2 -A2*B1
return {x= f1/f3, y= f2/f3}
end
function pointLiesOnLine(x,y,x1,y1,x2,y2)
local dx1 = x-x1
local dy1 = y-y1
local dx2 = x-x2
local dy2 = y-y2
local crossProduct = dy1*dx2 -dx1*dy2
if crossProduct ~= 0 then return false
else
if ((x1>=x) and (x>=x2)) or ((x2>=x) and (x>=x1)) then
if ((y1>=y) and (y>=y2)) or ((y2>=y) and (y>=y1)) then
return true
else return false end
else return false end
end
end
function dist(x1,y1,x2,y2)
local dx = x1-x2
local dy = y1-y2
return math.sqrt(dx*dx + dy* dy)
end
function findMinDistBetnPointAndLine(x1,y1,x2,y2,x3,y3)
-- finds the min distance between (x3,y3) and line (x1,y2)--(x2,y2)
local A2,B2,C2,A1,B1,C1
local dx = y2-y1
local dy = x2-x1
if dx == 0 then A2=1 B2=0 C2=-x3 A1=0 B1=1 C1=-y1
elseif dy == 0 then A2=0 B2=1 C2=-y3 A1=1 B1=0 C1=-x1
else
local m1 = dy/dx
local m2 = -1/m1
A2=m2 B2=-1 C2=y3-m2*x3 A1=m1 B1=-1 C1=y1-m1*x1
end
local intsecPoint= solveLinearEquation(A1,B1,C1,A2,B2,C2)
if pointLiesOnLine(intsecPoint.x, intsecPoint.y,x1,y1,x2,y2) then
return dist(intsecPoint.x, intsecPoint.y, x3,y3)
else
return math.min(dist(x3,y3,x1,y1),dist(x3,y3,x2,y2))
end
end