com.mapinfo.midev.index.rtree

Class RTree

java.lang.Object

com.mapinfo.midev.index.rtree.RTree

public final class RTree
extends Object

Creates r-tree structure. Default node maximum capacity is 10 and default minimum capacity is the maximum capacity divided by 2. Users can define both maximum and minimum capacity, but the minimum capacity can not be greater than the half of maximum capacity, otherwise it is set to the half of maximum. The following sample shows a typical pattern for using an r-tree. The BoundedObject is used here as a decorator for the object we want to store in the r-tree.

public static class BoundedObject<T> {

    private final Envelope m_envelope;
    private final T m_data;

    public BoundedObject(Envelope envelope, T data) {
        m_envelope = envelope;
        m_data = data;
    }

    public Envelope getEnvelope() {
        return m_envelope;
    }

    public T getData() {
        return m_data;
    }
}

The r-tree requires a decorator that knows how to get the bounds of the stored object:

public static class BoundedObjectDecorator<T> implements IEnvelopeDecorator<BoundedObject<T>> {
    public Envelope getEnvelope(BoundedObject<T> o) {
        return o.getEnvelope();
    }
}

The BoundedObject can now be stored in the r-tree:

// create the r-tree with the decorator
IEnvelopeDecorator<BoundedObject<String>> decorator = new BoundedObjectDecorator<>();
RTree<BoundedObject<String>> rTree = new RTree<>(decorator);

// add some objects to the r-tree
SpatialInfo spatialInfo = SpatialInfo.create(CoordSysConstants.longLatWGS84);
rTree.add(new BoundedObject<>(new Envelope(-79.761933, 40.496604,
        -71.856138, 45.012508, spatialInfo), "New York"));
rTree.add(new BoundedObject<>(new Envelope(-109.060278, 36.992442,
        -102.041495, 41.003444, spatialInfo), "Colorado"));
rTree.add(new BoundedObject<>(new Envelope(-109.050191, 31.332216,
        -103.001970, 37.000317, spatialInfo), "New Mexico"));

// retrieve the objects from the r-tree with an envelope search
RTreeCursor<BoundedObject<String>> cursor = rTree.search(
        new RTreeEnvelopeSearch(new Envelope(-104.743840, 34.705783,
                -99.889056, 37.902327, spatialInfo)));
while (cursor.hasNext()) {
    BoundedObject<String> o = cursor.next();
}

Constructor Summary

Constructors

Constructor and Description
RTree(IEnvelopeDecorator decorator) Creates a r-tree structure from the specified envelope decorator which help getting envelope from the user-defined objects stored in the leaf node of r-tree.
RTree(IEnvelopeDecorator decorator, int maxCapacity, int minCapacity) Creates a r-tree structure with specified envelope decorator, maximum capacity and minimum capacity.
RTree(IEnvelopeDecorator decorator, IRTreeHelper helper) Creates a r-tree implementation with the specified decorator and helper.

Method Summary

Modifier and Type	Method and Description
void	add(Object o) Adds a data item into this tree.
void	clear() Clear up this tree.
Envelope	getEnvelope() Gets the entire envelope of this r-tree.
void	remove(Object o) Removes the specified data item from this tree.
RTreeCursor	search(IRTreeEnvelopeSearch rs) Gets a r-tree search curosr based on the specified search criteria.

Methods inherited from class java.lang.Object

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

Constructor Detail

RTree

public RTree(IEnvelopeDecorator decorator)

Creates a r-tree structure from the specified envelope decorator which help getting envelope from the user-defined objects stored in the leaf node of r-tree. The default maximum capacity is 10 and minimum capacity is 5.

Parameters:

decorator - decorator to get envelopes from user-defined objects in leaf node.

RTree

public RTree(IEnvelopeDecorator decorator,
             int maxCapacity,
             int minCapacity)

Creates a r-tree structure with specified envelope decorator, maximum capacity and minimum capacity.

Parameters:

decorator - decorator to get envelopes from user-defined objects in leaf node.

maxCapacity - The maximum capacity of each node in this tree.

minCapacity - The minimum capacity of each node in this tree. Should not be great than maxCapacity/2, otherwise it is set to maxCapacity/2.

RTree

public RTree(IEnvelopeDecorator decorator,
             IRTreeHelper helper)

Creates a r-tree implementation with the specified decorator and helper.

Parameters:

decorator - decorator to get envelopes from user-defined objects in leaf node.

helper - The helper that handles the underlying structure of the r-tree data.

Method Detail

remove

public void remove(Object o)

Removes the specified data item from this tree.

Parameters:

o - the data item will be deleted if can be found in this tree.

add

public void add(Object o)

Adds a data item into this tree.

Parameters:

o - the data item will be inserted to this tree.

search

public RTreeCursor search(IRTreeEnvelopeSearch rs)

Gets a r-tree search curosr based on the specified search criteria. Through this cursor, data items which satisfy the search criteria will be fetched.

Parameters:

rs - search criteria. An IRTreeEnvelopeSearch instance.

Returns:

a r-tree cursor to search all data items that satisfy the search criteria.

getEnvelope

public Envelope getEnvelope()

Gets the entire envelope of this r-tree.

Returns:

an Envelope object.

clear

public void clear()

Clear up this tree.