R-Tree_Spatial_Search

R Tree implementation for spatial search in n dimensional space

MA2233 DSA LAB Project

R-Trees in Spatial Search

R-Trees are tree data structures user for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectanges or polygons. When the information is of spatial nature, then to obtain the nearest neighbours of given queries, an R-Tree is typically used.

Typically different sets of points are bounded by hyper-rectangles. Given a query point q, only those bounding boxes that intersect with the bounding box containing the query point q are search to find the nearest neighbour of q.

The following is required

• Create 2000 points from [-10, 10]²⁰ ,i.e., the points come from a 20-dimensional space with the max values along any dimension lying between -10 and 10.
• Construct an R-tree of different depths and given and arbitrary query point find its nearest neighbour by searching through the R-tree.
• Investigate for which type of distance functions, viz., Euclidean, Manhattan or the L1 distance, is the returned nearest neighbour actually the nearest neighbour of the given query point q.

Parts of the problem

Insertion - Splitting

• Guttman's
  • Linear
  • Quadratic
  • Exponential
• Greene's

Querying

• Greedy
• Priority Queue

Higher Dimensionality

Use Cases

1. Spatial Indexing in Maps & GIS

   R-trees are the backbone of many geographic information systems.

   Examples

   • Finding all buildings within a region

   • Querying roads that intersect a selected area

   • Finding nearest hospitals, restaurants, ATMs

   • GPS map tile indexing

   • GIS software like PostGIS, ArcGIS, and QGIS use R-trees internally.

2. Collision Detection in 2D/3D Games

   R-trees are great when you have many moving objects with bounding boxes.

   Used for:

   • Broad-phase collision detection (fast elimination of far-apart objects)

   • Spatial partitioning in large worlds

   • Line-of-sight / ray intersection queries

   • Managing bullets, NPCs, physics bodies, etc.

   R-tree is especially useful when:

   • Objects vary in size

   • Objects move around

   • The world is not grid-aligned

   Unlike quadtrees, R-trees avoid “deep skinny” trees when objects cluster.

3. CAD, Modeling, & Rendering

   CAD software relies heavily on R-trees to index geometry.

   Examples:

   • Picking/selecting shapes

   • Intersection checks between geometric solids

   • Quickly finding visible objects in a viewport

   • Identifying nearby surfaces for snapping tools

4. Spatial Databases

   R-trees are built into SQLite, MySQL, PostgreSQL (PostGIS) as spatial indexes.

   Use cases:

   • Spatial joins

   • Nearest-neighbor search

   • Geo-fencing

5. Real-time Tracking & Sensor Systems

   R-trees efficiently maintain spatial relationships among many moving objects.

   Examples:

   • Vehicle tracking (cars, drones, ships)

   • Air traffic control

   • IoT sensors spread across an area

   • Real-time asset monitoring in large warehouses

6. Pathfinding & Robotics

   In robotics you need to check obstacles efficiently.

   Uses:

   • Storing obstacle bounding boxes

   • Querying nearby hazards

   • Checking if a planned path intersects obstacles

   • Collision avoidance