Let AB be a line segment specified by the endpoints A and B. Given an arbitrary
point Q, the problem is to determine the point P on AB closest to Q.
We can view this problem in terms of voronoi regions.
Projecting Q onto the extended line through AB provides the solution.
If the projection point P lies within the segment, P itself is the correct answer. If P lies outside the segment, it is instead the segment endpoint closest to C that is the closest point.
Any point on the line through AB can be expressed parametrically as P(t) = A +
t (B − A). Using the projective properties of the dot product, the t corresponding
to the projection of C onto the line is given by t = (C − A) · n/ length(B − A), where
n = (B − A)/ length(B − A) is a unit vector in the direction of AB.
Because the closest point on the line segment is required, t must be clamped to the
interval 0 ≤ t ≤ 1, after which P can be obtained by substituting t into the parametric
equation.
Implemented, this becomes:
class Segment {
static getPointOnSegmentClosestToPoint(point, linePoint1, linePoint2) {
// create a vector from the point to the first line point
var p1ToP = point.difference(linePoint1);
// create a vector representing the line
var line = linePoint2.difference(linePoint1);
// get the length squared of the line
var ab2 = line.dot(line);
// get the projection of AP on AB
var ap_ab = p1ToP.dot(line);
// check ab2 for zero (linePoint1 == linePoint2)
if (ab2 <= Epsilon.E) return linePoint1.copy();
// get the position from the first line point to the projection
var t = ap_ab / ab2;
// make sure t is in between 0.0 and 1.0
t = Interval.clamp(t, 0.0, 1.0);
// create the point on the line
return line.multiply(t).add(linePoint1);
}
}If divisions are expensive, the division operation can be postponed by multiplying both sides of the comparisons by the denominator, which as a square term is
guaranteed to be nonnegative
void ClosestPtPointSegment(Point c, Point a, Point b, float &t, Point &d)
{
Vector ab = b – a;
// Project c onto ab, but deferring divide by Dot(ab, ab)
t = Dot(c – a, ab);
if (t <= 0.0f) {
// c projects outside the [a,b] interval, on the a side; clamp to a
t = 0.0f;
d = a;
} else {
float denom = Dot(ab, ab); // Always nonnegative since denom = ||ab||∧2
if (t >= denom) {
// c projects outside the [a,b] interval, on the b side; clamp to b
t = 1.0f;
d = b;
} else {
// c projects inside the [a,b] interval; must do deferred divide now
t=t/ denom;
d = a + t * ab;
}
}
}Implementation using glmatrix by Claudio Esperança
// Returns the point on line segment q-r closest to point p
function closestSegmentPoint(p, q, r) {
let s = vec2.dist(q,r);
if (s < 0.00001) return q; // Degenerate line segment - both endpoints at approximately the same distance
let v = vec2.normalize([],vec2.sub([],r,q));
let u = vec2.sub([],p,q);
let d = vec2.dot(u,v);
if (d < 0) return q;
if (d > s) return r;
return vec2.lerp ([], q, r, d/s)
}
Useful References
Comments