我需要一个基本函数来查找点与线段之间最短的距离。您可以使用任何编程语言编写解决方案,我可以将其转换为我正在使用的语言(Javascript)。
编辑:我的线段由两个端点定义。因此,我的线段AB
由两个点A(x1,y1)
和B(x2,y2)
定义。我正在尝试查找该线段与点C(x3,y3)
之间的距离。我的几何技能有些生疏,所以我看到的示例很令人困惑,对此我感到抱歉。
我需要一个基本函数来查找点与线段之间最短的距离。您可以使用任何编程语言编写解决方案,我可以将其转换为我正在使用的语言(Javascript)。
编辑:我的线段由两个端点定义。因此,我的线段AB
由两个点A(x1,y1)
和B(x2,y2)
定义。我正在尝试查找该线段与点C(x3,y3)
之间的距离。我的几何技能有些生疏,所以我看到的示例很令人困惑,对此我感到抱歉。
这里没有看到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;
}
}
上面的函数对垂直线不起作用。这是一个运行良好的函数! 带有点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;
}
// line (a -> b ) point p[enter image description here][1]
float distanceToLine(vec2 a, vec2 b, vec2 p) {
float aside = dot((p - a),(b - a));
if(aside< 0.0) return length(p-a);
float bside = dot((p - b),(a - b));
if(bside< 0.0) return length(p-b);
vec2 pointOnLine = (bside*a + aside*b)/pow(length(a-b),2.0);
return length(p - pointOnLine);
}
def dist(x1,y1,x2,y2,px,py):
a = np.array([[x1,y1]]).T
b = np.array([[x2,y2]]).T
x = np.array([[px,py]]).T
tp = (np.dot(x.T, b) - np.dot(a.T, b)) / np.dot(b.T, b)
tp = tp[0][0]
tmp = x - (a + tp*b)
d = np.sqrt(np.dot(tmp.T,tmp)[0][0])
return d, a+tp*b
x1,y1=2.,2.
x2,y2=5.,5.
px,py=4.,1.
d, inters = dist(x1,y1, x2,y2, px,py)
print (d)
print (inters)
2.1213203435596424
[[2.5]
[2.5]]
这里解释了数学问题
{x:5, y:7}
。请注意,这不是绝对最有效的方法,但这是我能想到的最简单和最易于理解的代码。// a, b, and c in the code below are all points
function distance(a, b)
{
var dx = a.x - b.x;
var dy = a.y - b.y;
return Math.sqrt(dx*dx + dy*dy);
}
function Segment(a, b)
{
var ab = {
x: b.x - a.x,
y: b.y - a.y
};
var length = distance(a, b);
function cross(c) {
return ab.x * (c.y-a.y) - ab.y * (c.x-a.x);
};
this.distanceFrom = function(c) {
return Math.min(distance(a,c),
distance(b,c),
Math.abs(cross(c) / length));
};
}
%Matlab solution by Tim from Cody
function ans=distP2S(x0,y0,x1,y1,x2,y2)
% Point is x0,y0
z=complex(x0-x1,y0-y1);
complex(x2-x1,y2-y1);
abs(z-ans*min(1,max(0,real(z/ans))));
这里是与C++答案相同的内容,但已移植到Pascal。点参数的顺序已更改以适应我的代码,但是本质相同。
function Dot(const p1, p2: PointF): double;
begin
Result := p1.x * p2.x + p1.y * p2.y;
end;
function SubPoint(const p1, p2: PointF): PointF;
begin
result.x := p1.x - p2.x;
result.y := p1.y - p2.y;
end;
function ShortestDistance2(const p,v,w : PointF) : double;
var
l2,t : double;
projection,tt: PointF;
begin
// Return minimum distance between line segment vw and point p
//l2 := length_squared(v, w); // i.e. |w-v|^2 - avoid a sqrt
l2 := Distance(v,w);
l2 := MPower(l2,2);
if (l2 = 0.0) then begin
result:= Distance(p, v); // v == w case
exit;
end;
// 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
t := Dot(SubPoint(p,v),SubPoint(w,v)) / l2;
if (t < 0.0) then begin
result := Distance(p, v); // Beyond the 'v' end of the segment
exit;
end
else if (t > 1.0) then begin
result := Distance(p, w); // Beyond the 'w' end of the segment
exit;
end;
//projection := v + t * (w - v); // Projection falls on the segment
tt.x := v.x + t * (w.x - v.x);
tt.y := v.y + t * (w.y - v.y);
result := Distance(p, tt);
end;
Double Distance(Point a, Point b)
{
double xdiff = a.X - b.X, ydiff = a.Y - b.Y;
return Math.Sqrt((long)xdiff * xdiff + (long)ydiff * ydiff);
}
Boolean IsBetween(double x, double a, double b)
{
return ((a <= b && x >= a && x <= b) || (a > b && x <= a && x >= b));
}
Double GetDistance(Point pt, Point pt1, Point pt2, out Point intersection)
{
Double a, x, y, R;
if (pt1.X != pt2.X) {
a = (double)(pt2.Y - pt1.Y) / (pt2.X - pt1.X);
x = (a * (pt.Y - pt1.Y) + a * a * pt1.X + pt.X) / (a * a + 1);
y = a * x + pt1.Y - a * pt1.X; }
else { x = pt1.X; y = pt.Y; }
if (IsBetween(x, pt1.X, pt2.X) && IsBetween(y, pt1.Y, pt2.Y)) {
intersection = new Point((int)x, (int)y);
R = Distance(intersection, pt); }
else {
double d1 = Distance(pt, pt1), d2 = Distance(pt, pt2);
if (d1 < d2) { intersection = pt1; R = d1; }
else { intersection = pt2; R = d2; }}
return R;
}
解决Dart和Flutter的方案:
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);
}
// find closest point to P on line segment AB:
vec3 closest_point_on_line_segment(in vec3 P, in vec3 A, in vec3 B) {
vec3 AP = P - A, AB = B - A;
float l = dot(AB, AB);
if (l <= 0.0000001) return A; // A and B are practically the same
return AP - AB*clamp(dot(AP, AB)/l, 0.0, 1.0); // do the projection
}
如果您可以确定A和B永远不会非常接近彼此,那么可以简化为删除if()。事实上,即使A和B是相同的,在没有条件的情况下,我的GPU仍然可以使用这个版本来给出正确的结果(但这是使用OpenGL 4.1之前的版本,在GLSL除以零未定义的情况下):
// find closest point to P on line segment AB:
vec3 closest_point_on_line_segment(in vec3 P, in vec3 A, in vec3 B) {
vec3 AP = P - A, AB = B - A;
return AP - AB*clamp(dot(AP, AB)/dot(AB, AB), 0.0, 1.0);
}
LineString
类。 - TC1