org.deegree_impl.io.rtree
Class RTree

java.lang.Object
  org.deegree_impl.io.rtree.RTree

public class RTree

extends java.lang.Object

Implementierung eines R-Baumes nach den Algorithmen von Antonio Guttman.

Version:

1.4

Author:

Wolfgang Bär

Field Summary

PageFile

file

Constructor Summary

RTree(int dimension, int capacity)
Erzeugt einen leeren R-Baum.

RTree(int dimension, int capacity, java.lang.String fileName)
Erzeugt neuen R-Baum abgespeichert in Persistenter PageFile.

RTree(java.lang.String fileName)
Erzeugt R-Baum basierend auf übergebener Persistenter PageFile.

Method Summary

private void	adjustTree(Node n1, Node n2)
private LeafNode	chooseLeaf(Node node, HyperBoundingBox box)
void	close() Closes the rtree and frees the ressources.
private void	condenseTree(Node n, java.util.Stack stack)
java.lang.Object[]	contains(HyperBoundingBox box) Sucht alle Einträge, deren HyperBoundingBoxes die die übergebene enthalten.
private void	containsSearch(Node node1, java.util.Vector v, HyperBoundingBox box)
boolean	delete(HyperBoundingBox box) Löscht alle Eintrag aus dem R-Baum
boolean	delete(HyperBoundingBox box, int objID) Löscht einen Eintrag aus dem R-Baum
java.lang.Object[]	find(HyperBoundingBox box) Findet alle Eintrag aus dem R-Baum
private void	findLeaf(Node node, HyperBoundingBox box, int objID, java.util.Vector v)
private void	findSearch(Node node1, java.util.Vector v, HyperBoundingBox box)
boolean	insert(java.lang.Object obj, HyperBoundingBox box) Fügt ein Object mit seiner HyperBoundingBox in den R-Baum ein.
java.lang.Object[]	intersects(HyperBoundingBox box) Sucht alle Einträge, deren HyperBoundingBoxes mit der übergebenen überlappen.
private void	intersectsSearch(Node node1, java.util.Vector v, HyperBoundingBox box)
double[]	nearestNeighbour(HyperPoint point) Holt den nächsten Nachbarn zum angegebenen Suchpunkt.
private double[]	nearestNeighbour(Node node, HyperPoint point, double[] temp)
private int[]	pickNext(Node node, boolean[] marker, Node group1, Node group2)
private int[]	pickSeeds(Node node)
private Node[]	splitNode(Node node)

Methods inherited from class java.lang.Object

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

Field Detail

file

public PageFile file

Constructor Detail

RTree

public RTree(int dimension,
             int capacity)
      throws RTreeException

Erzeugt einen leeren R-Baum. Mit MemoryPageFile und leerem RootNode.

Parameters:

dimension - number of dimensions of all data

capacity - maximum load per node (page) plus 1 for overflow

RTree

public RTree(int dimension,
             int capacity,
             java.lang.String fileName)
      throws RTreeException

Erzeugt neuen R-Baum abgespeichert in Persistenter PageFile.

Parameters:

dimension - number of dimensions of all data

capacity - maximum load per node (page) plus 1 for overflow

fileName - filename of the persistent pagefile

RTree

public RTree(java.lang.String fileName)
      throws RTreeException

Erzeugt R-Baum basierend auf übergebener Persistenter PageFile.

Parameters:

fileName - filename of an existing persistent pagefile

Method Detail

intersects

public java.lang.Object[] intersects(HyperBoundingBox box)
                              throws RTreeException

Sucht alle Einträge, deren HyperBoundingBoxes mit der übergebenen überlappen.

Parameters:

box - für Überlappung

Returns:

Object[] Array von gefundenen Objekten (Integer-Objekte)

Throws:

RTreeException

contains

public java.lang.Object[] contains(HyperBoundingBox box)
                            throws RTreeException

Sucht alle Einträge, deren HyperBoundingBoxes die die übergebene enthalten.

Parameters:

box - die enthalten sein soll

Returns:

Object[] Array von gefundenen Objekten (Integer-Objekte)

Throws:

RTreeException

containsSearch

private void containsSearch(Node node1,
                            java.util.Vector v,
                            HyperBoundingBox box)

Parameters:

node1 -

v -

box -

intersectsSearch

private void intersectsSearch(Node node1,
                              java.util.Vector v,
                              HyperBoundingBox box)

Parameters:

node1 -

v -

box -

insert

public boolean insert(java.lang.Object obj,
                      HyperBoundingBox box)
               throws RTreeException

Fügt ein Object mit seiner HyperBoundingBox in den R-Baum ein.

Parameters:

obj - das einzufügende Object (Integer-Object)

box - dessen HyperBoundingBox

Returns:

boolean true, wenn erfolgreich

Throws:

RTreeException

splitNode

private Node[] splitNode(Node node)
                  throws PageFileException

Parameters:

node -

Returns:

Throws:

PageFileException

pickSeeds

private int[] pickSeeds(Node node)

Parameters:

node -

Returns:

pickNext

private int[] pickNext(Node node,
                       boolean[] marker,
                       Node group1,
                       Node group2)

Parameters:

node -

marker -

group1 -

group2 -

Returns:

chooseLeaf

private LeafNode chooseLeaf(Node node,
                            HyperBoundingBox box)

Parameters:

node -

box -

Returns:

nearestNeighbour

public double[] nearestNeighbour(HyperPoint point)
                          throws RTreeException

Holt den nächsten Nachbarn zum angegebenen Suchpunkt.

Parameters:

point - Suchpunkt

Returns:

double[] Stelle 0 = Distanz, Stelle 1 Data-Pointer (als double)

Throws:

RTreeException

nearestNeighbour

private double[] nearestNeighbour(Node node,
                                  HyperPoint point,
                                  double[] temp)

Parameters:

node -

point -

temp -

Returns:

close

public void close()
           throws RTreeException

Closes the rtree and frees the ressources.

Throws:

RTreeException - if an error occures.

delete

public boolean delete(HyperBoundingBox box,
                      int objID)
               throws RTreeException

Löscht einen Eintrag aus dem R-Baum

Parameters:

box - BoundingBox des Eintrages

objID - Objekt-ID zur genauen Identifizierung.

Returns:

boolean true, wenn erfolgreich

Throws:

RTreeException

delete

public boolean delete(HyperBoundingBox box)
               throws RTreeException

Löscht alle Eintrag aus dem R-Baum

Parameters:

box - BoundingBox der Eintragungen

Returns:

boolean true, wenn erfolgreich

Throws:

RTreeException

find

public java.lang.Object[] find(HyperBoundingBox box)
                        throws RTreeException

Findet alle Eintrag aus dem R-Baum

Parameters:

box - BoundingBox der Eintragungen

Returns:

Object[] Array von gefundenen Objekten (Integer-Objekte)

Throws:

RTreeException

findSearch

private void findSearch(Node node1,
                        java.util.Vector v,
                        HyperBoundingBox box)

Parameters:

node1 -

v -

box -

findLeaf

private void findLeaf(Node node,
                      HyperBoundingBox box,
                      int objID,
                      java.util.Vector v)

Parameters:

node -

box -

objID -

v -

condenseTree

private void condenseTree(Node n,
                          java.util.Stack stack)
                   throws PageFileException

Parameters:

n -

stack -

Throws:

PageFileException

adjustTree

private void adjustTree(Node n1,
                        Node n2)
                 throws PageFileException

Parameters:

n1 -

n2 -

Throws:

PageFileException