tag

#spatial-index

3 pages tagged

Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

R Tree Search

R Tree Search R tree search is a spatial indexing method for multidimensional objects such as rectangles or bounding boxes. It organizes data into a balanced tree of minimum bounding rectangles (MBRs), enabling efficient spatial queries. It is widely used in databases and geographic information systems. Problem Given a set of spatial rectangles and a query rectangle $Q$, find all rectangles that intersect $Q$: $$ R \cap Q \neq \emptyset...
algorithms searching r-tree spatial-index
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Quadtree Search

Quadtree Search Quadtree search partitions 2D space recursively into four quadrants. Each node represents a rectangular region and stores points or subregions within that area. It is used for spatial indexing, collision detection, and range queries in two dimensions. Problem Given a set of 2D points and a query rectangle $Q$, find all points inside $Q$: $$ x_1 \le x \le x_2, \quad y_1 \le y \le y_2 $$ Structure...
algorithms searching quadtree spatial-index
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Octree Search

Octree Search Octree search extends quadtree ideas to three dimensional space. It recursively partitions space into eight octants, enabling efficient spatial queries over 3D points or volumes. It is commonly used in graphics, physics simulation, and spatial indexing. Problem Given a set of 3D points and a query axis aligned bounding box (AABB), find all points inside the box: $$ x_1 \le x \le x_2,\quad y_1 \le y \le y_2,\quad...
algorithms searching octree spatial-index 3d