我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
当前回答
上面的函数在垂直线上不起作用。这是一个工作正常的函数! 与点p1 p2相交。CheckPoint为p;
public float DistanceOfPointToLine2(PointF p1, PointF p2, PointF p)
{
// (y1-y2)x + (x2-x1)y + (x1y2-x2y1)
//d(P,L) = --------------------------------
// sqrt( (x2-x1)pow2 + (y2-y1)pow2 )
double ch = (p1.Y - p2.Y) * p.X + (p2.X - p1.X) * p.Y + (p1.X * p2.Y - p2.X * p1.Y);
double del = Math.Sqrt(Math.Pow(p2.X - p1.X, 2) + Math.Pow(p2.Y - p1.Y, 2));
double d = ch / del;
return (float)d;
}
其他回答
对于感兴趣的人,这里是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));
}
以下是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 );
}
在我自己的问题线程如何计算在C, c# / .NET 2.0或Java的所有情况下一个点和线段之间的最短2D距离?当我找到一个c#的答案时,我被要求把它放在这里:所以它是从http://www.topcoder.com/tc?d1=tutorials&d2=geometry1&module=Static修改的:
//Compute the dot product AB . BC
private double DotProduct(double[] pointA, double[] pointB, double[] pointC)
{
double[] AB = new double[2];
double[] BC = new double[2];
AB[0] = pointB[0] - pointA[0];
AB[1] = pointB[1] - pointA[1];
BC[0] = pointC[0] - pointB[0];
BC[1] = pointC[1] - pointB[1];
double dot = AB[0] * BC[0] + AB[1] * BC[1];
return dot;
}
//Compute the cross product AB x AC
private double CrossProduct(double[] pointA, double[] pointB, double[] pointC)
{
double[] AB = new double[2];
double[] AC = new double[2];
AB[0] = pointB[0] - pointA[0];
AB[1] = pointB[1] - pointA[1];
AC[0] = pointC[0] - pointA[0];
AC[1] = pointC[1] - pointA[1];
double cross = AB[0] * AC[1] - AB[1] * AC[0];
return cross;
}
//Compute the distance from A to B
double Distance(double[] pointA, double[] pointB)
{
double d1 = pointA[0] - pointB[0];
double d2 = pointA[1] - pointB[1];
return Math.Sqrt(d1 * d1 + d2 * d2);
}
//Compute the distance from AB to C
//if isSegment is true, AB is a segment, not a line.
double LineToPointDistance2D(double[] pointA, double[] pointB, double[] pointC,
bool isSegment)
{
double dist = CrossProduct(pointA, pointB, pointC) / Distance(pointA, pointB);
if (isSegment)
{
double dot1 = DotProduct(pointA, pointB, pointC);
if (dot1 > 0)
return Distance(pointB, pointC);
double dot2 = DotProduct(pointB, pointA, pointC);
if (dot2 > 0)
return Distance(pointA, pointC);
}
return Math.Abs(dist);
}
我不是要回答问题,而是要问问题,所以我希望我不会因为某些原因而得到数百万张反对票,而是批评。我只是想(并被鼓励)分享其他人的想法,因为这个帖子中的解决方案要么是用一些奇异的语言(Fortran, Mathematica),要么被某人标记为错误。对我来说唯一有用的(由Grumdrig编写)是用c++编写的,没有人标记它有错误。但是它缺少被调用的方法(dot等)。
在javascript中使用几何:
var a = { x:20, y:20};//start segment
var b = { x:40, y:30};//end segment
var c = { x:37, y:14};//point
// magnitude from a to c
var ac = Math.sqrt( Math.pow( ( a.x - c.x ), 2 ) + Math.pow( ( a.y - c.y ), 2) );
// magnitude from b to c
var bc = Math.sqrt( Math.pow( ( b.x - c.x ), 2 ) + Math.pow( ( b.y - c.y ), 2 ) );
// magnitude from a to b (base)
var ab = Math.sqrt( Math.pow( ( a.x - b.x ), 2 ) + Math.pow( ( a.y - b.y ), 2 ) );
// perimeter of triangle
var p = ac + bc + ab;
// area of the triangle
var area = Math.sqrt( p/2 * ( p/2 - ac) * ( p/2 - bc ) * ( p/2 - ab ) );
// height of the triangle = distance
var h = ( area * 2 ) / ab;
console.log ("height: " + h);
在数学
它使用线段的参数描述,并将点投影到线段定义的直线中。当参数在线段内从0到1时,如果投影在这个范围之外,我们计算到相应端点的距离,而不是法线到线段的直线。
Clear["Global`*"];
distance[{start_, end_}, pt_] :=
Module[{param},
param = ((pt - start).(end - start))/Norm[end - start]^2; (*parameter. the "."
here means vector product*)
Which[
param < 0, EuclideanDistance[start, pt], (*If outside bounds*)
param > 1, EuclideanDistance[end, pt],
True, EuclideanDistance[pt, start + param (end - start)] (*Normal distance*)
]
];
策划的结果:
Plot3D[distance[{{0, 0}, {1, 0}}, {xp, yp}], {xp, -1, 2}, {yp, -1, 2}]
画出比截断距离更近的点:
等高线图: