Java based demonstration of spatial indexes

Usage (Parameters for this applet):

• MaxNumOfPoints - Maximum number of nodes. The number of nodes can be between 3-100.
• InitialNumOfPoints - Initial number of nodes. This is the number of nodes that will be displayed when the application start. The scroll bar and the text field will be updated according to this value. This number can be any value between 3 and MaxNumOfPoints.
• Radius - Nodes representation radius. Every node is represented as a filled circle on the applet. The Radius is defined in pixels and its value can be 3-10.

For explanations on the principles behind the applet, read the following text :

• Introduction
• Spatial Indexing - General
• Simple Grid
• Spatial Indexing - Points
• PR K-d Tree
• PR Quadtree
• Point Quadtree
• K-d Tree
• Spatial Indexing - Lines
• Simple Edges Grid
• MX Quadtree
• PMR Quadtree

If you want to find more about the technical details (Source code etc.) - Click Here

Introduction

Spatial indexing is one of the bases of spatial databases. They are commonly used in computerised systems that use a spatial databases - such as CAD systems and Geographic Information Systems (GIS). The current applet demonstrates several data structures for indexing spatial data.
The indexes that are demonstrated are used to handle 1 dimensional objects (points) and 2 dimensional objects (lines).
For a demonstration of line elements, the applet generates two geometrical structure based on the set of points: a minimum spanning tree and convex hull. The user can choose the number of nodes and the line generation method (for the indexes that are based on lines).
It is possible to change the position of any node, by pointing to a node with the mouse, and draging it to a new location. To change the number of nodes, drag the scroll bar on the control panel.
The lines and the nodes are the "spatial database" that is used for the spatial indexes. The applet creates the index as a graphic representation on the display. It is possible to change the position of nodes, or the number of nodes in order to see how the index is changing according to those changes.

Spatial indexing - general

Simple Grid

A grid is a regular decomposition of space. By applying a grid of squares with a regular height and width. Every grid cell is a "bucket" that hold the spatial entities which are located inside its boundaries. The cell holds 0,1 or more entities - this is it's main disadvantage, since it is not efficient way for accessing the data. The grid cell size for this applet is defined as (Radius*3).

Spatial Indexing - Points

PR K-d Tree (Orenstein, 1982)

The PR K-d Tree is a regular decomposition of space. Decomposition occurs whenever a bucket overflows. In the current implementation the bucket size is 4. The decomposition is done by splitting the bucket into 2 equal buckets. The decomposition is done in different directions: the first one horizontally, then vertically and so on.
The maximum level of decomposition depends on the minimum separation between two points, but it is bounds by the minimum cell size (Radius*3).

PR Quadtree (Orenstein)

The PR Quadtree is a regular decomposition of space. Decomposition occurs whenever a bucket overflows. In the current implementation the bucket size is 4. The decomposition is done by splitting the bucket into 4 equal buckets. The PR Quadtree is useful when the domain of data points is finite. The maximum level of decomposition depends on the minimum separation between two points, but it is bounds by the minimum cell size (Radius*3).

Point Quadtree (Finkel/Bentley, 1974)

The point quadtree is a marriage between a uniform grid and a binary search tree. Decomposition occurs whenever a bucket overflows. In the current implementation the bucket size is 4. The decomposition is done by splitting the bucket into 4 buckets along the x and y coordinates of the lowest order point in this bucket (the point that was inserted first to the bucket).

K-D Tree (Bentley, 1975)

The K-D tree is another example for a marriage between a uniform grid and a binary search tree. Decomposition occurs whenever a bucket is overflow. In the current implementation the bucket size is 4. The decomposition is done by splitting the bucket into 2 buckets along the x or y coordinates of the lowest order point in this bucket (the point that was inserted first to the bucket). The decomposition is done in different directions: the first one horizontally, then vertically and so on.

Spatial Indexing - Lines

Simple Edges Grid

A grid is a regular decomposition of space, by applying a grid of squares with a regular height and width. Every grid cell is a "bucket" that hold the spatial entities which are located inside its boundaries. The cell holds 0,1 or more entities - this is its main disadvantage, since it is not efficient way for accessing the data. The grid cell size is defined as (Radius*3).
Every grid cell can be "empty" - no edges are passing through it, or "full" - there is at least one edge that passes through it. In this example, a "full" cell is marked by an "X" sign.

MX Quadtree (Hunter)

The MX Quadtree is a regular decomposition of space. Decomposition occurs whenever a bucket is overflow. On the current implementation the bucket size is 1. The decomposition is done by splitting the bucket into 4 equal buckets. The criteria for overflow is the existence of a segment that crosses the "bucket" boundaries. The edges are represented by "black" pixels. This quadtree is also useful for simple digitised polygons - with no intersecting edges. The maximum level of decomposition depends on the minimum cell size (Radius*3).

PMR Quadtree

The PMR Quadtree is a regular decomposition of space. Decomposition occurs whenever a bucket overflows. In the current implementation the bucket size is 2. The decomposition is done by splitting the bucket into 4 equal buckets. The criteria for overflow is that at least two segments are crossing the "bucket" boundaries. The maximum level of decomposition depends on the minimum cell size (Radius*3).

Links for more information on spatial indexes

This applet is based on outlines and principles that were taught in the course "Geographical Information Systems: A technical approach" (held in winter semester 1995) by Prof. Hanan Samet and Prof. Catriel Beery.

Note about computing: When this applet was written, we wrote " The number of nodes can be between 2-40. The limit is due to the intensive calculation that this applet does. On high numbers (>30) the amount of CPU consumed by it is amazingly high." Within 6 years, it was possible to add a complex algorithm (Convex Hull) and to increase the number of nodes to 100. The original was written for a high-end Sun workstation, the updated version can run on my 333Mhz P-II. Moore's low and all that jazz...

More information is available in Hanan Samet site .

This applet was Written by: Muki Haklay & Sabina Gertz.

The Source code:
SpatialIdx.java
The original (1995) source Tree.java