我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
当前回答
上面的函数在垂直线上不起作用。这是一个工作正常的函数! 与点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;
}
其他回答
%Matlab solution by Tim from Cody
function ans=distP2S(x0,y0,x1,y1,x2,y2)
% Point is x0,y0
z=complex(x0-x1,y0-y1);
complex(x2-x1,y2-y1);
abs(z-ans*min(1,max(0,real(z/ans))));
Matlab代码,内置“自检”,如果他们调用函数没有参数:
function r = distPointToLineSegment( xy0, xy1, xyP )
% r = distPointToLineSegment( xy0, xy1, xyP )
if( nargin < 3 )
selfTest();
r=0;
else
vx = xy0(1)-xyP(1);
vy = xy0(2)-xyP(2);
ux = xy1(1)-xy0(1);
uy = xy1(2)-xy0(2);
lenSqr= (ux*ux+uy*uy);
detP= -vx*ux + -vy*uy;
if( detP < 0 )
r = norm(xy0-xyP,2);
elseif( detP > lenSqr )
r = norm(xy1-xyP,2);
else
r = abs(ux*vy-uy*vx)/sqrt(lenSqr);
end
end
function selfTest()
%#ok<*NASGU>
disp(['invalid args, distPointToLineSegment running (recursive) self-test...']);
ptA = [1;1]; ptB = [-1;-1];
ptC = [1/2;1/2]; % on the line
ptD = [-2;-1.5]; % too far from line segment
ptE = [1/2;0]; % should be same as perpendicular distance to line
ptF = [1.5;1.5]; % along the A-B but outside of the segment
distCtoAB = distPointToLineSegment(ptA,ptB,ptC)
distDtoAB = distPointToLineSegment(ptA,ptB,ptD)
distEtoAB = distPointToLineSegment(ptA,ptB,ptE)
distFtoAB = distPointToLineSegment(ptA,ptB,ptF)
figure(1); clf;
circle = @(x, y, r, c) rectangle('Position', [x-r, y-r, 2*r, 2*r], ...
'Curvature', [1 1], 'EdgeColor', c);
plot([ptA(1) ptB(1)],[ptA(2) ptB(2)],'r-x'); hold on;
plot(ptC(1),ptC(2),'b+'); circle(ptC(1),ptC(2), 0.5e-1, 'b');
plot(ptD(1),ptD(2),'g+'); circle(ptD(1),ptD(2), distDtoAB, 'g');
plot(ptE(1),ptE(2),'k+'); circle(ptE(1),ptE(2), distEtoAB, 'k');
plot(ptF(1),ptF(2),'m+'); circle(ptF(1),ptF(2), distFtoAB, 'm');
hold off;
axis([-3 3 -3 3]); axis equal;
end
end
C#
改编自@Grumdrig
public static double MinimumDistanceToLineSegment(this Point p,
Line line)
{
var v = line.StartPoint;
var w = line.EndPoint;
double lengthSquared = DistanceSquared(v, w);
if (lengthSquared == 0.0)
return Distance(p, v);
double t = Math.Max(0, Math.Min(1, DotProduct(p - v, w - v) / lengthSquared));
var projection = v + t * (w - v);
return Distance(p, projection);
}
public static double Distance(Point a, Point b)
{
return Math.Sqrt(DistanceSquared(a, b));
}
public static double DistanceSquared(Point a, Point b)
{
var d = a - b;
return DotProduct(d, d);
}
public static double DotProduct(Point a, Point b)
{
return (a.X * b.X) + (a.Y * b.Y);
}
如果它是一条无限大的直线,而不是一条线段,最简单的方法是这样(在ruby中),其中mx + b是直线,(x1, y1)是已知的点
(y1 - mx1 - b).abs / Math.sqrt(m**2 + 1)
这里是与c++答案相同的东西,但移植到pascal。点参数的顺序已经改变,以适应我的代码,但还是一样的东西。
function Dot(const p1, p2: PointF): double;
begin
Result := p1.x * p2.x + p1.y * p2.y;
end;
function SubPoint(const p1, p2: PointF): PointF;
begin
result.x := p1.x - p2.x;
result.y := p1.y - p2.y;
end;
function ShortestDistance2(const p,v,w : PointF) : double;
var
l2,t : double;
projection,tt: PointF;
begin
// Return minimum distance between line segment vw and point p
//l2 := length_squared(v, w); // i.e. |w-v|^2 - avoid a sqrt
l2 := Distance(v,w);
l2 := MPower(l2,2);
if (l2 = 0.0) then begin
result:= Distance(p, v); // v == w case
exit;
end;
// 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
t := Dot(SubPoint(p,v),SubPoint(w,v)) / l2;
if (t < 0.0) then begin
result := Distance(p, v); // Beyond the 'v' end of the segment
exit;
end
else if (t > 1.0) then begin
result := Distance(p, w); // Beyond the 'w' end of the segment
exit;
end;
//projection := v + t * (w - v); // Projection falls on the segment
tt.x := v.x + t * (w.x - v.x);
tt.y := v.y + t * (w.y - v.y);
result := Distance(p, tt);
end;