Package org.jungrapht.visualization.spatial.rtree

Class LeafNode<T>

java.lang.Object

org.jungrapht.visualization.spatial.rtree.RTreeNode<T>

org.jungrapht.visualization.spatial.rtree.LeafNode<T>

All Implemented Interfaces:

Bounded, Node<T>, TreeNode

public class LeafNode<T>
extends RTreeNode<T>
implements Node<T>

a leaf node of an R-Tree. Contains a map of elements to their 2d bounds

Author:

Tom Nelson

Field Summary

Fields

Modifier and Type	Field	Description
static LeafNode	EMPTY	a LeafVertex with no children

Fields inherited from class org.jungrapht.visualization.spatial.rtree.RTreeNode

parent

Fields inherited from interface org.jungrapht.visualization.spatial.rtree.Node

m, M, marginIncrement

Method Summary

Modifier and Type	Method	Description
Node<T>	add(SplitterContext<T> splitterContext, Map.Entry<T,Rectangle2D> entry)	add the passed Entry to the map
Node<T>	add(SplitterContext<T> splitterContext, Map.Entry<T,Rectangle2D>... entries)
Node<T>	add(SplitterContext<T> splitterContext, T element, Rectangle2D bounds)
String	asString(String margin)
Point2D	centerOfGravity()
Collection<Shape>	collectGrids(Collection<Shape> list)	gather the bounds of the node children of this node
boolean	contains(Object key)
int	count()
static <T> LeafNode<T>	create(Collection<Map.Entry<T,Rectangle2D>> entries)
static <T> LeafNode<T>	create(Map.Entry<T,Rectangle2D> entry)
static <T> LeafNode<T>	create(T element, Rectangle2D bounds)
Rectangle2D	getBounds()	the bounding box of this node is held in the children map
Rectangle2D	getBoundsFor(T element)
Collection<? extends TreeNode>	getChildren()
LeafNode<T>	getContainingLeaf(T element)
Set<LeafNode<T>>	getContainingLeafs(Set<LeafNode<T>> containingLeafs, double x, double y)
Set<LeafNode<T>>	getContainingLeafs(Set<LeafNode<T>> containingLeafs, Point2D p)
T	getPickedObject(Point2D p)
Set<T>	getVisibleElements(Set<T> visibleElements, Shape shape)
boolean	isLeafChildren()	always false.
Node<T>	recalculateBounds()	called after a removal.
Node<T>	remove(T element)	remove passed element from the map if it exists call recalculateBounds to update all parent node bounds after removal of the element
int	size()	the number of children of this node
String	toString()

Methods inherited from class org.jungrapht.visualization.spatial.rtree.RTreeNode

getParent, setParent

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.jungrapht.visualization.spatial.rtree.Node

getParent, setParent

Field Detail

EMPTY

public static LeafNode EMPTY

a LeafVertex with no children

Method Detail

create

public static <T> LeafNode<T> create(Map.Entry<T,Rectangle2D> entry)

Type Parameters:

T - the type of the element

Parameters:

entry - the child for the newly created LeafVertex

Returns:

a newly created LeafVertex that contains the passed entry as its only element

create

public static <T> LeafNode<T> create(T element,
                                     Rectangle2D bounds)

Type Parameters:

T - the type of the element

Parameters:

element - the element child for the newly created LeafVertex

bounds - the bounds for the child of the newly created LeafVertex

Returns:

the newly created LeafVertex with one child element

create

public static <T> LeafNode<T> create(Collection<Map.Entry<T,Rectangle2D>> entries)

Type Parameters:

T - the type of the elements for this LeafVertex

Parameters:

entries - the elements for the newly created LeafVertex

Returns:

the newly created LeadVertex with the entries as children

centerOfGravity

public Point2D centerOfGravity()

Specified by:

centerOfGravity in interface Node<T>

add

public Node<T> add(SplitterContext<T> splitterContext,
                   Map.Entry<T,Rectangle2D>... entries)

Parameters:

splitterContext - how to split on overflow (R-Tree or R*-Tree)

entries - add to this LeafVertex

Returns:

the last node added to

add

public Node<T> add(SplitterContext<T> splitterContext,
                   T element,
                   Rectangle2D bounds)

Specified by:

add in interface Node<T>

Parameters:

splitterContext - how to split on overflow (R-Tree or R*-Tree)

element - the element to add

bounds - the bounding box of the element

Returns:

the highest node available after adding (this or parent)

isLeafChildren

public boolean isLeafChildren()

always false. children are elements, not LeafVertices

Specified by:

isLeafChildren in interface Node<T>

Returns:

remove

public Node<T> remove(T element)

remove passed element from the map if it exists call recalculateBounds to update all parent node bounds after removal of the element

Specified by:

remove in interface Node<T>

Parameters:

element - the element to remove

Returns:

the parent node, recurses to the top

recalculateBounds

public Node<T> recalculateBounds()

called after a removal. climb the tree to the root recalculating the bounds

Specified by:

recalculateBounds in interface Node<T>

Returns:

this LeafVertex

getBoundsFor

public Rectangle2D getBoundsFor(T element)

add

public Node<T> add(SplitterContext<T> splitterContext,
                   Map.Entry<T,Rectangle2D> entry)

add the passed Entry to the map

Parameters:

splitterContext - how to split on overflow

entry - the entry to add to the map

Returns:

the parent or this

contains

public boolean contains(Object key)

Parameters:

key - the element key to search for

Returns:

true if the key exists in the map. false otherwise

size

public int size()

the number of children of this node

Specified by:

size in interface Node<T>

Returns:

getContainingLeaf

public LeafNode<T> getContainingLeaf(T element)

Specified by:

getContainingLeaf in interface Node<T>

Parameters:

element - the element to find

Returns:

the LeafVertex that contains the passed element

getContainingLeafs

public Set<LeafNode<T>> getContainingLeafs(Set<LeafNode<T>> containingLeafs,
                                           Point2D p)

Specified by:

getContainingLeafs in interface Node<T>

Parameters:

p - the point to search for

Returns:

a Collection of LeafVertices that would contain the point

getContainingLeafs

public Set<LeafNode<T>> getContainingLeafs(Set<LeafNode<T>> containingLeafs,
                                           double x,
                                           double y)

Specified by:

getContainingLeafs in interface Node<T>

Parameters:

x - coordinate of the point to search for

y - coordinate of the point to search for

Returns:

a Collection of LeafVertices that would contain the passed coordinates

collectGrids

public Collection<Shape> collectGrids(Collection<Shape> list)

gather the bounds of the node children of this node

Specified by:

collectGrids in interface Node<T>

Parameters:

list - a list to populate with child bounds rectangles

Returns:

the list of child bounds rectangles

getBounds

public Rectangle2D getBounds()

the bounding box of this node is held in the children map

Specified by:

getBounds in interface Bounded

Specified by:

getBounds in interface TreeNode

Returns:

the bounding box of this node

getPickedObject

public T getPickedObject(Point2D p)

Specified by:

getPickedObject in interface Node<T>

Parameters:

p - a point to search for

Returns:

the map entry key whose bounds value contains the passed point

getVisibleElements

public Set<T> getVisibleElements(Set<T> visibleElements,
                                 Shape shape)

Specified by:

getVisibleElements in interface Node<T>

Parameters:

shape - a shape to filter the visible elements

Returns:

a subset of elements whose bounds intersect with the passed shape

count

public int count()

Specified by:

count in interface Node<T>

Returns:

the number of children in this node

asString

public String asString(String margin)

Specified by:

asString in interface Node<T>

getChildren

public Collection<? extends TreeNode> getChildren()

Specified by:

getChildren in interface TreeNode

toString

public String toString()

Overrides:

toString in class Object