language-agnostic - 点与线段之间的最短距离

Question

我需要一个基本函数来查找点和线段之间的最短距离。随意用您想要的任何语言编写解决方案；我可以将其翻译成我正在使用的内容(Javascript)。

编辑:我的线段由两个端点定义。因此，我的线段 AB 是由两点 A (x1,y1) 和 B (x2,y2) 定义的。我试图找到该线段和点 C (x3,y3) 之间的距离。我的几何技能很生疏，所以我看到的例子很令人困惑，我很遗憾地承认。

Answer 1

Eli，您选择的代码不正确。靠近线段所在线但远离线段一端的点将被错误地判断为靠近线段。 更新:提到的错误答案不再被接受。

这是一些正确的 C++ 代码。它假定一个 2D 向量类 class vec2 {float x,y;} ，本质上是使用加、减、缩放等运算符，以及距离和点积函数(即 x1 x2 + y1 y2 )。

float minimum_distance(vec2 v, vec2 w, vec2 p) {
  // Return minimum distance between line segment vw and point p
  const float l2 = length_squared(v, w);  // i.e. |w-v|^2 -  avoid a sqrt
  if (l2 == 0.0) return distance(p, v);   // v == w case
  // 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
  // We clamp t from [0,1] to handle points outside the segment vw.
  const float t = max(0, min(1, dot(p - v, w - v) / l2));
  const vec2 projection = v + t * (w - v);  // Projection falls on the segment
  return distance(p, projection);
}

编辑:我需要一个 Javascript 实现，所以它就在这里，没有依赖项(或注释，但它是上面的直接端口)。点用 x 表示为对象和y属性。

function sqr(x) { return x * x }
function dist2(v, w) { return sqr(v.x - w.x) + sqr(v.y - w.y) }
function distToSegmentSquared(p, v, w) {
  var l2 = dist2(v, w);
  if (l2 == 0) return dist2(p, v);
  var t = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / l2;
  t = Math.max(0, Math.min(1, t));
  return dist2(p, { x: v.x + t * (w.x - v.x),
                    y: v.y + t * (w.y - v.y) });
}
function distToSegment(p, v, w) { return Math.sqrt(distToSegmentSquared(p, v, w)); }

编辑 2:我需要一个 Java 版本，但更重要的是，我需要 3d 版本而不是 2d 版本。

float dist_to_segment_squared(float px, float py, float pz, float lx1, float ly1, float lz1, float lx2, float ly2, float lz2) {
  float line_dist = dist_sq(lx1, ly1, lz1, lx2, ly2, lz2);
  if (line_dist == 0) return dist_sq(px, py, pz, lx1, ly1, lz1);
  float t = ((px - lx1) * (lx2 - lx1) + (py - ly1) * (ly2 - ly1) + (pz - lz1) * (lz2 - lz1)) / line_dist;
  t = constrain(t, 0, 1);
  return dist_sq(px, py, pz, lx1 + t * (lx2 - lx1), ly1 + t * (ly2 - ly1), lz1 + t * (lz2 - lz1));
}

这里，在函数参数中，<px,py,pz>是有问题的点，线段的端点为 <lx1,ly1,lz1>和<lx2,ly2,lz2> 。函数dist_sq (假设存在)求两点之间距离的平方。