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); | |
| } | |
| } | |
| }()); |
