[解決済み] 点から線分までの最短距離

質問

ある点と線分の最短距離を求める基本的な関数が欲しい。 解答をどのような言語で書いても構いません。

EDIT: 私の線分は2つの端点で定義されています。ですから、私の線分は AB は、2つの点 A (x1,y1) と B (x2,y2) . この線分とある点との距離を求めます。 C (x3,y3) . 私の幾何学のスキルは錆びついているので、私が見た例は分かりにくくて、申し訳ないです。

どのように解決するのですか？

<ストライク エリさん、あなたが決めたコードは間違っています。線分が乗っている線分に近いが、線分の一端から離れている点は、線分に近いと間違って判断される。 更新：記載されている不正解は、もはや認められていないものです。

以下は、C++による正しいコードです。これは、2D-vectorというクラスを想定しています。 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);
}

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

EDIT 2: Javaバージョンが必要だったのですが、もっと重要なのは、2Dではなく3Dで表示する必要があったことです。

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 (が存在すると仮定して）2点間の距離の2乗を求める。