com.infomatiq.jsi.rtree
Class RTree

java.lang.Object
  extended by com.infomatiq.jsi.rtree.RTree
All Implemented Interfaces:
SpatialIndex

public class RTree
extends Object
implements SpatialIndex

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

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.


Constructor Summary
RTree()
          Constructor.
 
Method Summary
 void add(Rectangle r, int id)
          Adds a new rectangle to the spatial index
 boolean checkConsistency()
          Check the consistency of the tree.
 void contains(Rectangle r, gnu.trove.TIntProcedure v)
          Finds all rectangles contained by the passed rectangle.
 boolean delete(Rectangle r, int id)
          Deletes a rectangle from the spatial index
 Rectangle getBounds()
          Returns the bounds of all the entries in the spatial index, or null if there are no entries.
 int getHighestUsedNodeId()
          Get the highest used node ID
 Node getNode(int id)
          Get a node object, given the ID of the node.
 int getRootNodeId()
          Get the root node ID
 String getVersion()
          Returns a string identifying the type of spatial index, and the version number, eg "SimpleIndex-0.1"
 void init(Properties props)
          Initialize implementation dependent properties of the RTree.
 void intersects(Rectangle r, gnu.trove.TIntProcedure v)
          Finds all rectangles that intersect the passed rectangle.
 void nearest(Point p, gnu.trove.TIntProcedure v, float furthestDistance)
          Finds the nearest rectangles to the passed rectangle and calls v.execute(id) for each one.
 void nearestN_orig(Point p, gnu.trove.TIntProcedure v, int count, float furthestDistance)
          Deprecated. Use new NearestN or NearestNUnsorted instead. This implementation of nearestN is only suitable for small values of N (ie less than 10).
 void nearestN(Point p, gnu.trove.TIntProcedure v, int count, float furthestDistance)
          Finds the N nearest rectangles to the passed rectangle, and calls execute(id, distance) on each one, in order of increasing distance.
 void nearestNUnsorted(Point p, gnu.trove.TIntProcedure v, int count, float furthestDistance)
          Same as nearestN, except the found rectangles are not returned in sorted order.
 int size()
          Returns the number of entries in the spatial index
 
Methods inherited from class java.lang.Object
clone, equals, finalize, 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(Properties props)

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

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,
                    gnu.trove.TIntProcedure v,
                    float furthestDistance)
Description copied from interface: SpatialIndex
Finds the nearest rectangles to the passed rectangle and calls v.execute(id) for each one. If multiple rectangles are equally near, they will all be returned.

Specified by:
nearest in interface SpatialIndex
Parameters:
p - The point for which this method finds the nearest neighbours.
v - The IntProcedure whose execute() method is is called for each nearest neighbour.
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, TIntProcedure, float)

nearestNUnsorted

public void nearestNUnsorted(Point p,
                             gnu.trove.TIntProcedure v,
                             int count,
                             float furthestDistance)
Description copied from interface: SpatialIndex
Same as nearestN, except the found rectangles are not returned in sorted order. This will be faster, if sorting is not required

Specified by:
nearestNUnsorted in interface SpatialIndex
See Also:
SpatialIndex.nearestNUnsorted(Point, TIntProcedure, int, float)

nearestN

public void nearestN(Point p,
                     gnu.trove.TIntProcedure v,
                     int count,
                     float furthestDistance)
Description copied from interface: SpatialIndex
Finds the N nearest rectangles to the passed rectangle, and calls execute(id, distance) on each one, in order of increasing distance. Note that fewer than N rectangles may be found if fewer entries exist within the specified furthest distance, or more if rectangles N and N+1 have equal distances.

Specified by:
nearestN in interface SpatialIndex
Parameters:
p - The point for which this method finds the nearest neighbours.
v - The IntfloatProcedure whose execute() method is is called for each nearest neighbour.
count - The desired number of rectangles to find (but note that fewer or more may be returned)
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.nearestN(Point, TIntProcedure, int, float)

nearestN_orig

public void nearestN_orig(Point p,
                          gnu.trove.TIntProcedure v,
                          int count,
                          float furthestDistance)
Deprecated. Use new NearestN or NearestNUnsorted instead. This implementation of nearestN is only suitable for small values of N (ie less than 10).

See Also:
SpatialIndex.nearestN(Point, TIntProcedure, int, float)

intersects

public void intersects(Rectangle r,
                       gnu.trove.TIntProcedure 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, TIntProcedure)

contains

public void contains(Rectangle r,
                     gnu.trove.TIntProcedure 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.
v - The procedure whose visit() method is is called for each contained rectangle.
See Also:
SpatialIndex.contains(Rectangle, TIntProcedure)

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()

getBounds

public Rectangle getBounds()
Description copied from interface: SpatialIndex
Returns the bounds of all the entries in the spatial index, or null if there are no entries.

Specified by:
getBounds in interface SpatialIndex
See Also:
SpatialIndex.getBounds()

getVersion

public String getVersion()
Description copied from interface: SpatialIndex
Returns a string identifying the type of spatial index, and the version number, eg "SimpleIndex-0.1"

Specified by:
getVersion in interface SpatialIndex
See Also:
SpatialIndex.getVersion()

getNode

public Node getNode(int id)
Get a node object, given the ID of the node.


getHighestUsedNodeId

public int getHighestUsedNodeId()
Get the highest used node ID


getRootNodeId

public int getRootNodeId()
Get the root node ID


checkConsistency

public boolean checkConsistency()
Check the consistency of the tree.

Returns:
false if an inconsistency is detected, true otherwise.


Copyright © 2012. All Rights Reserved.