Package org.jungrapht.visualization.spatial

Class SpatialQuadTree<V>

java.lang.Object

org.jungrapht.visualization.spatial.AbstractSpatial<V,V>

org.jungrapht.visualization.spatial.SpatialQuadTree<V>

Type Parameters:

V - the node type

All Implemented Interfaces:

LayoutStateChange.Listener, LayoutVertexPositionChange.Listener<V>, TreeNode, Spatial<V,V>

public class SpatialQuadTree<V>
extends AbstractSpatial<V,V>
implements TreeNode, Spatial<V,V>, LayoutVertexPositionChange.Listener<V>

A spatial data structure that uses a quadtree.

Author:

Tom Nelson

Nested Class Summary

Nested classes/interfaces inherited from interface org.jungrapht.visualization.spatial.Spatial

Spatial.NoOp<T,NT>

Field Summary

Fields inherited from class org.jungrapht.visualization.spatial.AbstractSpatial

layoutModel, pickShapes, rectangle

Constructor Summary

Constructors

Constructor	Description
SpatialQuadTree(LayoutModel<V> layoutModel)
SpatialQuadTree(LayoutModel<V> layoutModel, double width, double height)
SpatialQuadTree(LayoutModel<V> layoutModel, int level, double x, double y, double width, double height)
SpatialQuadTree(LayoutModel<V> layoutModel, int pLevel, Rectangle2D area)

Method Summary

Modifier and Type	Method	Description
void	clear()	destroy the current spatial structure
boolean	equals(Object o)
Rectangle2D	getBounds()
Collection<? extends TreeNode>	getChildren()
V	getClosestElement(double x, double y)	get the node that is closest to the passed (x,y)
V	getClosestElement(Point2D p)
TreeNode	getContainingLeaf(Object element)
Set<SpatialQuadTree<V>>	getContainingLeafs(double x, double y)
Set<SpatialQuadTree<V>>	getContainingLeafs(Point2D p)
SpatialQuadTree<V>	getContainingQuadTreeLeaf(double x, double y)
SpatialQuadTree<V>	getContainingQuadTreeLeaf(Point2D p)	find the cell that would contain the passed point
TreeNode	getContainingQuadTreeLeaf(V node)
List<Shape>	getGrid()
Rectangle2D	getLayoutArea()	tha layout area that this tree cell operates over
protected int	getLevel()
protected org.jungrapht.visualization.spatial.SpatialQuadTree.Quadrant	getQuadrant(double x, double y)	find the quadrant that the point would be in
protected org.jungrapht.visualization.spatial.SpatialQuadTree.Quadrant	getQuadrant(Point p)	find the quadrant that the point would be in
Set<V>	getVertices()
List<Spatial>	getVertices(List<Spatial> list)
Set<V>	getVisibleElements(Shape shape)
Set<V>	getVisibleVertices(Rectangle2D r)
int	hashCode()
protected void	insert(V p)
void	layoutVertexPositionChanged(LayoutVertexPositionChange.Event<V> evt)
void	layoutVertexPositionChanged(LayoutVertexPositionChange.GraphEvent<V> evt)
void	recalculate()	rebuild the data structure
protected Set<V>	retrieve(Set<V> returnObjects, Rectangle2D r)
protected Set<V>	retrieve(Set<V> returnObjects, Shape shape)	Return all objects that are within the passed shape This is needed when the layout is rotated/skewed and the shape edges are no longer parallel to the grid edges.
void	setBounds(Rectangle2D bounds)	reset the side of this structure
SpatialQuadTree<V>	setMaxLevels(int l)
SpatialQuadTree<V>	setMaxObjects(int o)
protected void	split()
String	toString()
void	update(V node, Point location)	Update the structure for the passed node.

Methods inherited from class org.jungrapht.visualization.spatial.AbstractSpatial

getClosest, getLayoutModel, getPickShapes, isActive, layoutStateChanged, setActive

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface org.jungrapht.visualization.layout.event.LayoutStateChange.Listener

layoutStateChanged

Methods inherited from interface org.jungrapht.visualization.spatial.Spatial

getLayoutModel, getPickShapes, getUnion, getUnion, isActive, setActive

Constructor Detail

SpatialQuadTree

public SpatialQuadTree(LayoutModel<V> layoutModel)

Parameters:

layoutModel -

SpatialQuadTree

public SpatialQuadTree(LayoutModel<V> layoutModel,
                       double width,
                       double height)

Parameters:

layoutModel -

width -

height -

SpatialQuadTree

public SpatialQuadTree(LayoutModel<V> layoutModel,
                       int level,
                       double x,
                       double y,
                       double width,
                       double height)

Parameters:

level - level to start at. 0 is the root

x -

y -

width -

height -

SpatialQuadTree

public SpatialQuadTree(LayoutModel<V> layoutModel,
                       int pLevel,
                       Rectangle2D area)

Method Detail

getBounds

public Rectangle2D getBounds()

Specified by:

getBounds in interface TreeNode

getChildren

public Collection<? extends TreeNode> getChildren()

Specified by:

getChildren in interface TreeNode

setMaxObjects

public SpatialQuadTree<V> setMaxObjects(int o)

Parameters:

o - max number of objects allowed

Returns:

this QuadTree

setMaxLevels

public SpatialQuadTree<V> setMaxLevels(int l)

Parameters:

l - max levels allowed

Returns:

getLevel

protected int getLevel()

Returns:

the level of this cell

getVertices

public Set<V> getVertices()

Returns:

the nodes in this cell, assuming it is a leaf

clear

public void clear()

Description copied from interface: Spatial

destroy the current spatial structure

Specified by:

clear in interface Spatial<V,V>

split

protected void split()

getQuadrant

protected org.jungrapht.visualization.spatial.SpatialQuadTree.Quadrant getQuadrant(Point p)

find the quadrant that the point would be in

Parameters:

p - the point of interest

Returns:

the quadrant that would contain the point

getQuadrant

protected org.jungrapht.visualization.spatial.SpatialQuadTree.Quadrant getQuadrant(double x,
                                                                                   double y)

find the quadrant that the point would be in

Parameters:

x - , y the point of interest

Returns:

the quadrant that would contain the point

insert

protected void insert(V p)

retrieve

protected Set<V> retrieve(Set<V> returnObjects,
                          Rectangle2D r)

retrieve

protected Set<V> retrieve(Set<V> returnObjects,
                          Shape shape)

Return all objects that are within the passed shape This is needed when the layout is rotated/skewed and the shape edges are no longer parallel to the grid edges.

getVertices

public List<Spatial> getVertices(List<Spatial> list)

getGrid

public List<Shape> getGrid()

Specified by:

getGrid in interface Spatial<V,V>

Returns:

a geometic representation of the spatial structure

getVisibleElements

public Set<V> getVisibleElements(Shape shape)

Specified by:

getVisibleElements in interface Spatial<V,V>

Parameters:

shape - the possibly non-rectangular area of interest

Returns:

the nodes that are in the quadtree cells that intersect with the passed shape

getVisibleVertices

public Set<V> getVisibleVertices(Rectangle2D r)

Parameters:

r -

Returns:

the nodes that are in the quadtree cells that intersect with the passed rectangle

getLayoutArea

public Rectangle2D getLayoutArea()

tha layout area that this tree cell operates over

Specified by:

getLayoutArea in interface Spatial<V,V>

Returns:

recalculate

public void recalculate()

Description copied from interface: Spatial

rebuild the data structure

Specified by:

recalculate in interface Spatial<V,V>

getContainingQuadTreeLeaf

public TreeNode getContainingQuadTreeLeaf(V node)

Parameters:

node - the node to search for

Returns:

the quadtree leaf that contains the passed node

getContainingLeafs

public Set<SpatialQuadTree<V>> getContainingLeafs(Point2D p)

Specified by:

getContainingLeafs in interface Spatial<V,V>

Parameters:

p - a point to search in the spatial structure

Returns:

all leaf nodes that contain the passed point

getContainingLeafs

public Set<SpatialQuadTree<V>> getContainingLeafs(double x,
                                                  double y)

Specified by:

getContainingLeafs in interface Spatial<V,V>

Parameters:

x - the x location to search for

y - the y location to search for

Returns:

all leaf nodes that contain the passed coordinates

getContainingLeaf

public TreeNode getContainingLeaf(Object element)

Specified by:

getContainingLeaf in interface Spatial<V,V>

Parameters:

element - element to search for

Returns:

the leaf node that currently contains the element (not a spatial search)

getContainingQuadTreeLeaf

public SpatialQuadTree<V> getContainingQuadTreeLeaf(Point2D p)

find the cell that would contain the passed point

Parameters:

p - the point of interest

Returns:

the cell that would contain p

getContainingQuadTreeLeaf

public SpatialQuadTree<V> getContainingQuadTreeLeaf(double x,
                                                    double y)

Parameters:

x - location of interest

y - location of interest

Returns:

the cell that would contain (x, y)

getClosestElement

public V getClosestElement(Point2D p)

Specified by:

getClosestElement in interface Spatial<V,V>

Parameters:

p - a point to search in the spatial structure

Returns:

the closest element to the passed point

getClosestElement

public V getClosestElement(double x,
                           double y)

get the node that is closest to the passed (x,y)

Specified by:

getClosestElement in interface Spatial<V,V>

Parameters:

x -

y -

Returns:

the node closest to x,y

setBounds

public void setBounds(Rectangle2D bounds)

reset the side of this structure

Specified by:

setBounds in interface Spatial<V,V>

Parameters:

bounds - the new bounds for the data struture

update

public void update(V node,
                   Point location)

Update the structure for the passed node. If the node is still in the same cell, don't rebuild the structure. If it moved to a new cell, rebuild the structure

Specified by:

update in interface Spatial<V,V>

Parameters:

node -

location - the location of the element

layoutVertexPositionChanged

public void layoutVertexPositionChanged(LayoutVertexPositionChange.Event<V> evt)

Specified by:

layoutVertexPositionChanged in interface LayoutVertexPositionChange.Listener<V>

layoutVertexPositionChanged

public void layoutVertexPositionChanged(LayoutVertexPositionChange.GraphEvent<V> evt)

Specified by:

layoutVertexPositionChanged in interface LayoutVertexPositionChange.Listener<V>

equals

public boolean equals(Object o)

Overrides:

equals in class Object

hashCode

public int hashCode()

Overrides:

hashCode in class Object

toString

public String toString()

Overrides:

toString in class Object