我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(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。
其他回答
快速实现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))
}
用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
在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);
现在我的解决方案...... (Javascript)
这是非常快的,因为我试图避免任何数学。战俘的功能。
如你所见,在函数的最后,我得到了直线的距离。
代码来自lib http://www.draw2d.org/graphiti/jsdoc/#!/例子
/**
* Static util function to determine is a point(px,py) on the line(x1,y1,x2,y2)
* A simple hit test.
*
* @return {boolean}
* @static
* @private
* @param {Number} coronaWidth the accepted corona for the hit test
* @param {Number} X1 x coordinate of the start point of the line
* @param {Number} Y1 y coordinate of the start point of the line
* @param {Number} X2 x coordinate of the end point of the line
* @param {Number} Y2 y coordinate of the end point of the line
* @param {Number} px x coordinate of the point to test
* @param {Number} py y coordinate of the point to test
**/
graphiti.shape.basic.Line.hit= function( coronaWidth, X1, Y1, X2, Y2, px, py)
{
// Adjust vectors relative to X1,Y1
// X2,Y2 becomes relative vector from X1,Y1 to end of segment
X2 -= X1;
Y2 -= Y1;
// px,py becomes relative vector from X1,Y1 to test point
px -= X1;
py -= Y1;
var dotprod = px * X2 + py * Y2;
var projlenSq;
if (dotprod <= 0.0) {
// px,py is on the side of X1,Y1 away from X2,Y2
// distance to segment is length of px,py vector
// "length of its (clipped) projection" is now 0.0
projlenSq = 0.0;
} else {
// switch to backwards vectors relative to X2,Y2
// X2,Y2 are already the negative of X1,Y1=>X2,Y2
// to get px,py to be the negative of px,py=>X2,Y2
// the dot product of two negated vectors is the same
// as the dot product of the two normal vectors
px = X2 - px;
py = Y2 - py;
dotprod = px * X2 + py * Y2;
if (dotprod <= 0.0) {
// px,py is on the side of X2,Y2 away from X1,Y1
// distance to segment is length of (backwards) px,py vector
// "length of its (clipped) projection" is now 0.0
projlenSq = 0.0;
} else {
// px,py is between X1,Y1 and X2,Y2
// dotprod is the length of the px,py vector
// projected on the X2,Y2=>X1,Y1 vector times the
// length of the X2,Y2=>X1,Y1 vector
projlenSq = dotprod * dotprod / (X2 * X2 + Y2 * Y2);
}
}
// Distance to line is now the length of the relative point
// vector minus the length of its projection onto the line
// (which is zero if the projection falls outside the range
// of the line segment).
var lenSq = px * px + py * py - projlenSq;
if (lenSq < 0) {
lenSq = 0;
}
return Math.sqrt(lenSq)<coronaWidth;
};
JavaScript中一个基于这个公式的更简洁的解决方案:
distToSegment: function (point, linePointA, linePointB){
var x0 = point.X;
var y0 = point.Y;
var x1 = linePointA.X;
var y1 = linePointA.Y;
var x2 = linePointB.X;
var y2 = linePointB.Y;
var Dx = (x2 - x1);
var Dy = (y2 - y1);
var numerator = Math.abs(Dy*x0 - Dx*y0 - x1*y2 + x2*y1);
var denominator = Math.sqrt(Dx*Dx + Dy*Dy);
if (denominator == 0) {
return this.dist2(point, linePointA);
}
return numerator/denominator;
}