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:
- 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)
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
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
Spatial Datastructures Visualization
Instructions and further information about the visualization tool can be found below.
not able to load Java applet
For an explanation of the implemented algorithms as well as their
visualization and animation, click on one of the following links:
- 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.
- 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.