我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
当前回答
在数学
它使用线段的参数描述,并将点投影到线段定义的直线中。当参数在线段内从0到1时,如果投影在这个范围之外,我们计算到相应端点的距离,而不是法线到线段的直线。
Clear["Global`*"];
distance[{start_, end_}, pt_] :=
Module[{param},
param = ((pt - start).(end - start))/Norm[end - start]^2; (*parameter. the "."
here means vector product*)
Which[
param < 0, EuclideanDistance[start, pt], (*If outside bounds*)
param > 1, EuclideanDistance[end, pt],
True, EuclideanDistance[pt, start + param (end - start)] (*Normal distance*)
]
];
策划的结果:
Plot3D[distance[{{0, 0}, {1, 0}}, {xp, yp}], {xp, -1, 2}, {yp, -1, 2}]
画出比截断距离更近的点:
等高线图:
其他回答
对于感兴趣的人,这里是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));
}
在javascript中使用几何:
var a = { x:20, y:20};//start segment
var b = { x:40, y:30};//end segment
var c = { x:37, y:14};//point
// magnitude from a to c
var ac = Math.sqrt( Math.pow( ( a.x - c.x ), 2 ) + Math.pow( ( a.y - c.y ), 2) );
// magnitude from b to c
var bc = Math.sqrt( Math.pow( ( b.x - c.x ), 2 ) + Math.pow( ( b.y - c.y ), 2 ) );
// magnitude from a to b (base)
var ab = Math.sqrt( Math.pow( ( a.x - b.x ), 2 ) + Math.pow( ( a.y - b.y ), 2 ) );
// perimeter of triangle
var p = ac + bc + ab;
// area of the triangle
var area = Math.sqrt( p/2 * ( p/2 - ac) * ( p/2 - bc ) * ( p/2 - ab ) );
// height of the triangle = distance
var h = ( area * 2 ) / ab;
console.log ("height: " + h);
在我自己的问题线程如何计算在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等)。
快速实现http://paulbourke.net/geometry/pointlineplane/source.c
static func magnitude(p1: CGPoint, p2: CGPoint) -> CGFloat {
let vector = CGPoint(x: p2.x - p1.x, y: p2.y - p1.y)
return sqrt(pow(vector.x, 2) + pow(vector.y, 2))
}
/// http://paulbourke.net/geometry/pointlineplane/
/// http://paulbourke.net/geometry/pointlineplane/source.c
static func pointDistanceToLine(point: CGPoint, lineStart: CGPoint, lineEnd: CGPoint) -> CGFloat? {
let lineMag = magnitude(p1: lineEnd, p2: lineStart)
let u = (((point.x - lineStart.x) * (lineEnd.x - lineStart.x)) +
((point.y - lineStart.y) * (lineEnd.y - lineStart.y))) /
(lineMag * lineMag)
if u < 0 || u > 1 {
// closest point does not fall within the line segment
return nil
}
let intersectionX = lineStart.x + u * (lineEnd.x - lineStart.x)
let intersectionY = lineStart.y + u * (lineEnd.y - lineStart.y)
return magnitude(p1: point, p2: CGPoint(x: intersectionX, y: intersectionY))
}
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);
}