Skip to content

Instantly share code, notes, and snippets.

@mbostock
Last active February 25, 2024 17:46
Show Gist options
  • Save mbostock/8027637 to your computer and use it in GitHub Desktop.
Save mbostock/8027637 to your computer and use it in GitHub Desktop.
Closest Point on Path
license: gpl-3.0

This page demonstrates a simple approximate algorithm for finding the closest point on any given SVG path element. Although the algorithm is not guaranteed to return the best answer, the answer is reasonably good, and the accuracy is tunable at the expense of performance. It is based on Mike Kamermans’ excellent Primer on Bézier Curves.

A coarse linear scan of the path provides an initial guess. Then, a binary search improves the guess to the desired level of precision (here, about 1px). The coarseness of the initial scan is configurable; for paths where there may be multiple close points at different lengths along the path, such as at intersections, a finer initial scan is needed to avoid converging on a suboptimal answer.

Knowing the closest path to a given point is useful for multi-line charts in the same way the Voronoi tessellation is useful for scatterplots: it makes it easier to select or highlight elements using the mouse. Instead of requiring the user to hover over a line precisely, you can use this algorithm to find the line closest to the mouse. Alternatively, you can compute a Voronoi diagram for lines by sampling points along each path.

<!DOCTYPE html>
<meta charset="utf-8">
<style>
path {
fill: none;
stroke: #000;
stroke-width: 1.5px;
}
line {
fill: none;
stroke: red;
stroke-width: 1.5px;
}
circle {
fill: red;
}
rect {
fill: none;
cursor: crosshair;
pointer-events: all;
}
</style>
<body>
<script src="//d3js.org/d3.v3.min.js"></script>
<script>
var points = [[474,276],[586,393],[378,388],[338,323],[341,138],[547,252],[589,148],[346,227],[365,108],[562,62]];
var width = 960,
height = 500;
var line = d3.svg.line()
.interpolate("cardinal");
var svg = d3.select("body").append("svg")
.attr("width", width)
.attr("height", height);
var path = svg.append("path")
.datum(points)
.attr("d", line);
var line = svg.append("line");
var circle = svg.append("circle")
.attr("cx", -10)
.attr("cy", -10)
.attr("r", 3.5);
svg.append("rect")
.attr("width", width)
.attr("height", height)
.on("mousemove", mousemoved);
function mousemoved() {
var m = d3.mouse(this),
p = closestPoint(path.node(), m);
line.attr("x1", p[0]).attr("y1", p[1]).attr("x2", m[0]).attr("y2", m[1]);
circle.attr("cx", p[0]).attr("cy", p[1]);
}
function closestPoint(pathNode, point) {
var pathLength = pathNode.getTotalLength(),
precision = 8,
best,
bestLength,
bestDistance = Infinity;
// linear scan for coarse approximation
for (var scan, scanLength = 0, scanDistance; scanLength <= pathLength; scanLength += precision) {
if ((scanDistance = distance2(scan = pathNode.getPointAtLength(scanLength))) < bestDistance) {
best = scan, bestLength = scanLength, bestDistance = scanDistance;
}
}
// binary search for precise estimate
precision /= 2;
while (precision > 0.5) {
var before,
after,
beforeLength,
afterLength,
beforeDistance,
afterDistance;
if ((beforeLength = bestLength - precision) >= 0 && (beforeDistance = distance2(before = pathNode.getPointAtLength(beforeLength))) < bestDistance) {
best = before, bestLength = beforeLength, bestDistance = beforeDistance;
} else if ((afterLength = bestLength + precision) <= pathLength && (afterDistance = distance2(after = pathNode.getPointAtLength(afterLength))) < bestDistance) {
best = after, bestLength = afterLength, bestDistance = afterDistance;
} else {
precision /= 2;
}
}
best = [best.x, best.y];
best.distance = Math.sqrt(bestDistance);
return best;
function distance2(p) {
var dx = p.x - point[0],
dy = p.y - point[1];
return dx * dx + dy * dy;
}
}
</script>
@averas
Copy link

averas commented Dec 19, 2013

Very useful!

Another similar challenge I've ran into is "the point within a polygon as far away from the boundary as possible". This point is useful for label placements within polygons, especially in irregularly shaped polygons where a simple "polygon center" approach places the label in non-intuitive positions (even outside of the polygon).

Are there any D3 examples addressing this?

@netsi1964
Copy link

Thank you for sharing - great example of use of Web API Interface for SVG.
I have copy and pasted this code to a pen on CodePen, and written a blog post there where I embed it - I have credited you and linked to this Gist: SVG is nice in many ways

@colinmegill
Copy link

This is amazing. 37 & 48 a duplicate declaration?

@luciancd
Copy link

thank you

@cdaringe
Copy link

cdaringe commented Dec 1, 2019

for future visitors, consider tuning the precision to your use case: https://gist.github.com/mbostock/8027637#file-index-html-L69

i made a path editor. as the path got longer, i had originally not adjusted the precision, and the linear scan would take very long. i made the precision value a function of path length, which may be a better default, @mbostock, if we want to adjust the gist :)

var precision = Math.floor(pathLength / 10)

@cdaringe
Copy link

cdaringe commented Dec 1, 2019

coming back just to say thank you!. enabled this: https://github.com/cdaringe/d3-svg-path-editor

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment