我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
当前回答
这是一个为有限线段而做的实现,而不是像这里的大多数其他函数那样的无限线(这就是为什么我做这个)。
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;
}
其他回答
I'm assuming you want to find the shortest distance between the point and a line segment; to do this, you need to find the line (lineA) which is perpendicular to your line segment (lineB) which goes through your point, determine the intersection between that line (lineA) and your line which goes through your line segment (lineB); if that point is between the two points of your line segment, then the distance is the distance between your point and the point you just found which is the intersection of lineA and lineB; if the point is not between the two points of your line segment, you need to get the distance between your point and the closer of two ends of the line segment; this can be done easily by taking the square distance (to avoid a square root) between the point and the two points of the line segment; whichever is closer, take the square root of that one.
嘿,我昨天才写的。它在Actionscript 3.0中,基本上是Javascript,尽管你可能没有相同的Point类。
//st = start of line segment
//b = the line segment (as in: st + b = end of line segment)
//pt = point to test
//Returns distance from point to line segment.
//Note: nearest point on the segment to the test point is right there if we ever need it
public static function linePointDist( st:Point, b:Point, pt:Point ):Number
{
var nearestPt:Point; //closest point on seqment to pt
var keyDot:Number = dot( b, pt.subtract( st ) ); //key dot product
var bLenSq:Number = dot( b, b ); //Segment length squared
if( keyDot <= 0 ) //pt is "behind" st, use st
{
nearestPt = st
}
else if( keyDot >= bLenSq ) //pt is "past" end of segment, use end (notice we are saving twin sqrts here cuz)
{
nearestPt = st.add(b);
}
else //pt is inside segment, reuse keyDot and bLenSq to get percent of seqment to move in to find closest point
{
var keyDotToPctOfB:Number = keyDot/bLenSq; //REM dot product comes squared
var partOfB:Point = new Point( b.x * keyDotToPctOfB, b.y * keyDotToPctOfB );
nearestPt = st.add(partOfB);
}
var dist:Number = (pt.subtract(nearestPt)).length;
return dist;
}
此外,这里有一个关于这个问题的相当完整和可读的讨论:notejot.com
这里没有看到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;
}
}
公认的答案行不通 (例如,0,0和(-10,2,10,2)之间的距离应为2)。
下面是工作代码:
def dist2line2(x,y,line):
x1,y1,x2,y2=line
vx = x1 - x
vy = y1 - y
ux = x2-x1
uy = y2-y1
length = ux * ux + uy * uy
det = (-vx * ux) + (-vy * uy) #//if this is < 0 or > length then its outside the line segment
if det < 0:
return (x1 - x)**2 + (y1 - y)**2
if det > length:
return (x2 - x)**2 + (y2 - y)**2
det = ux * vy - uy * vx
return det**2 / length
def dist2line(x,y,line): return math.sqrt(dist2line2(x,y,line))
在f#中,点c到a和b之间的线段的距离为:
let pointToLineSegmentDistance (a: Vector, b: Vector) (c: Vector) =
let d = b - a
let s = d.Length
let lambda = (c - a) * d / s
let p = (lambda |> max 0.0 |> min s) * d / s
(a + p - c).Length
向量d沿着线段从a指向b。d/s与c-a的点积给出了无限直线与点c之间最接近点的参数。使用min和max函数将该参数钳制到范围0..s,使该点位于a和b之间。最后,a+p-c的长度是c到线段上最近点的距离。
使用示例:
pointToLineSegmentDistance (Vector(0.0, 0.0), Vector(1.0, 0.0)) (Vector(-1.0, 1.0))