Skip to content

Instantly share code, notes, and snippets.

@Fil
Last active July 14, 2017 15:12
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Fil/63eb26b470ed38db1486f230d32ca1e9 to your computer and use it in GitHub Desktop.
Save Fil/63eb26b470ed38db1486f230d32ca1e9 to your computer and use it in GitHub Desktop.
Closest Point on Path d3v4 [UNLISTED]
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.

forked from mbostock's block: Closest Point on Path

forked from Fil's block: Closest Point on Path d3v4 [UNLISTED]

<!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="https://d3js.org/d3.v4.min.js"></script>
<script src="https://d3js.org/d3-hsv.v0.1.min.js"></script>
<script src="https://d3js.org/d3-contour.v1.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 linec = d3.line()
.curve(d3.curveCardinal);
var svg = d3.select("body").append("svg")
.attr("width", width)
.attr("height", height);
var i0 = d3.interpolateHsvLong(d3.hsv(120, 1, 0.65), d3.hsv(60, 1, 0.90)),
i1 = d3.interpolateHsvLong(d3.hsv(60, 1, 0.90), d3.hsv(0, 0, 0.95)),
interpolateTerrain = function(t) { return t < 0.5 ? i0(t * 2) : i1((t - 0.5) * 2); },
color = d3.scaleSequential(interpolateTerrain).domain([90, 190]);
var path = svg.append("path")
.datum(points)
.attr("d", linec);
var pathNode = path.node();
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>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment