我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
当前回答
in R
#distance beetween segment ab and point c in 2D space
getDistance_ort_2 <- function(a, b, c){
#go to complex numbers
A<-c(a[1]+1i*a[2],b[1]+1i*b[2])
q=c[1]+1i*c[2]
#function to get coefficients of line (ab)
getAlphaBeta <- function(A)
{ a<-Re(A[2])-Re(A[1])
b<-Im(A[2])-Im(A[1])
ab<-as.numeric()
ab[1] <- -Re(A[1])*b/a+Im(A[1])
ab[2] <-b/a
if(Im(A[1])==Im(A[2])) ab<- c(Im(A[1]),0)
if(Re(A[1])==Re(A[2])) ab <- NA
return(ab)
}
#function to get coefficients of line ortogonal to line (ab) which goes through point q
getAlphaBeta_ort<-function(A,q)
{ ab <- getAlphaBeta(A)
coef<-c(Re(q)/ab[2]+Im(q),-1/ab[2])
if(Re(A[1])==Re(A[2])) coef<-c(Im(q),0)
return(coef)
}
#function to get coordinates of interception point
#between line (ab) and its ortogonal which goes through point q
getIntersection_ort <- function(A, q){
A.ab <- getAlphaBeta(A)
q.ab <- getAlphaBeta_ort(A,q)
if (!is.na(A.ab[1])&A.ab[2]==0) {
x<-Re(q)
y<-Im(A[1])}
if (is.na(A.ab[1])) {
x<-Re(A[1])
y<-Im(q)
}
if (!is.na(A.ab[1])&A.ab[2]!=0) {
x <- (q.ab[1] - A.ab[1])/(A.ab[2] - q.ab[2])
y <- q.ab[1] + q.ab[2]*x}
xy <- x + 1i*y
return(xy)
}
intersect<-getIntersection_ort(A,q)
if ((Mod(A[1]-intersect)+Mod(A[2]-intersect))>Mod(A[1]-A[2])) {dist<-min(Mod(A[1]-q),Mod(A[2]-q))
} else dist<-Mod(q-intersect)
return(dist)
}
其他回答
这是Javascript中最简单的完整代码。
(X, y)是目标点(x1, y)到(x2, y)是线段。
更新:修复了评论中0长度的行问题。
function pDistance(x, y, x1, y1, x2, y2) {
var A = x - x1;
var B = y - y1;
var C = x2 - x1;
var D = y2 - y1;
var dot = A * C + B * D;
var len_sq = C * C + D * D;
var param = -1;
if (len_sq != 0) //in case of 0 length line
param = dot / len_sq;
var xx, yy;
if (param < 0) {
xx = x1;
yy = y1;
}
else if (param > 1) {
xx = x2;
yy = y2;
}
else {
xx = x1 + param * C;
yy = y1 + param * D;
}
var dx = x - xx;
var dy = y - yy;
return Math.sqrt(dx * dx + dy * dy);
}
更新:Kotlin版本
fun getDistance(x: Double, y: Double, x1: Double, y1: Double, x2: Double, y2: Double): Double {
val a = x - x1
val b = y - y1
val c = x2 - x1
val d = y2 - y1
val lenSq = c * c + d * d
val param = if (lenSq != .0) { //in case of 0 length line
val dot = a * c + b * d
dot / lenSq
} else {
-1.0
}
val (xx, yy) = when {
param < 0 -> x1 to y1
param > 1 -> x2 to y2
else -> x1 + param * c to y1 + param * d
}
val dx = x - xx
val dy = y - yy
return hypot(dx, dy)
}
如果它是一条无限大的直线,而不是一条线段,最简单的方法是这样(在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;
下面是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;
}
这个答案是基于公认答案的JavaScript解决方案。 它主要只是格式更好,函数名更长,当然函数语法更短,因为它是在ES6 + CoffeeScript中。
JavaScript版本(ES6)
distanceSquared = (v, w)=> Math.pow(v.x - w.x, 2) + Math.pow(v.y - w.y, 2);
distance = (v, w)=> Math.sqrt(distanceSquared(v, w));
distanceToLineSegmentSquared = (p, v, w)=> {
l2 = distanceSquared(v, w);
if (l2 === 0) {
return distanceSquared(p, v);
}
t = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / l2;
t = Math.max(0, Math.min(1, t));
return distanceSquared(p, {
x: v.x + t * (w.x - v.x),
y: v.y + t * (w.y - v.y)
});
}
distanceToLineSegment = (p, v, w)=> {
return Math.sqrt(distanceToLineSegmentSquared(p, v));
}
CoffeeScript版本
distanceSquared = (v, w)-> (v.x - w.x) ** 2 + (v.y - w.y) ** 2
distance = (v, w)-> Math.sqrt(distanceSquared(v, w))
distanceToLineSegmentSquared = (p, v, w)->
l2 = distanceSquared(v, w)
return distanceSquared(p, v) if l2 is 0
t = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / l2
t = Math.max(0, Math.min(1, t))
distanceSquared(p, {
x: v.x + t * (w.x - v.x)
y: v.y + t * (w.y - v.y)
})
distanceToLineSegment = (p, v, w)->
Math.sqrt(distanceToLineSegmentSquared(p, v, w))