Skip to main content
Definition Website Computer and Technology

Quadtree

Subject: Computer and Technology noun /ˈkwɑːdˌtriː/ 1 definition

  1. Definition (noun)

    Entry #278 · Updated

    A Quadtree is a hierarchical tree data structure in which each internal node partitions a two-dimensional region into four child quadrants, recursively subdividing space until leaf criteria are met. Starting from a root bounding box, insertion splits a quadrant into northwest, northeast, southwest, and southeast sub-quadrants whenever the elements inside exceed a capacity threshold or fail a uniformity test, while sparse areas remain unsplit. During spatial operations—such as range queries, nearest-neighbor lookups, or collision detection—traversal skips entire subtrees whose bounding boxes fall outside the target area, avoiding linear scans over unrelated objects. Because resolution adapts dynamically to local density, quadtrees balance memory efficiency against fast spatial pruning, though they are inherently confined to two dimensions (unlike 3D octrees) and require depth bounds to handle tightly clustered or coincident coordinates.

    Common Types

    • Region Quadtree: Recursively divides a uniform 2D grid or raster image into equal-sized quadrants until every leaf block holds a homogeneous value (such as one pixel color or occupancy state), enabling compact representation of sparse grids and binary masks.

    • Point Quadtree: Uses each inserted 2D point as a splitting pivot that divides space around that point's coordinates into four variable-sized quadrants, making tree balance and query performance dependent on insertion order.

    • Point-Region (PR) Quadtree: Splits each quadrant strictly at its geometric center regardless of point positions, storing coordinates only in leaf buckets that subdivide whenever their element count exceeds a fixed capacity threshold.

    • Polygonal Map (PM) Quadtree: Extends quadtree subdivision to store vector line segments and polygon edges rather than isolated points, splitting cells until each leaf contains only a bounded set of edges or shared vertices.

    Example

    A 2D multiplayer game server simulates a 4096 × 4096 unit arena containing 12,000 projectiles and player hitboxes using a PR quadtree configured with a leaf capacity of 8 entities and a maximum depth of 10. During each 16.6 ms server tick, querying a player's 64 × 64 bounding box traverses only the intersecting quadrants and tests 11 candidate entities instead of checking all 12,000 objects.