quadtree_example.C File Reference

QuadTree: Spatial Data Structure for 2D Points. More...

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <random>
#include <chrono>
#include <quadtree.H>
#include <tclap/CmdLine.h>

Include dependency graph for quadtree_example.C:

Go to the source code of this file.

Functions
ostream &	operator<< (ostream &os, const Point &p)
	Print a point.
void	demo_basic_operations ()
	Demonstrate basic QuadTree operations.
void	demo_tree_structure ()
	Demonstrate tree structure.
void	demo_geographic_points ()
	Practical example: Geographic Points.
void	demo_collision_detection ()
	Practical example: Game Collision Detection.
void	demo_performance (int n)
	Performance demonstration.
void	demo_traversal ()
	Demonstrate node traversal.
int	main (int argc, char *argv[])

Detailed Description

QuadTree: Spatial Data Structure for 2D Points.

This example demonstrates the QuadTree, a hierarchical spatial data structure that recursively divides 2D space into four quadrants. QuadTrees are essential for efficient spatial queries and are widely used in computer graphics, GIS, game development, and computational geometry.

What is a QuadTree?

A QuadTree is a tree data structure where:

• Root: Represents entire 2D space (bounding box)
• Internal nodes: Have exactly 4 children (quadrants)
• Leaf nodes: Contain points or are empty
• Subdivision: Space is recursively divided into 4 equal quadrants

Structure

Each internal node divides space into four quadrants:

• NW (Northwest): Top-left quadrant
• NE (Northeast): Top-right quadrant
• SW (Southwest): Bottom-left quadrant
• SE (Southeast): Bottom-right quadrant

Example: Dividing a 100×100 space:

Root (0,0 to 100,100)
├── NW (0,0 to 50,50)
├── NE (50,0 to 100,50)
├── SW (0,50 to 50,100)
└── SE (50,50 to 100,100)

How It Works

Insertion

1. Start at root
2. Determine which quadrant point belongs to
3. If quadrant is empty, insert point there
4. If quadrant has points and exceeds capacity, subdivide
5. Recursively insert into appropriate sub-quadrant

Search

1. Start at root
2. Determine which quadrant(s) intersect query region
3. Recursively search relevant quadrants
4. Return all points in query region

Range Query

• Query: "Find all points in rectangle [x1,y1] to [x2,y2]"
• Efficiently prunes irrelevant quadrants
• Only searches quadrants that intersect query region

Complexity Analysis

Operation	Average	Worst Case	Notes
Insert	O(log n)	O(depth)	Depends on distribution
Search (point)	O(log n)	O(depth)	Point lookup
Range query	O(log n + k)	O(n)	k = points in range
Leaf neighbors (QuadNode)	O(log n)	O(depth)	Neighbor navigation between leaf regions
Remove	O(log n)	O(depth)	May require merging

Note: Worst case occurs when points are poorly distributed (e.g., all on a line), causing deep trees.

Applications

Geographic Information Systems (GIS)

• Spatial indexing: Efficiently store and query geographic data
• Map rendering: Quickly find features in viewport
• Location services: Find nearby points of interest
• Spatial joins: Efficiently join spatial datasets

Game Development

• Collision detection: Quickly find objects in collision range
• Visibility culling: Determine what's visible in viewport
• Spatial partitioning: Organize game world efficiently
• AI pathfinding: Spatial awareness for NPCs

Computer Graphics

• Image compression: Quadtree-based image representation
• Ray tracing: Accelerate ray-object intersection tests
• Level of detail (LOD): Adaptive detail based on distance
• Terrain rendering: Efficient terrain data structures

Computational Geometry

• Nearest neighbor: Find closest point efficiently
• Range searches: Find points in rectangular region
• Spatial clustering: Group nearby points
• Voronoi diagrams: Spatial partitioning

Scientific Simulations

• N-body simulations: Barnes-Hut algorithm uses quadtree
• Particle systems: Efficient neighbor finding
• Fluid dynamics: Spatial organization of particles
• Molecular dynamics: Efficient force calculations

Advantages

✅ Efficient queries: O(log n) average case ✅ Adaptive: Automatically adjusts to data distribution ✅ Memory efficient: Only subdivides where needed ✅ Simple concept: Easy to understand and implement

Disadvantages

❌ Worst case: Can degrade to O(n) with bad distribution ❌ 2D only: Designed for 2D space (use octree for 3D) ❌ Rebalancing: May need periodic rebalancing

Comparison with Other Spatial Structures

Structure	Dimensions	Best For	Complexity
QuadTree	2D	Uniform/adaptive	O(log n) avg
Octree	3D	3D spatial data	O(log n) avg
KD-Tree	k-D	High-dimensional	O(log n) avg
R-Tree	k-D	Rectangles	O(log n) avg
Grid	2D	Uniform distribution	O(1)

Usage Example

QuadTree qt(0, 100, 0, 100, 4);
 
qt.insert(Point(10, 20));
qt.insert(Point(30, 40));
 
if (Point *p = qt.search(Point(10, 20)))
  std::cout << "Found: " << *p << "\n";
 
qt.remove(Point(10, 20));
 
// Traverse all nodes (inspect leaf nodes and their stored points)
qt.for_each([](QuadNode *node) {
  if (node->is_leaf())
    std::cout << "Leaf with " << node->get_points_set().size() << " points\n";
});

See also

quadtree.H QuadTree implementation

quadnode.H QuadTree node structure

geom_example.C Other geometric algorithms

Author

Leandro Rabindranath León

Definition in file quadtree_example.C.

Function Documentation

demo_basic_operations()

void demo_basic_operations

(

)

Demonstrate basic QuadTree operations.

Definition at line 204 of file quadtree_example.C.

References QuadTree::contains(), QuadTree::insert(), Aleph::maps(), QuadTree::remove(), and QuadTree::search().

Referenced by main().

demo_collision_detection()

void demo_collision_detection

(

)

Practical example: Game Collision Detection.

Definition at line 353 of file quadtree_example.C.

References QuadTree::contains(), QuadTree::insert(), Aleph::maps(), and Aleph::HTList::size().

Referenced by main().

demo_geographic_points()

void demo_geographic_points

(

)

Practical example: Geographic Points.

Definition at line 302 of file quadtree_example.C.

References QuadTree::contains(), QuadTree::insert(), Aleph::maps(), QuadTree::search(), Aleph::HTList::size(), and y.

Referenced by main().

demo_performance()

void demo_performance

(

int

n

)

Performance demonstration.

Definition at line 406 of file quadtree_example.C.

References QuadTree::contains(), QuadTree::insert(), log2(), and Aleph::maps().

demo_traversal()

void demo_traversal

(

)

Demonstrate node traversal.

Definition at line 460 of file quadtree_example.C.

References QuadTree::for_each(), QuadNode::get_points_set(), QuadTree::insert(), QuadNode::is_leaf(), LEVEL, Aleph::maps(), and Aleph::HTList::size().

Referenced by main().

demo_tree_structure()

void demo_tree_structure

(

)

Demonstrate tree structure.

Definition at line 259 of file quadtree_example.C.

References QuadTree::insert(), and Aleph::maps().

Referenced by main().

main()

int main	(	int	argc,
		char *	argv[]
	)

Definition at line 507 of file quadtree_example.C.

References demo_basic_operations(), demo_collision_detection(), demo_geographic_points(), demo_performance(), demo_traversal(), demo_tree_structure(), and Aleph::maps().

operator<<()

ostream & operator<<	(	ostream &	os,
		const Point &	p
	)

Print a point.

Definition at line 196 of file quadtree_example.C.

References Point::get_x(), Point::get_y(), and Aleph::maps().