我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。
编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。
当前回答
用Matlab直接实现Grumdrig
function ans=distP2S(px,py,vx,vy,wx,wy)
% [px py vx vy wx wy]
t=( (px-vx)*(wx-vx)+(py-vy)*(wy-vy) )/idist(vx,wx,vy,wy)^2;
[idist(px,vx,py,vy) idist(px,vx+t*(wx-vx),py,vy+t*(wy-vy)) idist(px,wx,py,wy) ];
ans(1+(t>0)+(t>1)); % <0 0<=t<=1 t>1
end
function d=idist(a,b,c,d)
d=abs(a-b+1i*(c-d));
end
其他回答
使用arctangents的一行解决方案:
思路是将A移动到(0,0),并顺时针旋转三角形,使C位于X轴上, 当这种情况发生时,By就是距离。
a角= Atan(Cy - Ay, Cx - Ax); b角= Atan(By - Ay, Bx - Ax); AB长度=平方根((Bx - Ax)²+ (By - Ay)²) By = Sin (bAngle - aAngle) * ABLength
C#
public double Distance(Point a, Point b, Point c)
{
// normalize points
Point cn = new Point(c.X - a.X, c.Y - a.Y);
Point bn = new Point(b.X - a.X, b.Y - a.Y);
double angle = Math.Atan2(bn.Y, bn.X) - Math.Atan2(cn.Y, cn.X);
double abLength = Math.Sqrt(bn.X*bn.X + bn.Y*bn.Y);
return Math.Sin(angle)*abLength;
}
一行c#(要转换为SQL)
double distance = Math.Sin(Math.Atan2(b.Y - a.Y, b.X - a.X) - Math.Atan2(c.Y - a.Y, c.X - a.X)) * Math.Sqrt((b.X - a.X) * (b.X - a.X) + (b.Y - a.Y) * (b.Y - a.Y))
嘿,我昨天才写的。它在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
这是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)
}
省道和颤振的解决方法:
import 'dart:math' as math;
class Utils {
static double shortestDistance(Point p1, Point p2, Point p3){
double px = p2.x - p1.x;
double py = p2.y - p1.y;
double temp = (px*px) + (py*py);
double u = ((p3.x - p1.x)*px + (p3.y - p1.y)* py) /temp;
if(u>1){
u=1;
}
else if(u<0){
u=0;
}
double x = p1.x + u*px;
double y = p1.y + u*py;
double dx = x - p3.x;
double dy = y - p3.y;
double dist = math.sqrt(dx*dx+dy*dy);
return dist;
}
}
class Point {
double x;
double y;
Point(this.x, this.y);
}
Consider this modification to Grumdrig's answer above. Many times you'll find that floating point imprecision can cause problems. I'm using doubles in the version below, but you can easily change to floats. The important part is that it uses an epsilon to handle the "slop". In addition, you'll many times want to know WHERE the intersection happened, or if it happened at all. If the returned t is < 0.0 or > 1.0, no collision occurred. However, even if no collision occurred, many times you'll want to know where the closest point on the segment to P is, and thus I use qx and qy to return this location.
double PointSegmentDistanceSquared( double px, double py,
double p1x, double p1y,
double p2x, double p2y,
double& t,
double& qx, double& qy)
{
static const double kMinSegmentLenSquared = 0.00000001; // adjust to suit. If you use float, you'll probably want something like 0.000001f
static const double kEpsilon = 1.0E-14; // adjust to suit. If you use floats, you'll probably want something like 1E-7f
double dx = p2x - p1x;
double dy = p2y - p1y;
double dp1x = px - p1x;
double dp1y = py - p1y;
const double segLenSquared = (dx * dx) + (dy * dy);
if (segLenSquared >= -kMinSegmentLenSquared && segLenSquared <= kMinSegmentLenSquared)
{
// segment is a point.
qx = p1x;
qy = p1y;
t = 0.0;
return ((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 (p1x, p1y). 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.
qx = p1x;
qy = p1y;
// Note: If you wanted the ACTUAL intersection point of where the projected lines would intersect if
// we were doing PointLineDistanceSquared, then qx would be (p1x + (t * dx)) and qy would be (p1y + (t * dy)).
}
else if (t > (1.0 - kEpsilon))
{
// intersects at or to the "right" of second segment vertex (p2x, p2y). 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.
qx = p2x;
qy = p2y;
// Note: If you wanted the ACTUAL intersection point of where the projected lines would intersect if
// we were doing PointLineDistanceSquared, then qx would be (p1x + (t * dx)) and qy would be (p1y + (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.
qx = p1x + (t * dx);
qy = p1y + (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 = px - qx;
double dpqy = py - qy;
return ((dpqx * dpqx) + (dpqy * dpqy));
}
}