|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectcom.sun.electric.database.topology.RTNode
public class RTNode
The RTNode class implements R-Trees. R-trees come from this paper: Guttman, Antonin, "R-Trees: A Dynamic Index Structure for Spatial Searching", ACM SIGMOD, 14:2, 47-57, June 1984.
R-trees are height-balanced trees in which all leaves are at the same depth and contain RTBounds objects (generally Geometric objects NodeInst and ArcInst). Entries higher in the tree store boundary information that tightly encloses the leaves below. All nodes hold from M to 2M entries, where M is 4. The bounding boxes of two entries may overlap, which allows arbitrary structures to be represented. A search for a point or an area is a simple recursive walk through the tree to collect appropriate leaf nodes. Insertion and deletion, however, are more complex operations. The figure below illustrates how R-Trees work:
Nested Class Summary | |
---|---|
static class |
RTNode.Search
Class to search a given area of a Cell. |
Method Summary | |
---|---|
void |
checkRTree(int level,
java.lang.Object env)
Method to check the validity of an RTree node. |
void |
displayRTree(Cell cell)
Debugging method to display this R-Tree. |
java.lang.Object |
getChild(int index)
Method to get the number of children of this RTNode. |
boolean |
getFlag()
Method to get the leaf/branch flag of this RTNode. |
int |
getTotal()
Method to get the number of children of this RTNode. |
static RTNode |
linkGeom(java.lang.Object env,
RTNode root,
RTBounds geom)
Method to link this RTBounds into the R-tree of its parent Cell. |
static RTNode |
makeTopLevel()
Method to create the top-level R-Tree structure for a new Cell. |
void |
printRTree(int indent)
Debugging method to print this R-Tree. |
int |
tallyRTree()
Method to return the number of leaf entries in this RTree. |
static RTNode |
unLinkGeom(java.lang.Object env,
RTNode root,
RTBounds geom)
Method to remove this geometry from the R-tree its parent cell. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Method Detail |
---|
public int getTotal()
public java.lang.Object getChild(int index)
public boolean getFlag()
public static RTNode makeTopLevel()
public static RTNode linkGeom(java.lang.Object env, RTNode root, RTBounds geom)
env
- the environment of this operation (for messages).root
- root of the RTree.geom
- RTBounds to link.
public static RTNode unLinkGeom(java.lang.Object env, RTNode root, RTBounds geom)
env
- the environment of this operation (for messages).root
- root of the RTree.geom
- RTBounds to unlink.
public void printRTree(int indent)
indent
- the level of the tree, for proper indentation.public void displayRTree(Cell cell)
cell
- the Cell in which to show the R-Tree.public int tallyRTree()
public void checkRTree(int level, java.lang.Object env)
level
- the level of the node in the tree (for error reporting purposes).env
- the environment in which this node resides.
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |