我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
当前回答
我制作了一个交互式Desmos图来演示如何实现这一点:
https://www.desmos.com/calculator/kswrm8ddum
红点是A点,绿点是B点,C点是蓝色点。 您可以拖动图形中的点来查看值的变化。 左边的值“s”是线段的参数(即s = 0表示点A, s = 1表示点B)。 值“d”是第三点到经过A和B的直线的距离。
编辑:
有趣的小见解:坐标(s, d)是坐标系中第三点C的坐标,AB是单位x轴,单位y轴垂直于AB。
其他回答
GLSL版:
// line (a -> b ) point p[enter image description here][1]
float distanceToLine(vec2 a, vec2 b, vec2 p) {
float aside = dot((p - a),(b - a));
if(aside< 0.0) return length(p-a);
float bside = dot((p - b),(a - b));
if(bside< 0.0) return length(p-b);
vec2 pointOnLine = (bside*a + aside*b)/pow(length(a-b),2.0);
return length(p - pointOnLine);
}
这是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)
}
在数学
它使用线段的参数描述,并将点投影到线段定义的直线中。当参数在线段内从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}]
画出比截断距离更近的点:
等高线图:
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)
}
这里没有看到Java实现,所以我将Javascript函数从接受的答案转换为Java代码:
static double sqr(double x) {
return x * x;
}
static double dist2(DoublePoint v, DoublePoint w) {
return sqr(v.x - w.x) + sqr(v.y - w.y);
}
static double distToSegmentSquared(DoublePoint p, DoublePoint v, DoublePoint w) {
double l2 = dist2(v, w);
if (l2 == 0) return dist2(p, v);
double t = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / l2;
if (t < 0) return dist2(p, v);
if (t > 1) return dist2(p, w);
return dist2(p, new DoublePoint(
v.x + t * (w.x - v.x),
v.y + t * (w.y - v.y)
));
}
static double distToSegment(DoublePoint p, DoublePoint v, DoublePoint w) {
return Math.sqrt(distToSegmentSquared(p, v, w));
}
static class DoublePoint {
public double x;
public double y;
public DoublePoint(double x, double y) {
this.x = x;
this.y = y;
}
}