Display labels for points close to the mouse cursor. Could be used to display multiple tooltips, etc.
Uses k-nearest-neighbors algorithm from this block by llb4ll. Check the box to see the underlying quadtree (red points are the nearest points, orange are those that were searched but found to be not among the nearest).
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Labeling Nearest Points</title>
</head>
<style>
body {
font: 14px sans-serif;
}
.show-quadtree {
position: absolute;
left: 800px;
top: 30px;
}
.node {
fill: rgb(230, 230, 230);
fill-opacity: 0;
stroke: rgb(230, 230, 230);
stroke-width: .5px;
}
.node:hover {
fill-opacity: .2;
}
.node.hidden {
opacity: 0;
}
.point {
fill: rgb(149, 149, 149);
}
.point.scanned {
fill: orange;
}
.point.selected {
fill: red;
}
.point.uncolored {
fill: rgb(149, 149, 149);
}
</style>
<body>
<label class="show-quadtree">
Show quadtree
<input type="checkbox">
</label>
<script src="https://cdnjs.cloudflare.com/ajax/libs/underscore.js/1.8.3/underscore-min.js"></script>
<script src="//d3js.org/d3.v3.min.js" charset="utf-8"></script>
<script src="k-nearest-neighbors.js"></script>
<script>
var width = 960,
height = 500;
var svg = d3.select("body").append("svg")
.attr("width", width)
.attr("height", height);
var eventRect = svg.append("rect")
.attr("class", "event-rect")
.attr("width", width)
.attr("height", height)
.style("opacity", 0);
var data = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".split("")
.map(function(letter) {
var d = [Math.random() * width, Math.random() * height];
d.letter = letter;
return d;
});
var quadtree = d3.geom.quadtree()
.extent([[-1, -1], [width + 1, height + 1]])(data);
var circles = svg.selectAll(".point").data(data)
.enter().append("circle")
.attr("class", "point")
.attr("cx", function(d) { return d[0]; })
.attr("cy", function(d) { return d[1]; })
.attr("r", 5)
.classed("uncolored", true);
var rects = svg.selectAll(".node").data(kNearest.nodes(quadtree))
.enter().append("rect")
.attr("class", "node")
.attr("x", function(d) { return d.x1; })
.attr("y", function(d) { return d.y1; })
.attr("width", function(d) { return d.x2 - d.x1; })
.attr("height", function(d) { return d.y2 - d.y1; })
.classed("hidden", true)
.on("mousemove", mousemove);
var labels = svg.selectAll(".label").data(d3.range(4))
.enter().append("text")
.attr("class", "label")
.attr("dy", -10)
.style("font-size", "14px")
.style("font-weight", "bold")
.style("text-anchor", "middle");
var throttledUpdate = _.throttle(function(mouse) {
updateNearest(mouse);
updateTooltip(mouse);
}, 100);
function mousemove(d) {
throttledUpdate(d3.mouse(this));
}
function updateTooltip(mouse) {
var selected = circles
.filter(function(d) { return d.selected; });
labels.data(selected.data())
.classed("hidden", false)
.attr("x", function(d) { return d[0]; })
.attr("y", function(d) { return d[1]; })
.text(function(d) { return d.letter; });
}
d3.select(".show-quadtree input")
.on("change", function() {
rects.classed("hidden", !this.checked);
circles.classed("uncolored", !this.checked);
});
function updateNearest(coords) {
var x = coords[0],
y = coords[1];
circles.each(function(d) { d.scanned = d.selected = false; d.mindist = undefined; });
rects.each(function(d) { d.visited = false; d.mindist = undefined; });
var bestqueue = new Array(quadtree);
var resultqueue = [];
kNearest.neighbors(bestqueue, resultqueue, x, y, 4);
circles.classed("scanned", function(d) { return d.scanned; });
circles.classed("selected", function(d) { return d.selected; });
}
</script>
</body>
</html>
// source: http://bl.ocks.org/llb4ll/8709363
var kNearest = {};
(function() {
kNearest.nodes = nodes;
kNearest.neighbors = knearest;
// PDS Collect a list of nodes to draw rectangles, adding extent and depth data
function nodes(quadtree) {
var nodes = [];
quadtree.depth = 0; // root
quadtree.visit(function(node, x1, y1, x2, y2) {
node.x1 = x1;
node.y1 = y1;
node.x2 = x2;
node.y2 = y2;
nodes.push(node);
for (var i=0; i<4; i++) {
if (node.nodes[i]) node.nodes[i].depth = node.depth+1;
}
});
return nodes;
}
// calculate euclidean distance of two points with coordinates: a(ax, ay) and b(bx, by)
function euclidDistance(ax, ay, bx, by){
return Math.sqrt(Math.pow(ax-bx, 2) + Math.pow(ay-by, 2));
}
// calculate mindist between searchpoint and rectangle
function mindist(x, y, x1, y1, x2, y2){
var dx1 = x - x1, dx2 = x - x2, dy1 = y - y1, dy2 = y - y2;
if (dx1*dx2 < 0) { // x is between x1 and x2
if (dy1*dy2 < 0) { // (x,y) is inside the rectangle
return 0; // return 0 as point is in rect
}
return Math.min(Math.abs(dy1),Math.abs(dy2));
}
if (dy1*dy2 < 0) { // y is between y1 and y2
// we don't have to test for being inside the rectangle, it's already tested.
return Math.min(Math.abs(dx1),Math.abs(dx2));
}
return Math.min( Math.min(euclidDistance(x,y,x1,y1),euclidDistance(x,y,x2,y2)), Math.min(euclidDistance(x,y,x1,y2),euclidDistance(x,y,x2,y1)) );
}
// Find the nodes within the specified rectangle.
function knearest(bestqueue, resultqueue, x, y, k) {
// sort children according to their mindist/dist to searchpoint
bestqueue.sort(function(a, b){
// add minidst to nodes if not there already
[a, b].forEach(function(val, idx, array){
if(val.mindist == undefined){
val.scanned = true;
if(val.leaf){
val.point.scanned=true;
val.mindist = euclidDistance(x, y, val.x, val.y);
}else{
val.mindist = mindist(x, y, val.x1, val.y1, val.x2, val.y2);
}
}
});
return b.mindist - a.mindist;
});
// add nearest leafs if any
for (var i=bestqueue.length-1; i>=0; i--){
var elem = bestqueue[i];
if(elem.leaf){
elem.point.selected = true;
bestqueue.pop();
resultqueue.push(elem);
}else{
break;
}
if(resultqueue.length >=k){
break;
}
}
// check if enough points found
if(resultqueue.length >=k || bestqueue.length == 0){
// return if k neighbors found
return;
}else{
// add child nodes to bestqueue and recurse
var vistitednode = bestqueue.pop();
vistitednode.visited = true;
// add nodes to queue
vistitednode.nodes.forEach(function(val, idx, array){
bestqueue.push(val);
});
// recursion
knearest(bestqueue, resultqueue, x, y, k);
}
}
}());