我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(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。
其他回答
我制作了一个交互式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。
快速实现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))
}
以下是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 );
}
公认的答案行不通 (例如,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))
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.