StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p><strike>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.</strike> <em>Update: The incorrect answer mentioned is no longer the accepted one.</em></p> <p>Here's some correct code, in C++. It presumes a class 2D-vector <code>class vec2 {float x,y;}</code>, essentially, with operators to add, subract, scale, etc, and a distance and dot product function (i.e. <code>x1 x2 + y1 y2</code>).</p> <pre class="lang-c++ prettyprint-override"><code>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); } </code></pre> <p>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 <code>x</code> and <code>y</code> attributes.</p> <pre class="lang-javascript prettyprint-override"><code>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)); } </code></pre> <p>EDIT 2: I needed a Java version, but more important, I needed it in 3d instead of 2d.</p> <pre class="lang-java prettyprint-override"><code>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)); } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload