V
- the type of all values in the QuadTree
public static final class QuadTree.Node<V>
extends java.lang.Object
QuadTree
.
Represents a collection of PointD
keys and V values within a
QuadTree
. This collection and all references to related QuadTree.Node
instances within the QuadTree
are exposed as read-only properties.
QuadTree.Node
was inspired by the QuadTreeNode
class by
Michael J. Laszlo, Computational Geometry and Computer Graphics in C++,
Prentice Hall 1996, p.236ff.
Modifier and Type | Field and Description |
---|---|
RectD |
bounds
|
PointD |
center
The center of the
bounds of the QuadTree.Node . |
QuadTree.Node<V> |
parent
The parent of the
QuadTree.Node in the QuadTree . |
int |
signature
The unique signature of the
QuadTree.Node . |
Modifier and Type | Method and Description |
---|---|
java.util.Map<PointD,V> |
entries()
Gets all keys and values stored in the
QuadTree.Node . |
int |
gridX()
Gets the x-coordinate of the
QuadTree.Node in the tree structure. |
int |
gridY()
Gets the y-coordinate of the
QuadTree.Node in the tree structure. |
boolean |
hasCapacity()
Indicates whether the
QuadTree.Node has any remaining entries() capacity. |
boolean |
isLeaf()
Indicates whether the
QuadTree.Node is a leaf node. |
int |
level()
Gets the level of the
QuadTree.Node in the QuadTree . |
QuadTree.Node<V> |
maxXmaxY()
Gets the child
QuadTree.Node for the bounds quadrant
containing its greater x- and greater y-coordinates. |
QuadTree.Node<V> |
maxXminY()
Gets the child
QuadTree.Node for the bounds quadrant
containing its greater x- and smaller y-coordinates. |
QuadTree.Node<V> |
minXmaxY()
Gets the child
QuadTree.Node for the bounds quadrant
containing its smaller x- and greater y-coordinates. |
QuadTree.Node<V> |
minXminY()
Gets the child
QuadTree.Node for the bounds quadrant
containing its smaller x- and smaller y-coordinates. |
QuadTree<V> |
owner()
Gets the
QuadTree that contains the QuadTree.Node . |
public final RectD bounds
RectD
bounds of all PointD
keys in the QuadTree.Node
.
Indicates the subrange of the containing QuadTree
that is covered
by the QuadTree.Node
and its children. Always has a positive RectD.width()
and RectD.height()
. The two dimensions are not necessarily equal.
Any PointD
keys stored in the associated entries()
lie within
bounds
. The extreme RectD.max
coordinates are considered part
of the neighboring QuadTree.Node
on that side, if any.
public final PointD center
bounds
of the QuadTree.Node
.
Divides the associated bounds
into four equal-sized quadrants,
corresponding to the minXminY()
, minXmaxY()
, maxXminY()
,
and maxXmaxY()
child nodes. center
is precomputed to speed up
the traversal of the tree structure.public final QuadTree.Node<V> parent
QuadTree.Node
in the QuadTree
.
Never null
except for the permanent QuadTree.rootNode
of the containing QuadTree
.public final int signature
QuadTree.Node
.
Holds an Integer
value containing a bitwise combination of level()
,
gridX()
, and gridY()
. This value uniquely identifies the position
of each QuadTree.Node
in the containing QuadTree
, and also serves as its
key within the QuadTree.nodes()
hashtable.public java.util.Map<PointD,V> entries()
QuadTree.Node
.
Usually contains up to QuadTree.capacity
elements when not null
.
If level()
equals QuadTree.MAX_LEVEL
, the number of elements is
unbounded. Use the containing QuadTree
to add, change, or remove elements.
If entries()
is valid, the four child links minXminY()
,
minXmaxY()
, maxXminY()
, and maxXmaxY()
are all null
.
Conversely, at least one link is valid if entries()
is null
.
public int gridX()
QuadTree.Node
in the tree structure.
Returns the middle 14 bits of signature
.QuadTree.Node
within the grid of its
level()
, ranging from zero to 2^level()
public int gridY()
QuadTree.Node
in the tree structure.
Returns the highest 14 bits of signature
.QuadTree.Node
within the grid of its
level()
, ranging from zero to 2^level()
public boolean hasCapacity()
QuadTree.Node
has any remaining entries()
capacity.
Does not check whether level()
equals QuadTree.MAX_LEVEL
, in which case
the number of entries()
may exceed QuadTree.capacity
.true
if isLeaf()
is true
and the number of
entries()
is less than QuadTree.capacity
, else false
public boolean isLeaf()
true
if the QuadTree.Node
is a leaf node,
false
if it is an internal nodepublic int level()
QuadTree.Node
in the QuadTree
,
ranging from zero to QuadTree.MAX_LEVEL
public QuadTree.Node<V> maxXmaxY()
QuadTree.Node
for the bounds
quadrant
containing its greater x- and greater y-coordinates.QuadTree.Node
for the bounds
quadrant containing its
greater x- and greater y-coordinates, or null
if nonepublic QuadTree.Node<V> maxXminY()
QuadTree.Node
for the bounds
quadrant
containing its greater x- and smaller y-coordinates.QuadTree.Node
for the bounds
quadrant containing its
greater x- and smaller y-coordinates, or null
if nonepublic QuadTree.Node<V> minXmaxY()
QuadTree.Node
for the bounds
quadrant
containing its smaller x- and greater y-coordinates.QuadTree.Node
for the bounds
quadrant containing its
smaller x- and greater y-coordinates, or null
if nonepublic QuadTree.Node<V> minXminY()
QuadTree.Node
for the bounds
quadrant
containing its smaller x- and smaller y-coordinates.QuadTree.Node
for the bounds
quadrant containing its
smaller x- and smaller y-coordinates, or null
if nonepublic QuadTree<V> owner()
QuadTree
that contains the QuadTree.Node
.
Returns null
if the QuadTree.Node
has been removed from its QuadTree
.
Otherwise, returns the same valid object throughout the lifetime of the QuadTree.Node
.QuadTree
that contains the QuadTree.Node