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 3100.
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 310.
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 Kd Tree (Orenstein, 1982)
The PR Kd 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).
KD Tree (Bentley, 1975)
The KD 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).
