org.deegree.commons.index
Class RTree<T>

java.lang.Object
  org.deegree.commons.index.SpatialIndex<T>
      org.deegree.commons.index.RTree<T>

Type Parameters:

T - of objects the tree will hold.

public class RTree<T>
extends SpatialIndex<T>

RTree NB: When creating node entry arrays i.e. new RTree.NodeEntry[bigM + 1], be sure to always use dimension bigM + 1, as this length is expected (otherwise NullPointerExceptions will pop up).

The bulk insertion mechanism is an implementation of STRTree: Scott T. Leutenegger, Jeffrey M. Edgington, Mario A. Lopez: STR: A SIMPLE AND EFFICIENT ALGORITHM FOR R-TREE PACKING (1997)

The insert method (more precisely chooseSubtree and split) have been implemented after the paper: Norbert Beckmann, Bernhard Seeger: A Revised R*-tree in Comparison with Related Index Structures (2009)

Version:

$Revision: 31506 $, $Date: 2011-08-16 12:40:55 +0200 (Tue, 16 Aug 2011) $

Author:

Andreas Schmitz, Andrei Ionita, last edited by: $Author: aschmitz $

Field Summary

protected org.deegree.commons.index.RTree.NodeEntry<T>[]

root

Constructor Summary

RTree(float[] rootEnvelope, int numberOfObjects)

Method Summary

void	clear() Removes all objects from this spatial index.
boolean	getExtraFlag()
boolean	insert(float[] insertBox, T object) Add the given object to the spatial index using the given boundingbox
void	insertBulk(List<Pair<float[],T>> listOfObjects) Builds the index from the given objects with their envelope.
static <T> RTree<T>	loadFromDisk(String storagePath)
LinkedList<T>	query(float[] env) Query the spatial index with the given envelope and return all objects which intersect with the given boundingbox.
boolean	remove(T object) Removes the given object from this spatial index, using the objects' equals method.
void	writeTreeToDisk(String storagePath) Persist the r-tree to the given location.

Methods inherited from class org.deegree.commons.index.SpatialIndex

intersects

Methods inherited from class java.lang.Object

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

Field Detail

root

protected org.deegree.commons.index.RTree.NodeEntry<T>[] root

Constructor Detail

RTree

public RTree(float[] rootEnvelope,
             int numberOfObjects)

Parameters:

rootEnvelope - of this rtree.

numberOfObjects - each rectangle shall hold before splitting.

Method Detail

loadFromDisk

public static <T> RTree<T> loadFromDisk(String storagePath)
                             throws IOException

Type Parameters:

T -

Parameters:

storagePath - absolute path to the file

Returns:

a new instance

Throws:

IOException

query

public LinkedList<T> query(float[] env)

Description copied from class: SpatialIndex

Query the spatial index with the given envelope and return all objects which intersect with the given boundingbox.

Specified by:

query in class SpatialIndex<T>

Parameters:

env -

Returns:

a list of objects intersecting the given boundingbox.

insertBulk

public void insertBulk(List<Pair<float[],T>> listOfObjects)

Builds the index from the given objects with their envelope.

Specified by:

insertBulk in class SpatialIndex<T>

Parameters:

listOfObjects -

clear

public void clear()

Description copied from class: SpatialIndex

Removes all objects from this spatial index.

Specified by:

clear in class SpatialIndex<T>

remove

public boolean remove(T object)

Description copied from class: SpatialIndex

Removes the given object from this spatial index, using the objects' equals method.

Specified by:

remove in class SpatialIndex<T>

Parameters:

object - to be removed

Returns:

true if the removal was successful, false otherwise

getExtraFlag

public boolean getExtraFlag()

Returns:

extra flag read from a file (used for hacking around buggy shp files)

insert

public boolean insert(float[] insertBox,
                      T object)

Description copied from class: SpatialIndex

Add the given object to the spatial index using the given boundingbox

Specified by:

insert in class SpatialIndex<T>

Parameters:

insertBox - of the object

object - to insert

Returns:

true if the object could be inserted.

writeTreeToDisk

public void writeTreeToDisk(String storagePath)

Persist the r-tree to the given location.

Parameters:

storagePath -