我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
当前回答
基于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)
}
其他回答
对于感兴趣的人,这里是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));
}
这里没有看到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;
}
}
快速实现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))
}
这是一个基于向量数学的;这个解决方案也适用于更高的维度,并报告交点(在线段上)。
def dist(x1,y1,x2,y2,px,py):
a = np.array([[x1,y1]]).T
b = np.array([[x2,y2]]).T
x = np.array([[px,py]]).T
tp = (np.dot(x.T, b) - np.dot(a.T, b)) / np.dot(b.T, b)
tp = tp[0][0]
tmp = x - (a + tp*b)
d = np.sqrt(np.dot(tmp.T,tmp)[0][0])
return d, a+tp*b
x1,y1=2.,2.
x2,y2=5.,5.
px,py=4.,1.
d, inters = dist(x1,y1, x2,y2, px,py)
print (d)
print (inters)
结果是
2.1213203435596424
[[2.5]
[2.5]]
这里解释了数学
https://brilliant.org/wiki/distance-between-point-and-line/
这是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)
}