点と線分の間の最短距離を見つけるための基本的な関数が必要です。 好きな言語で自由にソリューションを書いてください。私が使用している言語 (Javascript) に翻訳できます。
編集: 私の線分は 2 つの端点によって定義されます。つまり、私の線分はAB2 つの点と によって定義されますA (x1,y1)。B (x2,y2)この線分と点の間の距離を求めていますC (x3,y3)。私の幾何学のスキルは鈍いので、私が見た例はわかりにくいです。申し訳ありませんが、認めます。
ベストアンサー1
Eli、あなたが決めたコードは間違っています。線分が位置する線に近いが線分の一方の端からは遠い点は、線分の近くと誤って判断されます。
更新: 記載されている誤った回答は、もはや受け入れられません。
class vec2 {float x,y;}以下は C++ で書かれた正しいコードです。基本的には、加算、減算、スケールなどの演算子と、距離とドット積関数 (つまりx1 x2 + y1 y2)を持つ 2D-vector クラスを想定しています。
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 バージョンが必要でしたが、もっと重要なのは、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 乗を求めます。