Quadtree
This interactive visualization demonstrates a quadtree spatial index in action. The page displays 5,000 randomly positioned points as small gray circles, overlaid with the quadtree's recursive subdivision rectangles. Users can drag a rectangular brush to select a region; as the brush moves, the quadtree traversal highlights every point whose quadrant was scanned in orange while marking points contained in the selection in red. The visualization efficiently filters points by recursively checking only relevant quadrants, with the quadtree's internal bounds (x1, x2, y1, y2) stored in each node. A performance optimization ensures only nodes visited by the quadtree—plus the previous selection—are updated, rather than all 5,000 points, resulting in faster brush response. The quadtree structure itself is shown with faint gray rectangles, and points are rendered as circles.
AI-generated descriptionChanges in this fork:
- index.html : Original file looped through all nodes:
point.each(function(d) { d.scanned = d.selected = false; });This version only touches the nodes scanned by the quadtree (and the previous selection), resulting in faster response - quadtree.js : Experiment in internalizing the area (x1,x2,y1,y2) of each quadrant within each node-object
See original <a href="http://bl.ocks.org/mbostock/4343214">here</a>