我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(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。
其他回答
下面是HSQLDB的SQL实现:
CREATE FUNCTION dist_to_segment(px double, py double, vx double, vy double, wx double, wy double)
RETURNS double
BEGIN atomic
declare l2 double;
declare t double;
declare nx double;
declare ny double;
set l2 =(vx - wx)*(vx - wx) + (vy - wy)*(vy - wy);
IF l2 = 0 THEN
RETURN sqrt((vx - px)*(vx - px) + (vy - py)*(vy - py));
ELSE
set t = ((px - vx) * (wx - vx) + (py - vy) * (wy - vy)) / l2;
set t = GREATEST(0, LEAST(1, t));
set nx=vx + t * (wx - vx);
set ny=vy + t * (wy - vy);
RETURN sqrt((nx - px)*(nx - px) + (ny - py)*(ny - py));
END IF;
END;
Postgres的实现:
CREATE FUNCTION dist_to_segment(px numeric, py numeric, vx numeric, vy numeric, wx numeric, wy numeric)
RETURNS numeric
AS $$
declare l2 numeric;
declare t numeric;
declare nx numeric;
declare ny numeric;
BEGIN
l2 := (vx - wx)*(vx - wx) + (vy - wy)*(vy - wy);
IF l2 = 0 THEN
RETURN sqrt((vx - px)*(vx - px) + (vy - py)*(vy - py));
ELSE
t := ((px - vx) * (wx - vx) + (py - vy) * (wy - vy)) / l2;
t := GREATEST(0, LEAST(1, t));
nx := vx + t * (wx - vx);
ny := vy + t * (wy - vy);
RETURN sqrt((nx - px)*(nx - px) + (ny - py)*(ny - py));
END IF;
END;
$$ LANGUAGE plpgsql;
本想在GLSL中这样做,但如果可能的话,最好避免所有这些条件。使用clamp()可以避免两种端点情况:
// find closest point to P on line segment AB:
vec3 closest_point_on_line_segment(in vec3 P, in vec3 A, in vec3 B) {
vec3 AP = P - A, AB = B - A;
float l = dot(AB, AB);
if (l <= 0.0000001) return A; // A and B are practically the same
return AP - AB*clamp(dot(AP, AB)/l, 0.0, 1.0); // do the projection
}
如果您可以确定A和B彼此不会非常接近,则可以简化为删除If()。事实上,即使A和B是相同的,我的GPU仍然给出了这个无条件版本的正确结果(但这是使用pre-OpenGL 4.1,其中GLSL除零是未定义的):
// find closest point to P on line segment AB:
vec3 closest_point_on_line_segment(in vec3 P, in vec3 A, in vec3 B) {
vec3 AP = P - A, AB = B - A;
return AP - AB*clamp(dot(AP, AB)/dot(AB, AB), 0.0, 1.0);
}
计算距离是很简单的——GLSL提供了一个distance()函数,你可以在这个最近的点和P。
灵感来自Iñigo Quilez的胶囊距离函数代码
用Matlab直接实现Grumdrig
function ans=distP2S(px,py,vx,vy,wx,wy)
% [px py vx vy wx wy]
t=( (px-vx)*(wx-vx)+(py-vy)*(wy-vy) )/idist(vx,wx,vy,wy)^2;
[idist(px,vx,py,vy) idist(px,vx+t*(wx-vx),py,vy+t*(wy-vy)) idist(px,wx,py,wy) ];
ans(1+(t>0)+(t>1)); % <0 0<=t<=1 t>1
end
function d=idist(a,b,c,d)
d=abs(a-b+1i*(c-d));
end
这是一个为有限线段而做的实现,而不是像这里的大多数其他函数那样的无限线(这就是为什么我做这个)。
Paul Bourke的理论实施。
Python:
def dist(x1, y1, x2, y2, x3, y3): # x3,y3 is the point
px = x2-x1
py = y2-y1
norm = px*px + py*py
u = ((x3 - x1) * px + (y3 - y1) * py) / float(norm)
if u > 1:
u = 1
elif u < 0:
u = 0
x = x1 + u * px
y = y1 + u * py
dx = x - x3
dy = y - y3
# Note: If the actual distance does not matter,
# if you only want to compare what this function
# returns to other results of this function, you
# can just return the squared distance instead
# (i.e. remove the sqrt) to gain a little performance
dist = (dx*dx + dy*dy)**.5
return dist
AS3:
public static function segmentDistToPoint(segA:Point, segB:Point, p:Point):Number
{
var p2:Point = new Point(segB.x - segA.x, segB.y - segA.y);
var something:Number = p2.x*p2.x + p2.y*p2.y;
var u:Number = ((p.x - segA.x) * p2.x + (p.y - segA.y) * p2.y) / something;
if (u > 1)
u = 1;
else if (u < 0)
u = 0;
var x:Number = segA.x + u * p2.x;
var y:Number = segA.y + u * p2.y;
var dx:Number = x - p.x;
var dy:Number = y - p.y;
var dist:Number = Math.sqrt(dx*dx + dy*dy);
return dist;
}
Java
private double shortestDistance(float x1,float y1,float x2,float y2,float x3,float y3)
{
float px=x2-x1;
float py=y2-y1;
float temp=(px*px)+(py*py);
float u=((x3 - x1) * px + (y3 - y1) * py) / (temp);
if(u>1){
u=1;
}
else if(u<0){
u=0;
}
float x = x1 + u * px;
float y = y1 + u * py;
float dx = x - x3;
float dy = y - y3;
double dist = Math.sqrt(dx*dx + dy*dy);
return dist;
}
我制作了一个交互式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。