点到线段的最短距离 [英] Shortest distance between a point and a line segment

问题描述

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

I need a basic function to find the shortest distance between a point and a line segment. Feel free to write the solution in any language you want; I can translate it into what I'm using (Javascript).

我的线段由两个端点定义.所以我的线段AB是由A(x1,y1)和B(x2,y2)两点定义的.我试图找出这条线段和点 C (x3,y3) 之间的距离.我的几何技能生疏了，所以我看到的例子很混乱，很抱歉.

My line segment is defined by two endpoints. So my line segment AB is defined by the two points A (x1,y1) and B (x2,y2). I'm trying to find the distance between this line segment and a point C (x3,y3). My geometry skills are rusty, so the examples I've seen are confusing, I'm sorry to admit.

推荐答案

Eli，你确定的代码不正确.靠近线段所在的线但远离线段一端的点会在靠近线段的地方被错误判断. 更新:提到的错误答案不再被接受.

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

Here's some correct code, in C++. It presumes a class 2D-vector class vec2 {float x,y;}, essentially, with operators to add, subract, scale, etc, and a distance and dot product function (i.e. 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 属性的对象.

I needed a Javascript implementation, so here it is, with no dependencies (or comments, but it's a direct port of the above). Points are represented as objects with x and y attributes.

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.

EDIT 2: I needed a Java version, but more important, I needed it in 3d instead of 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>代码> 和 <代码>.dist_sq 函数(假定存在)求两点之间距离的平方.

Here, in the function parameters, <px,py,pz> is the point in question and the line segment has the endpoints <lx1,ly1,lz1> and <lx2,ly2,lz2>. The function dist_sq (which is assumed to exist) finds the square of the distance between two points.

这篇关于点到线段的最短距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！