我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
当前回答
特征c++版本的3D线段和点
// Return minimum distance between line segment: head--->tail and point
double MinimumDistance(Eigen::Vector3d head, Eigen::Vector3d tail,Eigen::Vector3d point)
{
double l2 = std::pow((head - tail).norm(),2);
if(l2 ==0.0) return (head - point).norm();// head == tail case
// Consider the line extending the segment, parameterized as head + t (tail - point).
// We find projection of point onto the line.
// It falls where t = [(point-head) . (tail-head)] / |tail-head|^2
// We clamp t from [0,1] to handle points outside the segment head--->tail.
double t = max(0,min(1,(point-head).dot(tail-head)/l2));
Eigen::Vector3d projection = head + t*(tail-head);
return (point - projection).norm();
}
其他回答
下面是devnullicus转换为c#的c++版本。对于我的实现,我需要知道交叉点,并找到他的解决方案。
public static bool PointSegmentDistanceSquared(PointF point, PointF lineStart, PointF lineEnd, out double distance, out PointF intersectPoint)
{
const double kMinSegmentLenSquared = 0.00000001; // adjust to suit. If you use float, you'll probably want something like 0.000001f
const double kEpsilon = 1.0E-14; // adjust to suit. If you use floats, you'll probably want something like 1E-7f
double dX = lineEnd.X - lineStart.X;
double dY = lineEnd.Y - lineStart.Y;
double dp1X = point.X - lineStart.X;
double dp1Y = point.Y - lineStart.Y;
double segLenSquared = (dX * dX) + (dY * dY);
double t = 0.0;
if (segLenSquared >= -kMinSegmentLenSquared && segLenSquared <= kMinSegmentLenSquared)
{
// segment is a point.
intersectPoint = lineStart;
t = 0.0;
distance = ((dp1X * dp1X) + (dp1Y * dp1Y));
}
else
{
// Project a line from p to the segment [p1,p2]. By considering the line
// extending the segment, parameterized as p1 + (t * (p2 - p1)),
// we find projection of point p onto the line.
// It falls where t = [(p - p1) . (p2 - p1)] / |p2 - p1|^2
t = ((dp1X * dX) + (dp1Y * dY)) / segLenSquared;
if (t < kEpsilon)
{
// intersects at or to the "left" of first segment vertex (lineStart.X, lineStart.Y). If t is approximately 0.0, then
// intersection is at p1. If t is less than that, then there is no intersection (i.e. p is not within
// the 'bounds' of the segment)
if (t > -kEpsilon)
{
// intersects at 1st segment vertex
t = 0.0;
}
// set our 'intersection' point to p1.
intersectPoint = lineStart;
// Note: If you wanted the ACTUAL intersection point of where the projected lines would intersect if
// we were doing PointLineDistanceSquared, then intersectPoint.X would be (lineStart.X + (t * dx)) and intersectPoint.Y would be (lineStart.Y + (t * dy)).
}
else if (t > (1.0 - kEpsilon))
{
// intersects at or to the "right" of second segment vertex (lineEnd.X, lineEnd.Y). If t is approximately 1.0, then
// intersection is at p2. If t is greater than that, then there is no intersection (i.e. p is not within
// the 'bounds' of the segment)
if (t < (1.0 + kEpsilon))
{
// intersects at 2nd segment vertex
t = 1.0;
}
// set our 'intersection' point to p2.
intersectPoint = lineEnd;
// Note: If you wanted the ACTUAL intersection point of where the projected lines would intersect if
// we were doing PointLineDistanceSquared, then intersectPoint.X would be (lineStart.X + (t * dx)) and intersectPoint.Y would be (lineStart.Y + (t * dy)).
}
else
{
// The projection of the point to the point on the segment that is perpendicular succeeded and the point
// is 'within' the bounds of the segment. Set the intersection point as that projected point.
intersectPoint = new PointF((float)(lineStart.X + (t * dX)), (float)(lineStart.Y + (t * dY)));
}
// return the squared distance from p to the intersection point. Note that we return the squared distance
// as an optimization because many times you just need to compare relative distances and the squared values
// works fine for that. If you want the ACTUAL distance, just take the square root of this value.
double dpqX = point.X - intersectPoint.X;
double dpqY = point.Y - intersectPoint.Y;
distance = ((dpqX * dpqX) + (dpqY * dpqY));
}
return true;
}
这是一个为有限线段而做的实现,而不是像这里的大多数其他函数那样的无限线(这就是为什么我做这个)。
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;
}
这里没有看到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;
}
}
Lua: 查找线段(不是整条线)与点之间的最小距离
function solveLinearEquation(A1,B1,C1,A2,B2,C2)
--it is the implitaion of a method of solving linear equations in x and y
local f1 = B1*C2 -B2*C1
local f2 = A2*C1-A1*C2
local f3 = A1*B2 -A2*B1
return {x= f1/f3, y= f2/f3}
end
function pointLiesOnLine(x,y,x1,y1,x2,y2)
local dx1 = x-x1
local dy1 = y-y1
local dx2 = x-x2
local dy2 = y-y2
local crossProduct = dy1*dx2 -dx1*dy2
if crossProduct ~= 0 then return false
else
if ((x1>=x) and (x>=x2)) or ((x2>=x) and (x>=x1)) then
if ((y1>=y) and (y>=y2)) or ((y2>=y) and (y>=y1)) then
return true
else return false end
else return false end
end
end
function dist(x1,y1,x2,y2)
local dx = x1-x2
local dy = y1-y2
return math.sqrt(dx*dx + dy* dy)
end
function findMinDistBetnPointAndLine(x1,y1,x2,y2,x3,y3)
-- finds the min distance between (x3,y3) and line (x1,y2)--(x2,y2)
local A2,B2,C2,A1,B1,C1
local dx = y2-y1
local dy = x2-x1
if dx == 0 then A2=1 B2=0 C2=-x3 A1=0 B1=1 C1=-y1
elseif dy == 0 then A2=0 B2=1 C2=-y3 A1=1 B1=0 C1=-x1
else
local m1 = dy/dx
local m2 = -1/m1
A2=m2 B2=-1 C2=y3-m2*x3 A1=m1 B1=-1 C1=y1-m1*x1
end
local intsecPoint= solveLinearEquation(A1,B1,C1,A2,B2,C2)
if pointLiesOnLine(intsecPoint.x, intsecPoint.y,x1,y1,x2,y2) then
return dist(intsecPoint.x, intsecPoint.y, x3,y3)
else
return math.min(dist(x3,y3,x1,y1),dist(x3,y3,x2,y2))
end
end
对于感兴趣的人,这里是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));
}