Quadtree

100%

✓ Published0🌍 Public

Last edited Jun 1, 2018

Created on Jun 1, 2018

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.

AI-generated description

This example demonstrates accelerated two-dimensional filtering enabled by d3-quadtree. A quadtree recursively subdivides square cells into four equal-sized subcells. Each leaf node of the quadtree contains a single point. If a given quadtree cell does not intersect the brush extent, then none of the points contained in that subtree can be selected, and thus do not need to be scanned. Above, orange indicates points that are scanned but not selected. Without a quadtree, all points would need to be scanned!

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

mit Licensed

Similar vizzes

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

91% 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

85% match

Loading thumbnail…

Quadtree Search

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.

FFrissAnalytics

85% 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

79% 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

79% match

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

78% match

Loading thumbnail…

Scatter plot brushing

This example demonstrates interactive brushing on a scatter plot, where users can drag a rectangular selection to highlight points within that region in orange while dimming others remain blue. The visualization uses 300 randomly generated data points from a normal distribution, rendered as SVG circles with axes. The brushing interaction is implemented using d3.brush, with the brushed event updating circle fills based on the selection bounds, while brushended resets the colors with a smooth transition when the brush is cleared. The code uses d3.scaleLinear for positioning and d3.axisBottom/axisLeft for axes.

EEfratVil

74% match

Loading thumbnail…

Brush Transitions

Five thousand random points are drawn in an SVG scatterplot. A draggable brush region highlights points inside it in red, and after the mouse is released, the brush smoothly animates back to its original position from the default extent. The example uses D3’s `d3.svg.brush`, `d3.geom.quadtree` for efficient point selection, and a transition on the brush call to animate the extent, interrupting any ongoing transition if the user interacts again.

FFrissAnalytics

71% match