tpl_2dtree_example.cc File Reference

Educational examples for 2D spatial trees (k-d trees) More...

#include <iostream>
#include <cmath>
#include <tpl_2dtree.H>
#include <point.H>

Include dependency graph for tpl_2dtree_example.cc:

Go to the source code of this file.

Functions
int	main ()

Detailed Description

Educational examples for 2D spatial trees (k-d trees)

WHAT IS A 2D-TREE?

Binary search tree for 2D points (k-d tree with k=2) Alternates splitting on X and Y coordinates Enables efficient spatial queries in 2D space

HOW IT WORKS:

• Root level: Split on X coordinate
• Next level: Split on Y coordinate
  
• Alternates X/Y splits at each level
• Each node represents a point and implicitly defines a rectangular region

EFFICIENT OPERATIONS:

• Insert: O(log n) average
• Search: O(log n) average
• Range query: O(sqrt(n) + k) where k = results
• Nearest neighbor: O(log n) average

APPLICATIONS:

• Geographic information systems (GIS)
• Computer graphics (collision detection)
• Machine learning (k-NN classification)
• Game development (spatial partitioning)
• Computational geometry

COMPILE & RUN:

g++ -std=c++20 -I.. -o tpl_2dtree_example tpl_2dtree_example.cc -lm ./tpl_2dtree_example

Definition in file tpl_2dtree_example.cc.

Function Documentation

main()

int main

(

)

Definition at line 47 of file tpl_2dtree_example.cc.

References ah_domain_error_if, K2Tree< T >::contains(), Aleph::divide_and_conquer_partition_dp(), Aleph::Point::get_x(), Aleph::Point::get_y(), K2Tree< T >::insert(), K2Tree< T >::nearest(), K2Tree< T >::range(), and y.