Spatial Index Demos

These applets are based on algorithms published in the following books:

Click here for the table of contents and a 20% discount coupon

• H. Samet, The Design and Analysis of Spatial Data Structures, Addison-Wesley, 1990
• H. Samet, Applications of Spatial Data Structures, Addison-Wesley, 1990
• H. Samet, Foundations of Multidimensional and Metric Data Structures, Morgan-Kaufmann, 2006

A short course on some of the algorithms and data structures used in these applets was held at UC Berkeley on March 29-31, 1999.

If you are interested in these spatial index demos, check out our spatial data browser and spatial database engine: SAND Internet Browser

Recent Feature Updates

Window and Range search were replaced by the more general Overlap Search feature.

Within Query and various query object types (e.g., polygon, sector) were added to support richer nearest neighbor searches.

Spatial Datastructures Visualization

Instructions and further information about the visualization tool can be found below.

Points

• Point Quadtree Demo
• K-d Tree Demo
• MX Quadtree Demo
• PR Quadtree Demo
• Bucket PR Quadtree Demo
• PR K-d Tree Demo
• Bucket PR K-d Tree Demo
• PMR Quadtree Demo
• PMR k-d Demo
• 2D Range Tree Demo (old version here)
• Priority Search Tree Demo (old version here)
• R-Tree Demo
• PK Tree Demo
• Voronoi Diagram Demo
• Delaunay Triangulation Demo

Rectangles

• MX-CIF Quadtree Demo
• Rectangle Quadtree Demo
• Bucket Rectangle Quadtree Demo
• PMR Rectangle Quadtree Demo
• PMR Rectangle k-d Tree Demo
• R-tree Demo (old version here)
• Loose Quadtree Demo

Lines

• PM1 Quadtree Demo
• PM2 Quadtree Demo
• PM3 Quadtree Demo
• PMR Quadtree Demo
• Bucket PM Quadtree Demo
• R-Tree Demo

Region Quadtrees

• Region Quadtree Demo

Operations

• Insert Operation
• Move Operation - Click and drag the object nearest to the mouse cursor. The data structure changes dynamically as the object is being moved.
• Delete Operation
• Overlap Search Query
• Window Query
• Nearest Neighbor Query
• Within Query - Works like nearest neighbor but stops when objects are farther than the given distance.

Other Features

• Grid - Shows alignment of quadtree blocks with a regular grid. Press + or - to adjust resolution.
• Zoom In/Zoom Out - Explore areas in more detail or zoom out for an overview.
• Zoom Window - Magnifies a selected area in a separate window for detailed inspection.