Java based demonstration of spatial indexes

Usage (Parameters for this applet):

The applet handles the parameters:
  • 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 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).