dev.roanh.convexmerger.util

Class KDTree<T>

java.lang.Object

dev.roanh.convexmerger.animation.RenderableObject

dev.roanh.convexmerger.util.PartitionTree<T,KDTree<T>>

dev.roanh.convexmerger.util.KDTree<T>

Type Parameters:

T - The per cell item data type.

public class KDTree<T>
extends PartitionTree<T,KDTree<T>>

Implementation of a kd-tree for k = 2.

Field Summary

Fields

Modifier and Type	Field and Description
private java.awt.geom.Rectangle2D	bounds The axis aligned bounding rectangle defining the bounds of this kd-tree cell.
private KDTree<T>	high The high child of this kd-tree.
private KDTree<T>	low The low child of this kd-tree.
private KDTree<T>	parent The parent kd-tree this kd-tree is a cell in.
private java.awt.geom.Point2D	point The point defining the line splitting this kd-tree cell into a low and high cell.
private boolean	xAxis The way this kd-tree node is split into a low and high cell.

Constructor Summary

Constructors

Modifier	Constructor and Description
private	KDTree(KDTree<T> parent, java.util.List<java.awt.geom.Point2D> points, boolean xAxis) Constructs a new child kd-tree node with the given parent node, point set to build a sub tree with and axis to split on.
	KDTree(java.util.List<java.awt.geom.Point2D> points) Constructs a new kd-tree for the given point set.

Method Summary

Modifier and Type	Method and Description
java.awt.geom.Rectangle2D	getBounds() Gets the bounding rectangle of this kd-tree node.
java.util.List<KDTree<T>>	getChildren() Gets the child nodes of this tree node.
KDTree<T>	getHighNode() Gets the child node containing the high value points stored in the children of this node.
KDTree<T>	getLowNode() Gets the child node containing the low value points stored in the children of this node.
KDTree<T>	getParent() Gets the parent tree node of this node.
java.awt.geom.Point2D	getPoint() Gets the point defining the line dividing this kd-tree node into two child nodes.
KDTree<T>	getSelf() Gets 'this' partition tree.
java.awt.Shape	getShape() Gets the shape defining the boundary of this tree cell.
boolean	intersects(java.awt.geom.Line2D line) Checks if the given line intersects this kd-tree node.
boolean	isLeafCell() Checks if this tree node is a leaf cell.
void	render(java.awt.Graphics2D g) Renders this object.

Methods inherited from class dev.roanh.convexmerger.util.PartitionTree

addData, getData, getDepth, getHeight, setMarked, streamCells, streamLeafCells

Methods inherited from class dev.roanh.convexmerger.animation.RenderableObject

getAnimation, hasAnimation, renderOrAnimate, runAnimation, setAnimation

Methods inherited from class java.lang.Object

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

Field Detail

parent

private KDTree<T> parent

The parent kd-tree this kd-tree is a cell in. Will be null if this is the root node of the tree.

low

private KDTree<T> low

The low child of this kd-tree. This is the cell containing the points lower than the point for this KD tree. Will be null if this is a leaf cell.

high

private KDTree<T> high

The high child of this kd-tree. This is the cell containing the points higher than the point for this kd-tree. Will be null if this is a leaf cell.

point

private java.awt.geom.Point2D point

The point defining the line splitting this kd-tree cell into a low and high cell. Will be null if this is a leaf cell.

xAxis

private boolean xAxis

The way this kd-tree node is split into a low and high cell. If true the splitting line is vertical and otherwise the splitting line is horizontal.

bounds

private java.awt.geom.Rectangle2D bounds

The axis aligned bounding rectangle defining the bounds of this kd-tree cell.

Constructor Detail

KDTree

public KDTree(java.util.List<java.awt.geom.Point2D> points)

Constructs a new kd-tree for the given point set.

Parameters:

points - The points to build a kd-tree from.

KDTree

private KDTree(KDTree<T> parent,
               java.util.List<java.awt.geom.Point2D> points,
               boolean xAxis)

Constructs a new child kd-tree node with the given parent node, point set to build a sub tree with and axis to split on.

Parameters:

parent - The parent node of this kd-tree node.

points - The points to build a kd-subtree from.

xAxis - True if this cell should be split based on the X coordinate of points, false to split on the Y coordinate.

Method Detail

getPoint

public java.awt.geom.Point2D getPoint()

Gets the point defining the line dividing this kd-tree node into two child nodes.

Returns:

The point dividing this tree node.

getLowNode

public KDTree<T> getLowNode()

Gets the child node containing the low value points stored in the children of this node.

Returns:

The low value child node.

getHighNode

public KDTree<T> getHighNode()

Gets the child node containing the high value points stored in the children of this node.

Returns:

The high value child node.

intersects

public boolean intersects(java.awt.geom.Line2D line)

Checks if the given line intersects this kd-tree node.

Parameters:

line - The line to check for intersection.

Returns:

True if the given line intersects this kd-tree node.

getBounds

public java.awt.geom.Rectangle2D getBounds()

Gets the bounding rectangle of this kd-tree node.

Returns:

The bounding rectangle of this kd-tree node.

render

public void render(java.awt.Graphics2D g)

Description copied from class: RenderableObject

Renders this object.

Overrides:

render in class PartitionTree<T,KDTree<T>>

Parameters:

g - The graphics context to use.

getShape

public java.awt.Shape getShape()

Description copied from class: PartitionTree

Gets the shape defining the boundary of this tree cell.

Specified by:

getShape in class PartitionTree<T,KDTree<T>>

Returns:

The partition tree cell bounds.

isLeafCell

public boolean isLeafCell()

Description copied from class: PartitionTree

Checks if this tree node is a leaf cell.

Specified by:

isLeafCell in class PartitionTree<T,KDTree<T>>

Returns:

True if this tree node is a leaf cell.

getChildren

public java.util.List<KDTree<T>> getChildren()

Description copied from class: PartitionTree

Gets the child nodes of this tree node.

Specified by:

getChildren in class PartitionTree<T,KDTree<T>>

Returns:

The direct child nodes of this node.

getParent

public KDTree<T> getParent()

Description copied from class: PartitionTree

Gets the parent tree node of this node.

Specified by:

getParent in class PartitionTree<T,KDTree<T>>

Returns:

The parent node of this node or null if this is node is the root node of the tree.

getSelf

public KDTree<T> getSelf()

Description copied from class: PartitionTree

Gets 'this' partition tree.

Specified by:

getSelf in class PartitionTree<T,KDTree<T>>

Returns:

This partition tree.