Adapted https://bl.ocks.org/mbostock/4343214 for search for points in a radius.
Last active
November 5, 2019 00:11
-
-
Save wonga00/3987b9736d5077501ef5ee0409ea93c1 to your computer and use it in GitHub Desktop.
In radius search with d3.quadtree
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <!DOCTYPE html> | |
| <style> | |
| .point { | |
| fill: #000; | |
| fill-opacity: 0.4; | |
| } | |
| .point--scanned { | |
| fill: orange; | |
| fill-opacity: 1; | |
| stroke: orange; | |
| stroke-width: 3px; | |
| } | |
| .point--selected { | |
| fill: red; | |
| fill-opacity: 1; | |
| stroke: red; | |
| stroke-width: 5px; | |
| } | |
| .node { | |
| fill: none; | |
| stroke: #ccc; | |
| shape-rendering: crispEdges; | |
| } | |
| .circle-selection { | |
| fill: rgba(0, 0, 0, 0.2); | |
| } | |
| </style> | |
| <svg width="960" height="500"></svg> | |
| <script src="https://d3js.org/d3.v4.min.js"></script> | |
| <script> | |
| var svg = d3.select("svg"), | |
| width = +svg.attr("width"), | |
| height = +svg.attr("height"), | |
| cx = 100, | |
| cy = 100, | |
| searchRadius = 80, | |
| selected; | |
| var random = Math.random, | |
| data = d3.range(2500).map(function() { return [random() * width, random() * height]; }); | |
| var quadtree = d3.quadtree() | |
| // .extent([[-1, -1], [width + 1, height + 1]]) | |
| .addAll(data); | |
| svg.selectAll(".node") | |
| .data(nodes(quadtree)) | |
| .enter().append("rect") | |
| .attr("class", "node") | |
| .attr("x", function(d) { return d.x0; }) | |
| .attr("y", function(d) { return d.y0; }) | |
| .attr("width", function(d) { return d.y1 - d.y0; }) | |
| .attr("height", function(d) { return d.x1 - d.x0; }); | |
| var point = 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", 2); | |
| svg.append("circle") | |
| .attr("class", "circle-selection") | |
| .attr('cx', cx) | |
| .attr('cy', cy) | |
| .attr('r', searchRadius); | |
| function highlightSearch() { | |
| point.each(function(d) { d.scanned = d.selected = false; }); | |
| search(quadtree, cx, cy, 100); | |
| point.classed("point--scanned", function(d) { return d.scanned; }); | |
| point.classed("point--selected", function(d) { return d.selected; }); | |
| } | |
| function inCircle(x, y, cx, cy, radius) { | |
| return (x - cx) * (x - cx) + (y - cy) * (y- cy) < radius * radius; | |
| } | |
| function rectCircleIntersect(rx, ry, rwidth, rheight, cx, cy, radius) { | |
| let dx = cx - Math.max(rx, Math.min(cx, rx + rwidth)); | |
| let dy = cy - Math.max(ry, Math.min(cy, ry + rheight)); | |
| return (dx * dx + dy * dy) < (radius * radius); | |
| } | |
| // Find the nodes within the specified circle. | |
| function search(quadtree, cx, cy, radius) { | |
| quadtree.visit(function(node, x1, y1, x2, y2) { | |
| if (!node.length) { | |
| do { | |
| var d = node.data; | |
| d.scanned = true; | |
| d.selected = inCircle(d[0], d[1], cx, cy, searchRadius); | |
| } while (node = node.next); | |
| } | |
| return !rectCircleIntersect(x1, y1, x2 - x1, y2 - y1, cx, cy, searchRadius); | |
| }); | |
| } | |
| // Collapse the quadtree into an array of rectangles. | |
| function nodes(quadtree) { | |
| var nodes = []; | |
| quadtree.visit(function(node, x0, y0, x1, y1) { | |
| node.x0 = x0, node.y0 = y0; | |
| node.x1 = x1, node.y1 = y1; | |
| nodes.push(node); | |
| return (x1 - x0) < 5; | |
| }); | |
| return nodes; | |
| } | |
| highlightSearch(); | |
| </script> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment