我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
当前回答
快速实现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))
}
其他回答
下面是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;
};
只是遇到了这个,我想我应该添加一个Lua实现。它假设点以表{x=xVal, y=yVal}给出,直线或线段由包含两个点的表给出(见下面的例子):
function distance( P1, P2 )
return math.sqrt((P1.x-P2.x)^2 + (P1.y-P2.y)^2)
end
-- Returns false if the point lies beyond the reaches of the segment
function distPointToSegment( line, P )
if line[1].x == line[2].x and line[1].y == line[2].y then
print("Error: Not a line!")
return false
end
local d = distance( line[1], line[2] )
local t = ((P.x - line[1].x)*(line[2].x - line[1].x) + (P.y - line[1].y)*(line[2].y - line[1].y))/(d^2)
local projection = {}
projection.x = line[1].x + t*(line[2].x-line[1].x)
projection.y = line[1].y + t*(line[2].y-line[1].y)
if t >= 0 and t <= 1 then -- within line segment?
return distance( projection, {x=P.x, y=P.y} )
else
return false
end
end
-- Returns value even if point is further down the line (outside segment)
function distPointToLine( line, P )
if line[1].x == line[2].x and line[1].y == line[2].y then
print("Error: Not a line!")
return false
end
local d = distance( line[1], line[2] )
local t = ((P.x - line[1].x)*(line[2].x - line[1].x) + (P.y - line[1].y)*(line[2].y - line[1].y))/(d^2)
local projection = {}
projection.x = line[1].x + t*(line[2].x-line[1].x)
projection.y = line[1].y + t*(line[2].y-line[1].y)
return distance( projection, {x=P.x, y=P.y} )
end
使用示例:
local P1 = {x = 0, y = 0}
local P2 = {x = 10, y = 10}
local line = { P1, P2 }
local P3 = {x = 7, y = 15}
print(distPointToLine( line, P3 )) -- prints 5.6568542494924
print(distPointToSegment( line, P3 )) -- prints false
和这个答案一样,只是用的是Visual Basic。使其可作为Microsoft Excel和VBA/宏中的用户定义函数使用。
函数返回点(x,y)到由(x1,y1)和(x2,y2)定义的线段的最近距离。
Function DistanceToSegment(x As Double, y As Double, x1 As Double, y1 As Double, x2 As Double, y2 As Double)
Dim A As Double
A = x - x1
Dim B As Double
B = y - y1
Dim C As Double
C = x2 - x1
Dim D As Double
D = y2 - y1
Dim dot As Double
dot = A * C + B * D
Dim len_sq As Double
len_sq = C * C + D * D
Dim param As Double
param = -1
If (len_sq <> 0) Then
param = dot / len_sq
End If
Dim xx As Double
Dim yy As Double
If (param < 0) Then
xx = x1
yy = y1
ElseIf (param > 1) Then
xx = x2
yy = y2
Else
xx = x1 + param * C
yy = y1 + param * D
End If
Dim dx As Double
dx = x - xx
Dim dy As Double
dy = y - yy
DistanceToSegment = Math.Sqr(dx * dx + dy * dy)
End Function
这是一个为有限线段而做的实现,而不是像这里的大多数其他函数那样的无限线(这就是为什么我做这个)。
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;
}