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

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

Type Parameters:

T - a positionable

Direct Known Subclasses:

QTModelScene

public class QTree<T>
extends SpatialIndex<T>

The QTree is a quadtree based organization of a scene containing PositionableModels.

Version:

$Revision: 19885 $, $Date: 2009-10-01 12:39:24 +0200 (Do, 01 Okt 2009) $

Author:

Rutger Bezema, last edited by: $Author: rbezema $

Nested Class Summary

protected class

QTree.Entry<T> The Entry class wraps an object with its envelope

Field Summary

protected QTree<T>[]	children the children of this node
protected byte	currentDepth the current depth of this node
protected float[]	envelope the envelope of this tree
protected ArrayList<QTree.Entry<T>>	leafObjects Objects partially (or totally) contained in this node (if this node is a leaf).
protected static byte	LOWER_LEFT denoting lower left son
protected static byte	LOWER_RIGHT denoting lower right son
protected int	numberOfObjects the number of object this tree can hold in a leaf
protected List<QTree.Entry<T>>	objectsCoveringEnv The objects which totally cover this qtree node
protected static byte	UP_LEFT denoting upper left son
protected static byte	UP_RIGHT denoting upper right son

Constructor Summary

	QTree(Envelope validDomain, int numberOfObjects)
protected	QTree(int numberOfObjects, float[] envelope, byte depth) Create son node.

Method Summary

protected float[]	bboxForSon(int son)
void	clear() Removes all objects from this spatial index.
protected QTree<T>	createNode(int son)
float[]	getEnvelope()
protected float	getHalfHeight()
protected float	getHalfWidth()
int	getMaxOffset()
protected List<QTree<T>>	getObjectNodes(float[] entryEnv)
List<T>	getObjects()
protected List<T>	getObjects(float[] envelope) Convenience method to retrieve the objects intersecting with the given envelope.
protected boolean	hasCoveringObjects()
boolean	insert(Envelope envelope, T object) Add the given object to the spatial index using the given boundingbox
protected boolean	insert(float[] envelope, T object)
void	insertBulk(List<Pair<Envelope,T>> listOfObjects) Create the spatial index from the given list of envelope, objects tuples.
protected boolean	isLeaf()
void	outputAsDot(Writer out, String id, int level, int sonID)
List<T>	query(Envelope 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.
String	toString()

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

createEnvelope, intersects

Methods inherited from class java.lang.Object

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

Field Detail

envelope

protected final float[] envelope

the envelope of this tree

children

protected QTree<T>[] children

the children of this node

leafObjects

protected ArrayList<QTree.Entry<T>> leafObjects

Objects partially (or totally) contained in this node (if this node is a leaf).

objectsCoveringEnv

protected List<QTree.Entry<T>> objectsCoveringEnv

The objects which totally cover this qtree node

numberOfObjects

protected final int numberOfObjects

the number of object this tree can hold in a leaf

currentDepth

protected final byte currentDepth

the current depth of this node

LOWER_LEFT

protected static final byte LOWER_LEFT

denoting lower left son

See Also:

Constant Field Values

LOWER_RIGHT

protected static final byte LOWER_RIGHT

denoting lower right son

See Also:

Constant Field Values

UP_LEFT

protected static final byte UP_LEFT

denoting upper left son

See Also:

Constant Field Values

UP_RIGHT

protected static final byte UP_RIGHT

denoting upper right son

See Also:

Constant Field Values

Constructor Detail

QTree

protected QTree(int numberOfObjects,
                float[] envelope,
                byte depth)

Create son node.

Parameters:

numberOfObjects -

envelope -

depth -

QTree

public QTree(Envelope validDomain,
             int numberOfObjects)

Parameters:

validDomain -

numberOfObjects - each node will contain

Method Detail

getEnvelope

public final float[] getEnvelope()

Returns:

the envelope

getMaxOffset

public final int getMaxOffset()

Returns:

the maxOffset

getHalfWidth

protected final float getHalfWidth()

Returns:

the half of the width added to min x

getHalfHeight

protected final float getHalfHeight()

Returns:

the half of the height added to the min y

insert

public boolean insert(Envelope envelope,
                      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:

envelope - of the object

object - to insert

Returns:

true if the object was inserted, false otherwise.

insert

protected boolean insert(float[] envelope,
                         T object)

Parameters:

envelope - of the object

object - to insert

Returns:

true if the object was inserted, false otherwise.

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 remove

Returns:

true if the object was inserted, false otherwise.

toString

public String toString()

Overrides:

toString in class Object

getObjectNodes

protected final List<QTree<T>> getObjectNodes(float[] entryEnv)

Parameters:

entryEnv -

Returns:

the nodes the given envelope will intersect.

isLeaf

protected final boolean isLeaf()

Returns:

true if this is a leaf node

createNode

protected QTree<T> createNode(int son)

Parameters:

son - one of LOWER_LEFT,LOWER_RIGHT,UP_LEFT,UP_RIGHT

Returns:

a new QTree created from the given index.

bboxForSon

protected final float[] bboxForSon(int son)

Parameters:

son - one of LOWER_LEFT,LOWER_RIGHT,UP_LEFT,UP_RIGHT

Returns:

the new envelope for the given son.

hasCoveringObjects

protected final boolean hasCoveringObjects()

Returns:

true if this node has objects fitting the total region of space.

query

public List<T> query(Envelope 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 - to get the leafObjects for.

Returns:

the leafObjects which intersect with this node and or it's children, or the empty list.

getObjects

protected List<T> getObjects(float[] envelope)

Convenience method to retrieve the objects intersecting with the given envelope.

Parameters:

envelope -

Returns:

a List with all objects intersecting with the given envelope.

getObjects

public List<T> getObjects()

Returns:

the leafObjects which intersect with this node and or it's children, or the empty list.

clear

public void clear()

Description copied from class: SpatialIndex

Removes all objects from this spatial index.

Specified by:

clear in class SpatialIndex<T>

outputAsDot

public void outputAsDot(Writer out,
                        String id,
                        int level,
                        int sonID)
                 throws IOException

Parameters:

out -

id -

level -

sonID -

Throws:

IOException

insertBulk

public void insertBulk(List<Pair<Envelope,T>> listOfObjects)

Description copied from class: SpatialIndex

Create the spatial index from the given list of envelope, objects tuples.

Specified by:

insertBulk in class SpatialIndex<T>

Parameters:

listOfObjects - to be inserted into the spatial index.