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.
AI-generated descriptionThis 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!