我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
当前回答
和这个答案一样,只是用的是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
其他回答
在我自己的问题线程如何计算在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等)。
以下是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 );
}
您可以尝试PHP geo-math-php的库
composer require rkondratuk/geo-math-php:^1
例子:
<?php
use PhpGeoMath\Model\GeoSegment;
use PhpGeoMath\Model\Polar3dPoint;
$polarPoint1 = new Polar3dPoint(
40.758742779050706, -73.97855507715238, Polar3dPoint::EARTH_RADIUS_IN_METERS
);
$polarPoint2 = new Polar3dPoint(
40.74843388072615, -73.98566565776102, Polar3dPoint::EARTH_RADIUS_IN_METERS
);
$polarPoint3 = new Polar3dPoint(
40.74919365249446, -73.98133456388013, Polar3dPoint::EARTH_RADIUS_IN_METERS
);
$arcSegment = new GeoSegment($polarPoint1, $polarPoint2);
$nearestPolarPoint = $arcSegment->calcNearestPoint($polarPoint3);
// Shortest distance from point-3 to segment(point-1, point-2)
$geoDistance = $nearestPolarPoint->calcGeoDistanceToPoint($polarPoint3);
这是一个为有限线段而做的实现,而不是像这里的大多数其他函数那样的无限线(这就是为什么我做这个)。
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;
}
这是Javascript中最简单的完整代码。
(X, y)是目标点(x1, y)到(x2, y)是线段。
更新:修复了评论中0长度的行问题。
function pDistance(x, y, x1, y1, x2, y2) {
var A = x - x1;
var B = y - y1;
var C = x2 - x1;
var D = y2 - y1;
var dot = A * C + B * D;
var len_sq = C * C + D * D;
var param = -1;
if (len_sq != 0) //in case of 0 length line
param = dot / len_sq;
var xx, yy;
if (param < 0) {
xx = x1;
yy = y1;
}
else if (param > 1) {
xx = x2;
yy = y2;
}
else {
xx = x1 + param * C;
yy = y1 + param * D;
}
var dx = x - xx;
var dy = y - yy;
return Math.sqrt(dx * dx + dy * dy);
}
更新:Kotlin版本
fun getDistance(x: Double, y: Double, x1: Double, y1: Double, x2: Double, y2: Double): Double {
val a = x - x1
val b = y - y1
val c = x2 - x1
val d = y2 - y1
val lenSq = c * c + d * d
val param = if (lenSq != .0) { //in case of 0 length line
val dot = a * c + b * d
dot / lenSq
} else {
-1.0
}
val (xx, yy) = when {
param < 0 -> x1 to y1
param > 1 -> x2 to y2
else -> x1 + param * c to y1 + param * d
}
val dx = x - xx
val dy = y - yy
return hypot(dx, dy)
}