我需要一个基本函数来查找点与线段之间最短的距离。您可以使用任何编程语言编写解决方案,我可以将其转换为我正在使用的语言(Javascript)。
编辑:我的线段由两个端点定义。因此,我的线段AB
由两个点A(x1,y1)
和B(x2,y2)
定义。我正在尝试查找该线段与点C(x3,y3)
之间的距离。我的几何技能有些生疏,所以我看到的示例很令人困惑,对此我感到抱歉。
我需要一个基本函数来查找点与线段之间最短的距离。您可以使用任何编程语言编写解决方案,我可以将其转换为我正在使用的语言(Javascript)。
编辑:我的线段由两个端点定义。因此,我的线段AB
由两个点A(x1,y1)
和B(x2,y2)
定义。我正在尝试查找该线段与点C(x3,y3)
之间的距离。我的几何技能有些生疏,所以我看到的示例很令人困惑,对此我感到抱歉。
看起来StackOverflow上几乎所有人都已经贡献了一个答案(目前有23个答案),所以这里是我对C#的贡献。这主要基于M. Katz的答案,而该答案又基于Grumdrig的答案。
public struct MyVector
{
private readonly double _x, _y;
// Constructor
public MyVector(double x, double y)
{
_x = x;
_y = y;
}
// Distance from this point to another point, squared
private double DistanceSquared(MyVector otherPoint)
{
double dx = otherPoint._x - this._x;
double dy = otherPoint._y - this._y;
return dx * dx + dy * dy;
}
// Find the distance from this point to a line segment (which is not the same as from this
// point to anywhere on an infinite line). Also returns the closest point.
public double DistanceToLineSegment(MyVector lineSegmentPoint1, MyVector lineSegmentPoint2,
out MyVector closestPoint)
{
return Math.Sqrt(DistanceToLineSegmentSquared(lineSegmentPoint1, lineSegmentPoint2,
out closestPoint));
}
// Same as above, but avoid using Sqrt(), saves a new nanoseconds in cases where you only want
// to compare several distances to find the smallest or largest, but don't need the distance
public double DistanceToLineSegmentSquared(MyVector lineSegmentPoint1,
MyVector lineSegmentPoint2, out MyVector closestPoint)
{
// Compute length of line segment (squared) and handle special case of coincident points
double segmentLengthSquared = lineSegmentPoint1.DistanceSquared(lineSegmentPoint2);
if (segmentLengthSquared < 1E-7f) // Arbitrary "close enough for government work" value
{
closestPoint = lineSegmentPoint1;
return this.DistanceSquared(closestPoint);
}
// Use the magic formula to compute the "projection" of this point on the infinite line
MyVector lineSegment = lineSegmentPoint2 - lineSegmentPoint1;
double t = (this - lineSegmentPoint1).DotProduct(lineSegment) / segmentLengthSquared;
// Handle the two cases where the projection is not on the line segment, and the case where
// the projection is on the segment
if (t <= 0)
closestPoint = lineSegmentPoint1;
else if (t >= 1)
closestPoint = lineSegmentPoint2;
else
closestPoint = lineSegmentPoint1 + (lineSegment * t);
return this.DistanceSquared(closestPoint);
}
public double DotProduct(MyVector otherVector)
{
return this._x * otherVector._x + this._y * otherVector._y;
}
public static MyVector operator +(MyVector leftVector, MyVector rightVector)
{
return new MyVector(leftVector._x + rightVector._x, leftVector._y + rightVector._y);
}
public static MyVector operator -(MyVector leftVector, MyVector rightVector)
{
return new MyVector(leftVector._x - rightVector._x, leftVector._y - rightVector._y);
}
public static MyVector operator *(MyVector aVector, double aScalar)
{
return new MyVector(aVector._x * aScalar, aVector._y * aScalar);
}
// Added using ReSharper due to CodeAnalysis nagging
public bool Equals(MyVector other)
{
return _x.Equals(other._x) && _y.Equals(other._y);
}
public override bool Equals(object obj)
{
if (ReferenceEquals(null, obj)) return false;
return obj is MyVector && Equals((MyVector) obj);
}
public override int GetHashCode()
{
unchecked
{
return (_x.GetHashCode()*397) ^ _y.GetHashCode();
}
}
public static bool operator ==(MyVector left, MyVector right)
{
return left.Equals(right);
}
public static bool operator !=(MyVector left, MyVector right)
{
return !left.Equals(right);
}
}
这里是一个小的测试程序。
public static class JustTesting
{
public static void Main()
{
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
for (int i = 0; i < 10000000; i++)
{
TestIt(1, 0, 0, 0, 1, 1, 0.70710678118654757);
TestIt(5, 4, 0, 0, 20, 10, 1.3416407864998738);
TestIt(30, 15, 0, 0, 20, 10, 11.180339887498949);
TestIt(-30, 15, 0, 0, 20, 10, 33.541019662496844);
TestIt(5, 1, 0, 0, 10, 0, 1.0);
TestIt(1, 5, 0, 0, 0, 10, 1.0);
}
stopwatch.Stop();
TimeSpan timeSpan = stopwatch.Elapsed;
}
private static void TestIt(float aPointX, float aPointY,
float lineSegmentPoint1X, float lineSegmentPoint1Y,
float lineSegmentPoint2X, float lineSegmentPoint2Y,
double expectedAnswer)
{
// Katz
double d1 = DistanceFromPointToLineSegment(new MyVector(aPointX, aPointY),
new MyVector(lineSegmentPoint1X, lineSegmentPoint1Y),
new MyVector(lineSegmentPoint2X, lineSegmentPoint2Y));
Debug.Assert(d1 == expectedAnswer);
/*
// Katz using squared distance
double d2 = DistanceFromPointToLineSegmentSquared(new MyVector(aPointX, aPointY),
new MyVector(lineSegmentPoint1X, lineSegmentPoint1Y),
new MyVector(lineSegmentPoint2X, lineSegmentPoint2Y));
Debug.Assert(Math.Abs(d2 - expectedAnswer * expectedAnswer) < 1E-7f);
*/
/*
// Matti (optimized)
double d3 = FloatVector.DistanceToLineSegment(new PointF(aPointX, aPointY),
new PointF(lineSegmentPoint1X, lineSegmentPoint1Y),
new PointF(lineSegmentPoint2X, lineSegmentPoint2Y));
Debug.Assert(Math.Abs(d3 - expectedAnswer) < 1E-7f);
*/
}
private static double DistanceFromPointToLineSegment(MyVector aPoint,
MyVector lineSegmentPoint1, MyVector lineSegmentPoint2)
{
MyVector closestPoint; // Not used
return aPoint.DistanceToLineSegment(lineSegmentPoint1, lineSegmentPoint2,
out closestPoint);
}
private static double DistanceFromPointToLineSegmentSquared(MyVector aPoint,
MyVector lineSegmentPoint1, MyVector lineSegmentPoint2)
{
MyVector closestPoint; // Not used
return aPoint.DistanceToLineSegmentSquared(lineSegmentPoint1, lineSegmentPoint2,
out closestPoint);
}
}
一个2D和3D的解决方案
考虑一种基变换,使得线段变为(0, 0, 0)-(d, 0, 0)
,点变为(u, v, 0)
。最短距离发生在该平面上,并且由以下公式给出:
u ≤ 0 -> d(A, C)
0 ≤ u ≤ d -> |v|
d ≤ u -> d(B, C)
AB.AC ≤ 0 -> |AC|
0 ≤ AB.AC ≤ AB² -> |ABxAC|/|AB|
AB² ≤ AB.AC -> |BC|
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;
}
这是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;
}
WPF 版本:
public class LineSegment
{
private readonly Vector _offset;
private readonly Vector _vector;
public LineSegment(Point start, Point end)
{
_offset = (Vector)start;
_vector = (Vector)(end - _offset);
}
public double DistanceTo(Point pt)
{
var v = (Vector)pt - _offset;
// first, find a projection point on the segment in parametric form (0..1)
var p = (v * _vector) / _vector.LengthSquared;
// and limit it so it lays inside the segment
p = Math.Min(Math.Max(p, 0), 1);
// now, find the distance from that point to our point
return (_vector * p - v).Length;
}
}
基于Joshua的Javascript的AutoHotkeys版本:
plDist(x, y, x1, y1, x2, y2) {
A:= x - x1
B:= y - y1
C:= x2 - x1
D:= y2 - y1
dot:= A*C + B*D
sqLen:= C*C + D*D
param:= dot / sqLen
if (param < 0 || ((x1 = x2) && (y1 = y2))) {
xx:= x1
yy:= y1
} else if (param > 1) {
xx:= x2
yy:= y2
} else {
xx:= x1 + param*C
yy:= y1 + param*D
}
dx:= x - xx
dy:= y - yy
return sqrt(dx*dx + dy*dy)
}
https://www.desmos.com/calculator/kswrm8ddum
红点是A,绿点是B,点C是蓝色的。您可以拖动图中的点以查看值的变化。在左侧,“s”值是线段的参数(即s = 0表示点A,s = 1表示点B)。值“d”是第三个点到通过A和B的直线的距离。Python Numpy实现2D坐标数组:
import numpy as np
def dist2d(p1, p2, coords):
''' Distance from points to a finite line btwn p1 -> p2 '''
assert coords.ndim == 2 and coords.shape[1] == 2, 'coords is not 2 dim'
dp = p2 - p1
st = dp[0]**2 + dp[1]**2
u = ((coords[:, 0] - p1[0]) * dp[0] + (coords[:, 1] - p1[1]) * dp[1]) / st
u[u > 1.] = 1.
u[u < 0.] = 0.
dx = (p1[0] + u * dp[0]) - coords[:, 0]
dy = (p1[1] + u * dp[1]) - coords[:, 1]
return np.sqrt(dx**2 + dy**2)
# Usage:
p1 = np.array([0., 0.])
p2 = np.array([0., 10.])
# List of coordinates
coords = np.array(
[[0., 0.],
[5., 5.],
[10., 10.],
[20., 20.]
])
d = dist2d(p1, p2, coords)
# Single coordinate
coord = np.array([25., 25.])
d = dist2d(p1, p2, coord[np.newaxis, :])
被接受的答案不起作用(例如,0,0和(-10,2,10,2)之间的距离应该是2)。
下面是可行的代码:
def dist2line2(x,y,line):
x1,y1,x2,y2=line
vx = x1 - x
vy = y1 - y
ux = x2-x1
uy = y2-y1
length = ux * ux + uy * uy
det = (-vx * ux) + (-vy * uy) #//if this is < 0 or > length then its outside the line segment
if det < 0:
return (x1 - x)**2 + (y1 - y)**2
if det > length:
return (x2 - x)**2 + (y2 - y)**2
det = ux * vy - uy * vx
return det**2 / length
def dist2line(x,y,line): return math.sqrt(dist2line2(x,y,line))
LineString
类。 - TC1