Glossary · Rendering
Spatial Indexing
Also known as: Quadtree, R-tree.
A data structure (typically a quadtree or R-tree) that lets a renderer answer "which nodes are visible right now?" in O(log n) instead of O(n).
On every pan or zoom, the renderer needs to know which nodes lie inside the current viewport. Without a spatial index, this requires checking every node — O(n) per frame, which collapses to single-digit frame rates above a few thousand nodes. A spatial index (commonly a quadtree) divides the canvas into recursive quadrants so the renderer can prune entire branches in one comparison.
The result is O(log n) visibility queries, which combined with LOD culling keeps frame times under 16ms (60fps) even as the graph grows. TopoKit maintains its quadtree incrementally: nodes added, removed, or moved during layout update only the affected branches.
See also
References
Browse the full glossary or jump to the docs.