Spatial Index Demos

Brought to you by Frantisek Brabec (brabec at cs.umd.edu) and Hanan Samet (hjs at cs.umd.edu).

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, Reading, MA, 1990.
• H. Samet, Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS , Addison-Wesley, Reading, MA, 1990.
•   H. Samet, Foundations of Multidimensional and Metric Data Structures, Morgan-Kaufmann, San Francisco, 2006 (click for brochure and 20% off code)

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, you could be also interested in our most recently developed software - SAND Internet Browser. SAND is a spatial data browser and spatial database engine with Java front-end.

Window and Range search operations were replaced by more general Overlap Search. Overlap Search finds all the objects (e.g., rectangles) in the current data structure that intersect the query object (e.g., a path). The particular type of intersection can be specified by setting the additional conditions.

More query object types for which the nearest neighbor algorithm can be run were added. Now you can rank objects by their distance from point, rectangle, polygon, path, and sector. Also the Within query was added that finds all the objects within a given distance from a query object.

Required software

All the applets on this page use JDK 1.4 features. These are supported by the latest versions of both Mozilla Firefox (1.5 or newer) and MS Internet Explorer (7.0 or newer) browsers. If you cannot upgrade your browser, click here for the older version of the point structures demo, here for the older version of the rectangle structures demo and here for the older version of the line structures demo.

To use the original Sun's implementation of JDK in your browser, you can download and install Javasoft's Java Plug-in.

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 exactly as the Nearest Neighbor Query except it stops execution once the distance of the next nearest object from the query object is larger than the 'within' parameter.

Other Features

• Grid - shows grid that allows the user to investigate alignment of quadtree blocks with a regular grid. Press the + and - buttons to see finer or coarser grid respectively.
• Zoom In/Zoom Out - zooms in and out. Works as zoom in and out in any other application, zooming in allows you to see in more detail areas where objects are too close to each other to investigate fully from the regular view.
• Zoom Window - allows you to see a selected area of the applet in a separate window and potentially on a different zoom level. This can in effect serve as a magnifying glass tool.