我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
当前回答
嘿,我昨天才写的。它在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
其他回答
这里它使用Swift
/* Distance from a point (p1) to line l1 l2 */
func distanceFromPoint(p: CGPoint, toLineSegment l1: CGPoint, and l2: CGPoint) -> CGFloat {
let A = p.x - l1.x
let B = p.y - l1.y
let C = l2.x - l1.x
let D = l2.y - l1.y
let dot = A * C + B * D
let len_sq = C * C + D * D
let param = dot / len_sq
var xx, yy: CGFloat
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
}
let dx = p.x - xx
let dy = p.y - yy
return sqrt(dx * dx + dy * dy)
}
以下是Grumdrig解决方案的一个更完整的说明。这个版本还返回最近的点本身。
#include "stdio.h"
#include "math.h"
class Vec2
{
public:
float _x;
float _y;
Vec2()
{
_x = 0;
_y = 0;
}
Vec2( const float x, const float y )
{
_x = x;
_y = y;
}
Vec2 operator+( const Vec2 &v ) const
{
return Vec2( this->_x + v._x, this->_y + v._y );
}
Vec2 operator-( const Vec2 &v ) const
{
return Vec2( this->_x - v._x, this->_y - v._y );
}
Vec2 operator*( const float f ) const
{
return Vec2( this->_x * f, this->_y * f );
}
float DistanceToSquared( const Vec2 p ) const
{
const float dX = p._x - this->_x;
const float dY = p._y - this->_y;
return dX * dX + dY * dY;
}
float DistanceTo( const Vec2 p ) const
{
return sqrt( this->DistanceToSquared( p ) );
}
float DotProduct( const Vec2 p ) const
{
return this->_x * p._x + this->_y * p._y;
}
};
// return minimum distance between line segment vw and point p, and the closest point on the line segment, q
float DistanceFromLineSegmentToPoint( const Vec2 v, const Vec2 w, const Vec2 p, Vec2 * const q )
{
const float distSq = v.DistanceToSquared( w ); // i.e. |w-v|^2 ... avoid a sqrt
if ( distSq == 0.0 )
{
// v == w case
(*q) = v;
return v.DistanceTo( p );
}
// consider the line extending the segment, parameterized as v + t (w - v)
// we find projection of point p onto the line
// it falls where t = [(p-v) . (w-v)] / |w-v|^2
const float t = ( p - v ).DotProduct( w - v ) / distSq;
if ( t < 0.0 )
{
// beyond the v end of the segment
(*q) = v;
return v.DistanceTo( p );
}
else if ( t > 1.0 )
{
// beyond the w end of the segment
(*q) = w;
return w.DistanceTo( p );
}
// projection falls on the segment
const Vec2 projection = v + ( ( w - v ) * t );
(*q) = projection;
return p.DistanceTo( projection );
}
float DistanceFromLineSegmentToPoint( float segmentX1, float segmentY1, float segmentX2, float segmentY2, float pX, float pY, float *qX, float *qY )
{
Vec2 q;
float distance = DistanceFromLineSegmentToPoint( Vec2( segmentX1, segmentY1 ), Vec2( segmentX2, segmentY2 ), Vec2( pX, pY ), &q );
(*qX) = q._x;
(*qY) = q._y;
return distance;
}
void TestDistanceFromLineSegmentToPoint( float segmentX1, float segmentY1, float segmentX2, float segmentY2, float pX, float pY )
{
float qX;
float qY;
float d = DistanceFromLineSegmentToPoint( segmentX1, segmentY1, segmentX2, segmentY2, pX, pY, &qX, &qY );
printf( "line segment = ( ( %f, %f ), ( %f, %f ) ), p = ( %f, %f ), distance = %f, q = ( %f, %f )\n",
segmentX1, segmentY1, segmentX2, segmentY2, pX, pY, d, qX, qY );
}
void TestDistanceFromLineSegmentToPoint()
{
TestDistanceFromLineSegmentToPoint( 0, 0, 1, 1, 1, 0 );
TestDistanceFromLineSegmentToPoint( 0, 0, 20, 10, 5, 4 );
TestDistanceFromLineSegmentToPoint( 0, 0, 20, 10, 30, 15 );
TestDistanceFromLineSegmentToPoint( 0, 0, 20, 10, -30, 15 );
TestDistanceFromLineSegmentToPoint( 0, 0, 10, 0, 5, 1 );
TestDistanceFromLineSegmentToPoint( 0, 0, 0, 10, 1, 5 );
}
GLSL版:
// line (a -> b ) point p[enter image description here][1]
float distanceToLine(vec2 a, vec2 b, vec2 p) {
float aside = dot((p - a),(b - a));
if(aside< 0.0) return length(p-a);
float bside = dot((p - b),(a - b));
if(bside< 0.0) return length(p-b);
vec2 pointOnLine = (bside*a + aside*b)/pow(length(a-b),2.0);
return length(p - pointOnLine);
}
WPF版本:
public class LineSegment
{
private readonly Vector _offset;
private readonly Vector _vector;
public LineSegment(Point start, Point end)
{
_offset = (Vector)start;
_vector = (Vector)(end - _offset);
}
public double DistanceTo(Point pt)
{
var v = (Vector)pt - _offset;
// first, find a projection point on the segment in parametric form (0..1)
var p = (v * _vector) / _vector.LengthSquared;
// and limit it so it lays inside the segment
p = Math.Min(Math.Max(p, 0), 1);
// now, find the distance from that point to our point
return (_vector * p - v).Length;
}
}
公认的答案行不通 (例如,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))