kragen/README.md

## README.md

      
    Raw
  

              README.md
            
          
    This page demonstrates a simple approximate algorithm for finding the closest point on any given SVG path element.
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). To account for kinks in the path that can cause the binary scan to get stuck in a local minimum, the coarseness of the initial scan is dependent on the number of path segments. I doubt this algorithm is provably correct, but it seems to produce fairly good results even for the kinky path shown above. This technique is based on Mike Kamermans’ excellent Primer on Bézier Curves.
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.

  
## index.html
<!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="http://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 pathLen = pathNode.getTotalLength(),
      precision = pathLen / pathNode.pathSegList.numberOfItems * .125,
      best,
      bestLen,
      bestDistance = Infinity;

  // linear scan for coarse approximation
  for (var scan, scanLen = 0, scanDistance; scanLen <= pathLen; scanLen += precision) {
    if ((scanDistance = distance2(scan = pathNode.getPointAtLength(scanLen))) < bestDistance) {
      best = scan, bestLen = scanLen, bestDistance = scanDistance;
    }
  }

  // binary search for precise estimate
  precision *= .5;
  while (precision > .5) {
    var before,
        after,
        beforeLen,
        afterLen,
        beforeDistance,
        afterDistance;
    if ((beforeLen = bestLen - precision) >= 0
        && (beforeDistance = distance2(before = pathNode.getPointAtLength(beforeLen)))
            < bestDistance) {
      best = before, bestLen = beforeLen, bestDistance = beforeDistance;
    } else if ((afterLen = bestLen + precision) <= pathLen
               && (afterDistance = distance2(after = pathNode.getPointAtLength(afterLen)))
                  < bestDistance) {
      best = after, bestLen = afterLen, bestDistance = afterDistance;
    } else {
      precision *= .5;
    }
  }

  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>

## thumbnail.png

      
    Raw
  

              thumbnail.png
	<!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="http://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 pathLen = pathNode.getTotalLength(),
	precision = pathLen / pathNode.pathSegList.numberOfItems * .125,
	best,
	bestLen,
	bestDistance = Infinity;

	// linear scan for coarse approximation
	for (var scan, scanLen = 0, scanDistance; scanLen <= pathLen; scanLen += precision) {
	if ((scanDistance = distance2(scan = pathNode.getPointAtLength(scanLen))) < bestDistance) {
	best = scan, bestLen = scanLen, bestDistance = scanDistance;
	}
	}

	// binary search for precise estimate
	precision *= .5;
	while (precision > .5) {
	var before,
	after,
	beforeLen,
	afterLen,
	beforeDistance,
	afterDistance;
	if ((beforeLen = bestLen - precision) >= 0
	&& (beforeDistance = distance2(before = pathNode.getPointAtLength(beforeLen)))
	< bestDistance) {
	best = before, bestLen = beforeLen, bestDistance = beforeDistance;
	} else if ((afterLen = bestLen + precision) <= pathLen
	&& (afterDistance = distance2(after = pathNode.getPointAtLength(afterLen)))
	< bestDistance) {
	best = after, bestLen = afterLen, bestDistance = afterDistance;
	} else {
	precision *= .5;
	}
	}

	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>