Quadtree Search

100%

Quadtree Search

✓ Published0🌍 Public

Last edited Dec 3, 2016

Created on Dec 3, 2016

This example visualizes a quadtree spatial index by rendering its hierarchical rectangular cells as SVG rectangles. As the mouse moves, it searches the quadtree for the nearest of 2,500 randomly generated points, highlighting the closest point in red. The visualization uses the d3.quadtree API to build and search the index, with d3.select and d3.mouse handling mouse events. The quadtree’s cells are drawn via the visit method, while points are displayed as SVG circles.

AI-generated description

This demonstrates finding the closest point to the mouse by searching a quadtree. As you descend into the quadtree, you track the closest point yet found and avoid searching cells that cannot contain closer points. Importantly, you must descend preferentially into closer cells so as to restrict the search more quickly.

Patrick Surry implemented a similar solution months earlier!

forked from <a href='http://bl.ocks.org/mbostock/'>mbostock</a>'s block: <a href='http://bl.ocks.org/mbostock/9078690'>Quadtree Search</a>

gpl-3.0 Licensed

Similar vizzes

Loading thumbnail…

Quadtree Search

This example shows a quadtree search for the nearest point to the mouse cursor among 2,500 randomly generated points. As the cursor moves, the closest point is highlighted in red. The visualization renders the quadtree’s subdivisions as gray rectangles and the points as black circles using SVG. It uses d3.quadtree with the find method, along with d3.mouse and quadtree.visit to display the search hierarchy.

Mmbostock

91% match

Loading thumbnail…

Quadtree

A quadtree accelerates two-dimensional point filtering in an interactive scatterplot. The visualization shows 2,500 random points that users select by dragging a rectangular brush. Orange points are scanned by the algorithm but not selected, while red points fall within the brush extent. The code uses d3.quadtree to recursively subdivide space and d3.brush for interaction, rendering SVG circles and cell outlines.

FFrissAnalytics

85% match

Loading thumbnail…

Quadtree - nearest neighbor

Clicking on the diagram places a yellow query point and a quadtree nearest-neighbor search identifies its closest orange base point, highlighted red. The d3.geom.quadtree recursively visits green rectangles, with color saturation indicating depth, while untested base points remain gray. Only orange points are measured for Euclidean distance, and the code uses d3.svg and SVG circles and rectangles to render the animated search process.

FFrissAnalytics

84% match

Loading thumbnail…

Quadtree

This example demonstrates accelerated two-dimensional filtering using d3-quadtree. A quadtree recursively subdivides square cells into four equal-sized subcells, with each leaf containing a single point from a dataset of 2,500 randomly generated coordinates. When a d3.brush selection is dragged, the quadtree’s visit method only scans points in intersecting cells, coloring scanned-but-unselected points orange and selected points red. The SVG rendering shows the quadtree’s subdivision rectangles in gray, highlighting how the algorithm avoids checking points outside the brush extent.

Mmbostock

82% match

Loading thumbnail…

Animated Quadtree

This animation demonstrates how a quadtree structure changes as new points are added, displaying each red dot as a point, gray rectangles as leaf nodes, and black lines as internal boundaries. The code uses the `d3_quadtree` JavaScript library with `tree.add`, `tree.visit`, and canvas rendering via `getContext("2d")`. Points are generated using `d3_random.randomNormal` to create a normal distribution centered at the midpoint of the canvas, with each addition triggering a partial redraw to highlight the affected region.

Mmbostock

77% match

Loading thumbnail…

Scatterplots with D3 and Quadtrees

A scatterplot of 50 randomly generated points uses interactive brushing to highlight selected data, listing their labels and recoloring them in tomato. The implementation leverages a quadtree for efficient spatial lookup, and a "Reveal quadtree" button triggers a slowed animation of the quadtree traversal during brushing. Built with D3 v4, the visualization renders in SVG and uses `d3.scaleLinear`, `d3.axisBottom`, `d3.axisLeft`, and a custom `d3.quadtree` structure.

FFrissAnalytics

76% match

Loading thumbnail…

Delaunay Triangulation

This interactive demonstration shows a Delaunay triangulation of 100 randomly generated points, with triangles and links redrawn in real time as the user moves the mouse. The first point follows the cursor, highlighting all triangles and links connected to it in red and white. Built with d3.v4 and the d3-voronoi API, it uses SVG paths, lines, and circles to render the triangulation, updating the visualization dynamically on mousemove and touchmove events.

Mmbostock

69% match

Loading thumbnail…

Gist 79ed32828a2db39ec232

This example demonstrates a divide-and-conquer binary search tree constructed over a set of disjoint line segments that span a horizontal strip, with endpoints on two parallel lines. It visualizes how the segments partition the strip into regions and how a query point can be located by traversing the tree. The code uses D3.js with SVG to draw the segments, circles, and tree edges, and employs custom helper functions like `dataAppend` and `translate` from d3-jetpack. The tree is built by recursively splitting the sorted list of bottom endpoints, and the visualization highlights the connection between the geometric arrangement and the hierarchical search structure.

11wheel

67% match