我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
当前回答
这里是与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;
其他回答
我需要一个Godot (GDscript)的实现,所以我写了一个基于grumdrig接受的答案:
func minimum_distance(v: Vector2, w: Vector2, p: Vector2):
# Return minimum distance between line segment vw and point p
var l2: float = (v - w).length_squared() # i.e. |w-v|^2 - avoid a sqrt
if l2 == 0.0:
return p.distance_to(v) # v == w case
# 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
# We clamp t from [0,1] to handle points outside the segment vw.
var t: float = max(0, min(1, (p - v).dot(w - v) / l2))
var projection: Vector2 = v + t * (w - v) # Projection falls on the segment
return p.distance_to(projection)
在f#中,点c到a和b之间的线段的距离为:
let pointToLineSegmentDistance (a: Vector, b: Vector) (c: Vector) =
let d = b - a
let s = d.Length
let lambda = (c - a) * d / s
let p = (lambda |> max 0.0 |> min s) * d / s
(a + p - c).Length
向量d沿着线段从a指向b。d/s与c-a的点积给出了无限直线与点c之间最接近点的参数。使用min和max函数将该参数钳制到范围0..s,使该点位于a和b之间。最后,a+p-c的长度是c到线段上最近点的距离。
使用示例:
pointToLineSegmentDistance (Vector(0.0, 0.0), Vector(1.0, 0.0)) (Vector(-1.0, 1.0))
这是一个自成体系的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;
使用arctangents的一行解决方案:
思路是将A移动到(0,0),并顺时针旋转三角形,使C位于X轴上, 当这种情况发生时,By就是距离。
a角= Atan(Cy - Ay, Cx - Ax); b角= Atan(By - Ay, Bx - Ax); AB长度=平方根((Bx - Ax)²+ (By - Ay)²) By = Sin (bAngle - aAngle) * ABLength
C#
public double Distance(Point a, Point b, Point c)
{
// normalize points
Point cn = new Point(c.X - a.X, c.Y - a.Y);
Point bn = new Point(b.X - a.X, b.Y - a.Y);
double angle = Math.Atan2(bn.Y, bn.X) - Math.Atan2(cn.Y, cn.X);
double abLength = Math.Sqrt(bn.X*bn.X + bn.Y*bn.Y);
return Math.Sin(angle)*abLength;
}
一行c#(要转换为SQL)
double distance = Math.Sin(Math.Atan2(b.Y - a.Y, b.X - a.X) - Math.Atan2(c.Y - a.Y, c.X - a.X)) * Math.Sqrt((b.X - a.X) * (b.X - a.X) + (b.Y - a.Y) * (b.Y - a.Y))
特征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();
}