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
You may use the appletviewer,
a tool included in Java SE Development Kit 8 (JDK 8), to view the
- First, download and install JDK 8. The versions including the appletviewer are available here.
Choose the correct version for your operating system, and you may
need to create an Oracle account first (it is free). E.g., jdk-8u221-windows-i586.exe for Windows 10 system.
- Change environment variables for convenience. If not done so, you may need to locate the appletviewer manually when executing it.
- Appletviewer can be found in the Java bin folder, e.g., C:\Program Files (x86)\Java\jdk1.8.0_221\bin\appletviewer.exe
- Afterwards, you are able to run appletviewer to visit the web sites containing applets.
Use the following command to execute the viewer: appletviewer [options] [url] where options could be omitted.
For example, if you are to watch the demo of rectangle quadtrees, use appletviewer http://donar.umiacs.umd.edu/quadtree/rectangles/recttree.html
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.