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

问题描述

我需要一个基本功能来查找点和线段之间的最短距离。随意用您想要的任何语言编写解决方案;我可以将它翻译成我正在使用的（Javascript）。

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

解决方案

Eli，你解决的代码是不正确的。 更新：提及的不正确答案已不再被接受。

这是C ++中的一些正确的代码。它假设一个类2D向量 class vec2 {float x，y;} ，本质上，操作符用于添加，删除，缩放等，以及距离和点乘积函数（即 x1 x2 + y1 y2 ）。

  float minimum_distance（vec2 v，vec2 w，vec2 p）{
 //返回线段vw和点p 
之间的最小距离const float l2 = length_squared（v，w）; //即| w-v | ^ 2  - 如果（l2 == 0.0）返回距离（p，v），则避免sqrt 
; // v == w case 
 //考虑扩展段的行，参数化为v + t（w  -  v）。 
 //我们找到投影点p到线上。 
 //它落在t = [（p-v））。 （w-v）] / | w-v | ^ 2 
 //我们用[0,1]来钳位t以处理段vw外的点。 
 const float t = max（0，min（1，dot（p-v，w-v）/ l2））; 
 const vec2 projection = v + t *（w  -  v）; //投影落在段
返回距离（p，投影）; 
 
 
 
 
 
编辑：我需要一个Javascript实现，所以在这里，没有依赖关系（或评论，但它是上述的直接端口）。点表示为具有 x 和 y 属性的对象。
 
 
 < （x，x）{返回x * x} 
函数dist2（v，w）{return sqr（vx  -  wx）+ sqr （vy  -  wy）} 
 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。
 $ b 
  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））; 
} 
  
 
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).

EDIT: 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, the code you've settled on is incorrect. A point near the line on which the segment lies but far off one end of the segment would be incorrectly judged near the segment. Update: The incorrect answer mentioned is no longer the accepted one.

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);
}
EDIT: 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)); }
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));
}


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