com.infomatiq.jsi.rtree
Class RTree

java.lang.Object
  |
  +--com.infomatiq.jsi.rtree.RTree

All Implemented Interfaces:

SpatialIndex

public class RTree

extends java.lang.Object

implements SpatialIndex

This is a lightweight RTree implementation, specifically designed for the following features (in order of importance):

• Fast intersection query performance. To achieve this, the RTree uses only main memory to store entries. Obviously this will only improve performance if there is enough physical memory to avoid paging.
• Low memory requirements.
• Fast add performance.

The main reason for the high speed of this RTree implementation is the avoidance of the creation of unnecessary objects, mainly achieved by using primitive collections from the trove4j library.

Version:

1.0b1

Author:

aled.morris@infomatiq.co.uk

Constructor Summary

RTree()
Constructor.

Method Summary

void	add(Rectangle r, int id) Adds a new rectangle to the spatial index
void	contains(Rectangle r, IntProcedure v) Finds all rectangles contained by the passed rectangle.
boolean	delete(Rectangle r, int id) Deletes a rectangle from the spatial index
java.lang.String	getVersion() Returns a string identifying the type of spatial index, and the version number, eg "SimpleIndex-1.0b1"
void	init(java.util.Properties props) Initialize implementation dependent properties of the RTree.
void	intersects(Rectangle r, IntProcedure v) Finds all rectangles that intersect the passed rectangle.
void	nearest(Point p, IntProcedure v, float furthestDistance) Finds all rectangles that are nearest to the passed rectangle, and calls execute() on the passed IntProcedure for each one.
int	size() Returns the number of entries in the spatial index

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

RTree

public RTree()

Constructor. Use init() method to initialize parameters of the RTree.

Method Detail

init

public void init(java.util.Properties props)

Initialize implementation dependent properties of the RTree. Currently implemented properties are:

• MaxNodeEntries
This specifies the maximum number of entries in a node. The default value is 10, which is used if the property is not specified, or is less than 2.
• MinNodeEntries
This specifies the minimum number of entries in a node. The default value is half of the MaxNodeEntries value (rounded down), which is used if the property is not specified or is less than 1.

Specified by:

init in interface SpatialIndex

Parameters:

props - The set of properties used to initialize the spatial index.

See Also:

SpatialIndex.init(Properties)

add

public void add(Rectangle r,
                int id)

Description copied from interface: SpatialIndex

Adds a new rectangle to the spatial index

Specified by:

add in interface SpatialIndex

Parameters:

r - The rectangle to add to the spatial index.

id - The ID of the rectangle to add to the spatial index. The result of adding more than one rectangle with the same ID is undefined.

See Also:

SpatialIndex.add(Rectangle, int)

delete

public boolean delete(Rectangle r,
                      int id)

Description copied from interface: SpatialIndex

Deletes a rectangle from the spatial index

Specified by:

delete in interface SpatialIndex

Parameters:

r - The rectangle to delete from the spatial index

id - The ID of the rectangle to delete from the spatial index

Returns:

true if the rectangle was deleted false if the rectangle was not found, or the rectangle was found but with a different ID

See Also:

SpatialIndex.delete(Rectangle, int)

nearest

public void nearest(Point p,
                    IntProcedure v,
                    float furthestDistance)

Description copied from interface: SpatialIndex

Finds all rectangles that are nearest to the passed rectangle, and calls execute() on the passed IntProcedure for each one.

Specified by:

nearest in interface SpatialIndex

Parameters:

p - The point for which this method finds the nearest neighbours.

furthestDistance - The furthest distance away from the rectangle to search. Rectangles further than this will not be found. This should be as small as possible to minimise the search time. Use Float.POSITIVE_INFINITY to guarantee that the nearest rectangle is found, no matter how far away, although this will slow down the algorithm.

See Also:

SpatialIndex.nearest(Point, IntProcedure, float)

intersects

public void intersects(Rectangle r,
                       IntProcedure v)

Description copied from interface: SpatialIndex

Finds all rectangles that intersect the passed rectangle.

Specified by:

intersects in interface SpatialIndex

Parameters:

r - The rectangle for which this method finds intersecting rectangles.

v - The IntProcedure whose execute() method is is called for each intersecting rectangle.

See Also:

SpatialIndex.intersects(Rectangle, IntProcedure)

contains

public void contains(Rectangle r,
                     IntProcedure v)

Description copied from interface: SpatialIndex

Finds all rectangles contained by the passed rectangle.

Specified by:

contains in interface SpatialIndex

Parameters:

r - The rectangle for which this method finds contained rectangles.

See Also:

SpatialIndex.contains(Rectangle, IntProcedure)

size

public int size()

Description copied from interface: SpatialIndex

Returns the number of entries in the spatial index

Specified by:

size in interface SpatialIndex

See Also:

SpatialIndex.size()

getVersion

public java.lang.String getVersion()

Description copied from interface: SpatialIndex

Returns a string identifying the type of spatial index, and the version number, eg "SimpleIndex-1.0b1"

Specified by:

getVersion in interface SpatialIndex

See Also:

SpatialIndex.getVersion()