我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
当前回答
下面是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;
其他回答
现在我的解决方案...... (Javascript)
这是非常快的,因为我试图避免任何数学。战俘的功能。
如你所见,在函数的最后,我得到了直线的距离。
代码来自lib http://www.draw2d.org/graphiti/jsdoc/#!/例子
/**
* Static util function to determine is a point(px,py) on the line(x1,y1,x2,y2)
* A simple hit test.
*
* @return {boolean}
* @static
* @private
* @param {Number} coronaWidth the accepted corona for the hit test
* @param {Number} X1 x coordinate of the start point of the line
* @param {Number} Y1 y coordinate of the start point of the line
* @param {Number} X2 x coordinate of the end point of the line
* @param {Number} Y2 y coordinate of the end point of the line
* @param {Number} px x coordinate of the point to test
* @param {Number} py y coordinate of the point to test
**/
graphiti.shape.basic.Line.hit= function( coronaWidth, X1, Y1, X2, Y2, px, py)
{
// Adjust vectors relative to X1,Y1
// X2,Y2 becomes relative vector from X1,Y1 to end of segment
X2 -= X1;
Y2 -= Y1;
// px,py becomes relative vector from X1,Y1 to test point
px -= X1;
py -= Y1;
var dotprod = px * X2 + py * Y2;
var projlenSq;
if (dotprod <= 0.0) {
// px,py is on the side of X1,Y1 away from X2,Y2
// distance to segment is length of px,py vector
// "length of its (clipped) projection" is now 0.0
projlenSq = 0.0;
} else {
// switch to backwards vectors relative to X2,Y2
// X2,Y2 are already the negative of X1,Y1=>X2,Y2
// to get px,py to be the negative of px,py=>X2,Y2
// the dot product of two negated vectors is the same
// as the dot product of the two normal vectors
px = X2 - px;
py = Y2 - py;
dotprod = px * X2 + py * Y2;
if (dotprod <= 0.0) {
// px,py is on the side of X2,Y2 away from X1,Y1
// distance to segment is length of (backwards) px,py vector
// "length of its (clipped) projection" is now 0.0
projlenSq = 0.0;
} else {
// px,py is between X1,Y1 and X2,Y2
// dotprod is the length of the px,py vector
// projected on the X2,Y2=>X1,Y1 vector times the
// length of the X2,Y2=>X1,Y1 vector
projlenSq = dotprod * dotprod / (X2 * X2 + Y2 * Y2);
}
}
// Distance to line is now the length of the relative point
// vector minus the length of its projection onto the line
// (which is zero if the projection falls outside the range
// of the line segment).
var lenSq = px * px + py * py - projlenSq;
if (lenSq < 0) {
lenSq = 0;
}
return Math.sqrt(lenSq)<coronaWidth;
};
这是一个为有限线段而做的实现,而不是像这里的大多数其他函数那样的无限线(这就是为什么我做这个)。
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;
}
如果它是一条无限大的直线,而不是一条线段,最简单的方法是这样(在ruby中),其中mx + b是直线,(x1, y1)是已知的点
(y1 - mx1 - b).abs / Math.sqrt(m**2 + 1)
JavaScript中一个基于这个公式的更简洁的解决方案:
distToSegment: function (point, linePointA, linePointB){
var x0 = point.X;
var y0 = point.Y;
var x1 = linePointA.X;
var y1 = linePointA.Y;
var x2 = linePointB.X;
var y2 = linePointB.Y;
var Dx = (x2 - x1);
var Dy = (y2 - y1);
var numerator = Math.abs(Dy*x0 - Dx*y0 - x1*y2 + x2*y1);
var denominator = Math.sqrt(Dx*Dx + Dy*Dy);
if (denominator == 0) {
return this.dist2(point, linePointA);
}
return numerator/denominator;
}
对于感兴趣的人,这里是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));
}