我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
当前回答
忍不住用python来编码:)
from math import sqrt, fabs
def pdis(a, b, c):
t = b[0]-a[0], b[1]-a[1] # Vector ab
dd = sqrt(t[0]**2+t[1]**2) # Length of ab
t = t[0]/dd, t[1]/dd # unit vector of ab
n = -t[1], t[0] # normal unit vector to ab
ac = c[0]-a[0], c[1]-a[1] # vector ac
return fabs(ac[0]*n[0]+ac[1]*n[1]) # Projection of ac to n (the minimum distance)
print pdis((1,1), (2,2), (2,0)) # Example (answer is 1.414)
fortran也是一样:)
real function pdis(a, b, c)
real, dimension(0:1), intent(in) :: a, b, c
real, dimension(0:1) :: t, n, ac
real :: dd
t = b - a ! Vector ab
dd = sqrt(t(0)**2+t(1)**2) ! Length of ab
t = t/dd ! unit vector of ab
n = (/-t(1), t(0)/) ! normal unit vector to ab
ac = c - a ! vector ac
pdis = abs(ac(0)*n(0)+ac(1)*n(1)) ! Projection of ac to n (the minimum distance)
end function pdis
program test
print *, pdis((/1.0,1.0/), (/2.0,2.0/), (/2.0,0.0/)) ! Example (answer is 1.414)
end program test
其他回答
如果它是一条无限大的直线,而不是一条线段,最简单的方法是这样(在ruby中),其中mx + b是直线,(x1, y1)是已知的点
(y1 - mx1 - b).abs / Math.sqrt(m**2 + 1)
省道和颤振的解决方法:
import 'dart:math' as math;
class Utils {
static double shortestDistance(Point p1, Point p2, Point p3){
double px = p2.x - p1.x;
double py = p2.y - p1.y;
double temp = (px*px) + (py*py);
double u = ((p3.x - p1.x)*px + (p3.y - p1.y)* py) /temp;
if(u>1){
u=1;
}
else if(u<0){
u=0;
}
double x = p1.x + u*px;
double y = p1.y + u*py;
double dx = x - p3.x;
double dy = y - p3.y;
double dist = math.sqrt(dx*dx+dy*dy);
return dist;
}
}
class Point {
double x;
double y;
Point(this.x, this.y);
}
在我自己的问题线程如何计算在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等)。
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;
}
该算法基于求出指定直线与包含指定点的正交直线的交点,并计算其距离。在线段的情况下,我们必须检查交点是否在线段的点之间,如果不是这样,则最小距离是指定点与线段的一个端点之间的距离。这是一个c#实现。
Double Distance(Point a, Point b)
{
double xdiff = a.X - b.X, ydiff = a.Y - b.Y;
return Math.Sqrt((long)xdiff * xdiff + (long)ydiff * ydiff);
}
Boolean IsBetween(double x, double a, double b)
{
return ((a <= b && x >= a && x <= b) || (a > b && x <= a && x >= b));
}
Double GetDistance(Point pt, Point pt1, Point pt2, out Point intersection)
{
Double a, x, y, R;
if (pt1.X != pt2.X) {
a = (double)(pt2.Y - pt1.Y) / (pt2.X - pt1.X);
x = (a * (pt.Y - pt1.Y) + a * a * pt1.X + pt.X) / (a * a + 1);
y = a * x + pt1.Y - a * pt1.X; }
else { x = pt1.X; y = pt.Y; }
if (IsBetween(x, pt1.X, pt2.X) && IsBetween(y, pt1.Y, pt2.Y)) {
intersection = new Point((int)x, (int)y);
R = Distance(intersection, pt); }
else {
double d1 = Distance(pt, pt1), d2 = Distance(pt, pt2);
if (d1 < d2) { intersection = pt1; R = d1; }
else { intersection = pt2; R = d2; }}
return R;
}