30:T564,// used for the demo, see below for an actual function you can reuse function findInCircleMark(quadtree, x, y, radius) { const result = []; // this function will be called for all accepted nodes function accept(d) { result.push(d); } // Visit the quadtree from the top, recursively quadtree.visit(function(node, x1, y1, x2, y2) { if (node.length) { // this node is not a leaf: mark that we visited it node.visited = true; // if ⟨x,y⟩ is outside the quad + a margin of radius, we know that there is no point // in that quad’s hierarchy that is at a distance < radius: eliminate the quad by returning truthy return ( x1 >= x + radius || y1 >= y + radius || x2 < x - radius || y2 < y - radius ); } // this is a leaf node: it contains 1 point in node.data do { // mark that we visited it const d = node.data; d.visited = true; // measure its euclidian distance to and accept it if < radius if (Math.hypot(d[0] - x, d[1] - y) < radius) accept(d); } while ((node = node.next)); // the do...while chained call is used to test coincident points—which would belong // to the same leaf node; in our case with random points, however, this test is useless // as the probability of coincident points is 0. }); return result; }31:T5f5,function chart() { const svg = d3 .create("svg") .attr("viewBox", [0, 0, width, height]) .style("cursor", "crosshair"), quad = svg .selectAll(".node") .data(materialize(quadtree)) .enter() .append("rect") .attr("class", "node") .attr("x", d => d.x0) .attr("y", d => d.y0) .attr("width", d => d.y1 - d.y0) .attr("height", d => d.x1 - d.x0), circle = svg .selectAll(".radius") .data([radius]) .join("circle") .attr("r", d => d) .attr("class", "radius") .attr("stroke", "orange"), point = svg .selectAll("circle") .data(data) .enter() .append("circle") .attr("cx", d => d[0]) .attr("cy", d => d[1]) .attr("r", 2); svg.on("mousemove click", move); move(); return svg.node(); function move(event) { const [x, y] = this ? d3.pointer(event, this) : [200, 200]; // reset the visited property quad.each(q => (q.node.visited = false)); point.each(d => (d.visited = false)); // search (will set visited on the traversed nodes) const one = quadtree.find(x, y, radius), all = findInCircleMark(quadtree, x, y, radius); // add the relevant classes on the svg marks quad.classed("visited", d => d.node.visited); point .classed("visited", d => d.visited) .classed("all", d => all.includes(d)) .classed("find", d => d === one); // move the radius circle circle.attr("cx", x).attr("cy", y); } }32:[] 2e:{"title":"Quadtree.findInCircle","cells":[{"id":0,"value":"# Quadtree.findInCircle\n\nIn the chart below, ${data.length} data points have been indexed in a quadtree. When the user moves or clicks at coordinates *x, y*, we can use [*quadtree*.find](https://d3js.org/d3-quadtree#quadtree_find) to locate the closest point in that tree, within a certain *radius* (shown as a red dot).\n\nHowever if instead of the closest point, we want to find *all* the points within that same radius (shown as orange dots), we can traverse the tree recursively with [*quadtree*.visit](https://d3js.org/d3-quadtree#quadtree_visit)(), and a function that will ignore any branch (or “quad”) that is too far from the mouse to contain any relevant point.\n\nThe nodes (quads and points) scanned during this quadtree visit are shown in black.","pinned":false,"hidden":false,"mode":"md"},{"id":182,"value":"chart()","pinned":false,"hidden":false,"mode":"ojs"},{"id":274,"value":"viewof radius = Inputs.range([0, 150], {label: \"search radius\", step: 1, value: 80})","pinned":false,"hidden":false,"mode":"ojs"},{"id":111,"value":"$30","pinned":true,"hidden":false,"mode":"ojs"},{"id":300,"value":"Here’s the actual function that one would use to search within a radius. It has an added *filter*, accepts *x* and *y* accessors (and it doesn’t try to mark the visited nodes):","pinned":false,"hidden":false,"mode":"md"},{"id":299,"value":"function findInCircle(quadtree, x, y, radius, filter) {\n const result = [],\n radius2 = radius * radius,\n accept = filter\n ? d => filter(d) && result.push(d)\n : d => result.push(d);\n\n quadtree.visit(function(node, x1, y1, x2, y2) {\n if (node.length) {\n return x1 >= x + radius || y1 >= y + radius || x2 < x - radius || y2 < y - radius;\n }\n\n const dx = +quadtree._x.call(null, node.data) - x,\n dy = +quadtree._y.call(null, node.data) - y;\n if (dx * dx + dy * dy < radius2) {\n do { accept(node.data); } while (node = node.next);\n }\n });\n \n return result;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":298,"value":"quadtree = d3\n .quadtree()\n .extent([[-1, -1], [width + 1, height + 1]])\n .addAll(data)","pinned":true,"hidden":false,"mode":"ojs"},{"id":397,"value":"---\n\nThe following code is for the demo:","pinned":false,"hidden":false,"mode":"md"},{"id":2,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":13,"value":"// Materialize the quadtree into an array of rectangles.\nfunction materialize(quadtree) {\n const rects = [];\n quadtree.visit((node, x0, y0, x1, y1) => {\n rects.push({ x0, y0, x1, y1, node });\n });\n return rects;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":20,"value":"data = {\n const randomx = d3.randomUniform(0, width),\n randomy = d3.randomUniform(0, height);\n return Array.from({ length: 2500 }, () => [randomx(), randomy()]);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":7,"value":"html`\n`","pinned":true,"hidden":false,"mode":"ojs"},{"id":25,"value":"height = 500","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W32","stdlib":"1","titling":"auto"}