V
- the type of all values in the QuadTree
public class QuadTree<V> extends java.util.AbstractMap<PointD,V>
PointD
keys and arbitrary values
that are sorted in two dimensions using a quadrant tree.
Provides a two-dimensional search tree with PointD
keys. The root node
covers a specified rectangle (not necessarily a square), and each child node
recursively covers one quadrant of its parent rectangle. Each leaf node holds
one or more key-and-value pairs in a hashtable. Internal nodes hold no data.
The tree structure is exposed through the QuadTree.Node
class. You can find the
node associated with any given key, or with any given tree level and quadrant
grid coordinates, and follow links to its four descendants and parent node.
All tree nodes have a unique signature that doubles as their key in a hashtable,
providing fast tree-wide enumeration and O(1) access to any node with a given level
and quadrant grid coordinates. findNode(PointD)
exploits this fact
for a depth probe algorithm that greatly shortens search times in large trees.
findRange(org.kynosarges.tektosyne.geometry.PointD, double)
performs a two-dimensional range search that finds
all elements within a given rectangular or circular key range.
Java Collections Framework features are provided by extending AbstractMap
,
and AbstractSet
for key-and-value entries. Keys cannot be null
but
values may be null
. Iterators do not support modification, and do not check
for concurrent external modifications.
QuadTree
was inspired by the QuadTree
class by Michael J. Laszlo,
Computational Geometry and Computer Graphics in C++, Prentice Hall 1996, p.231ff.
Modifier and Type | Class and Description |
---|---|
static class |
QuadTree.Node<V>
Provides a generic tree node within a
QuadTree . |
Modifier and Type | Field and Description |
---|---|
RectD |
bounds
|
int |
capacity
The maximum capacity for the
QuadTree.Node.entries() collections
of all leaf nodes() above MAX_LEVEL . |
static int |
MAX_LEVEL
The maximum level for any
QuadTree . |
static int |
PROBE_LEVEL
The minimum level at which
findNode(PointD) begins using a depth probe. |
QuadTree.Node<V> |
rootNode
The fixed
QuadTree.Node at the root of the QuadTree . |
Constructor and Description |
---|
QuadTree(RectD bounds)
|
QuadTree(RectD bounds,
int capacity)
|
QuadTree(RectD bounds,
java.util.Map<PointD,V> map)
|
Modifier and Type | Method and Description |
---|---|
boolean |
containsKey(java.lang.Object key)
Determines whether the
QuadTree contains the specified key. |
boolean |
containsKey(PointD key,
QuadTree.Node<V> node)
Determines whether the
QuadTree contains the specified key,
searching the specified QuadTree.Node first. |
boolean |
containsValue(java.lang.Object value)
Determines whether the
QuadTree contains the specified value. |
boolean |
containsValue(V value,
QuadTree.Node<V> node)
Determines whether the
QuadTree contains the specified value. |
void |
copyTo(java.util.Map.Entry<PointD,V>[] array,
int arrayIndex)
Copies all
QuadTree entries to the specified array,
starting at the specified array index. |
java.util.Set<java.util.Map.Entry<PointD,V>> |
entrySet()
Gets a
Set view of all entries in the QuadTree . |
QuadTree.Node<V> |
findNode(int level,
int gridX,
int gridY)
Finds the
QuadTree.Node at the specified level and grid coordinates within the QuadTree . |
QuadTree.Node<V> |
findNode(PointD key)
Finds the
QuadTree.Node within the QuadTree that should contain the specified key. |
QuadTree.Node<V> |
findNodeByValue(V value)
Finds a
QuadTree.Node within the QuadTree that contains the specified value. |
java.util.Map<PointD,V> |
findRange(PointD center,
double radius)
Finds all entries in the
QuadTree whose keys lie within the specified circular range. |
java.util.Map<PointD,V> |
findRange(RectD range)
Finds all entries in the
QuadTree whose keys lie within the specified rectangular range. |
V |
get(java.lang.Object key)
Gets the value associated with the specified key in the
QuadTree . |
QuadTree.Node<V> |
move(PointD oldKey,
PointD newKey,
QuadTree.Node<V> node)
Moves the specified entry to a different key within the
QuadTree . |
java.util.Map<java.lang.Integer,QuadTree.Node<V>> |
nodes()
Gets all
QuadTree.Node instances in the QuadTree . |
V |
put(PointD key,
V value)
Puts the specified entry in the
QuadTree . |
void |
putAll(java.util.Map<? extends PointD,? extends V> map)
Puts all entries from the specified
Map in the QuadTree . |
V |
remove(java.lang.Object key)
Removes the entry with the specified key from the
QuadTree . |
boolean |
remove(java.lang.Object key,
java.lang.Object value)
Removes the specified key and value from the
QuadTree . |
V |
replace(PointD key,
V value)
Replaces the value of the specified existing key with the specified value.
|
boolean |
replace(PointD key,
V oldValue,
V newValue)
Replaces the value of the specified key with the specified value,
but only if currently mapped to the specified existing value.
|
void |
setProbeUseBitMask(boolean value)
Enables or disables the use of a bit mask for finding depth probe levels.
|
clear, clone, equals, hashCode, isEmpty, keySet, size, toString, values
public static final int MAX_LEVEL
QuadTree
.
Holds the zero-based index of the deepest level in any QuadTree
. The maximum
total number of levels therefore equals MAX_LEVEL
+ 1, including the
rootNode
at level zero.
When a QuadTree.Node
is created on MAX_LEVEL
, its maximum capacity
is ignored so that its QuadTree.Node.entries()
collection may grow unbounded.
MAX_LEVEL
is fixed at 14 so that each QuadTree.Node
can be uniquely identified by
a 32-bit QuadTree.Node.signature
containing a bitwise combination of the following indices:
QuadTree.Node.level()
.
QuadTree.Node.gridX()
index.
QuadTree.Node.gridY()
index.
With a MAX_LEVEL
of 14, the deepest level can hold 16,384 x 16,384 nodes,
and the entire QuadTree
can hold 357,913,941 nodes.
public static final int PROBE_LEVEL
findNode(PointD)
begins using a depth probe.
findNode(PointD)
switches from a normal tree search to a heuristic depth probe algorithm
when the number of nodes()
in the QuadTree
reaches 4^PROBE_LEVEL
,
indicating that a large proportion of nodes()
resides at or below that level.
PROBE_LEVEL
is currently fixed at four, so that the depth probe starts at 256
nodes()
. PROBE_LEVEL
cannot be less than two since the depth probe ascends
two levels at a time.
public final RectD bounds
RectD
bounds of all keys in the QuadTree
.
Holds a RectD
with positive RectD.width()
and RectD.height()
that contains all PointD
keys in the QuadTree
.
The QuadTree
always divides both dimensions into the same number of grid cells
at each QuadTree.Node.level()
, but the dimensions do not have to be equal.
Attempting to add a PointD
key outside of bounds
always throws an
IllegalArgumentException
, and searching for such a key always fails.
public final int capacity
QuadTree.Node.entries()
collections
of all leaf nodes()
above MAX_LEVEL
.
Usually indicates the maximum number of elements in the QuadTree.Node.entries()
collection
of a QuadTree.Node
. However, capacity
is ignored and the collection size is
unbounded for any QuadTree.Node
whose QuadTree.Node.level()
equals MAX_LEVEL
.public final QuadTree.Node<V> rootNode
QuadTree.Node
at the root of the QuadTree
.
Never removed from the QuadTree
. An empty QuadTree
contains only the
rootNode
. This is the only QuadTree.Node
whose QuadTree.Node.entries()
collection
may be empty when it has no descendants.
All other nodes are descendants of rootNode
. The chain of QuadTree.Node.parent
links from any other QuadTree.Node
in the QuadTree
ends in the rootNode
,
whose own QuadTree.Node.parent
is always null
.
public QuadTree(RectD bounds)
bounds
- the RectD
bounds of all keys in the QuadTree
java.lang.IllegalArgumentException
- if the RectD.width()
or RectD.height()
of bounds
is equal to or less than zerojava.lang.NullPointerException
- if bounds
is null
public QuadTree(RectD bounds, int capacity)
bounds
- the RectD
bounds of all keys in the QuadTree
capacity
- the maximum capacity for the QuadTree.Node.entries()
collections
of all leaf nodes()
above MAX_LEVEL
java.lang.IllegalArgumentException
- if capacity
or the RectD.width()
or RectD.height()
of bounds
is equal to or less than zerojava.lang.NullPointerException
- if bounds
is null
public QuadTree(RectD bounds, java.util.Map<PointD,V> map)
QuadTree
with the specified bounds
and initial elements copied from the specified Map
.
capacity
defaults to 128. Calls putAll(java.util.Map<? extends org.kynosarges.tektosyne.geometry.PointD, ? extends V>)
to copy the
elements of the specified map
into the QuadTree
.bounds
- the RectD
bounds of all keys in the QuadTree
map
- the Map
providing initial elements for the QuadTree
java.lang.IllegalArgumentException
- if the RectD.width()
or RectD.height()
of bounds
is equal to or less than zero, or if map
contains
a PointD
key that lies outside of bounds
java.lang.NullPointerException
- if bounds
or map
is null
public boolean containsKey(PointD key, QuadTree.Node<V> node)
QuadTree
contains the specified key,
searching the specified QuadTree.Node
first.
Generally succeeds if findNode(PointD)
finds a QuadTree.Node
that contains the specified key
.
However, if the specified node
is a valid leaf node that contains
key
, containsKey
succeeds immediately without calling
findNode(PointD)
, resulting in an O(1) operation.
key
- the PointD
key to findnode
- an optional QuadTree.Node
to search for key
before searching the entire QuadTree
true
if the QuadTree
contains key
, else false
java.lang.IllegalArgumentException
- if node
is not null
,
and its QuadTree.Node.owner()
differs from the QuadTree
java.lang.NullPointerException
- if key
is null
public boolean containsValue(V value, QuadTree.Node<V> node)
QuadTree
contains the specified value.
Generally succeeds if findNodeByValue(V)
finds a QuadTree.Node
that
contains the specified value
, which may be null
.
However, if the specified node
is a valid leaf node that contains
value
, containsValue
succeeds immediately without calling
findNodeByValue(V)
, resulting in an O(k) operation where k is the
number of QuadTree.Node.entries()
stored in node
.
value
- the V value to findnode
- an optional QuadTree.Node
to search for value
before searching the entire QuadTree
true
if the QuadTree
associates value
with at least one PointD
key, else false
java.lang.IllegalArgumentException
- if node
is not null
,
and its QuadTree.Node.owner()
differs from the QuadTree
public void copyTo(java.util.Map.Entry<PointD,V>[] array, int arrayIndex)
QuadTree
entries to the specified array,
starting at the specified array index.
Copies entries in the Iterator
sequence of entrySet()
which is arbitrary.array
- the array that receives all QuadTree
entriesarrayIndex
- the zero-based index in array
where copying beginsjava.lang.ArrayIndexOutOfBoundsException
- if arrayIndex
is less than zero, or
arrayIndex
plus AbstractMap.size()
is greater than the length of array
java.lang.NullPointerException
- if array
is null
public QuadTree.Node<V> findNode(int level, int gridX, int gridY)
QuadTree.Node
at the specified level and grid coordinates within the QuadTree
.
Returns null
in the following cases:
level
is less than zero or greater than MAX_LEVEL
gridX
and/or gridY
is less than zero, or equal to or greater
than the number of grid cells in the corresponding dimension at level
QuadTree.Node
exists at the specified location
findNode
combines its arguments into the unique QuadTree.Node.signature
of the desired QuadTree.Node
which is used retrieve the node from the nodes()
hashtable. This is an O(1) operation.level
- the QuadTree.Node.level()
to searchgridX
- the QuadTree.Node.gridX()
coordinate to findgridY
- the QuadTree.Node.gridY()
coordinate to findQuadTree.Node
at the specified gridX
and gridY
coordinates
on the specified level
, if any, else null
public QuadTree.Node<V> findNode(PointD key)
QuadTree.Node
within the QuadTree
that should contain the specified key.
Does not check if the returned QuadTree.Node
actually contains key
.
Returns null
only if key
is outside of bounds
.
Performs a range search for key
, starting with the rootNode
.
This is usually an O(log m) operation where m is the number of nodes()
.
If nodes()
contains at least 4^PROBE_LEVEL
elements,
findNode
first probes a deeper level of the QuadTree
to
rapidly approach the QuadTree.Node
containing the specified key
.
The probe begins at level log4 m, where m is the number of nodes()
,
and ascends two levels at a time until either above PROBE_LEVEL
or
a valid QuadTree.Node
is found at the grid coordinates that contain key
.
findNode
then performs a regular tree search for the desired leaf node.
The depth probe is derived from a binary depth search algorithm given by Sariel Har-Peled in his lecture on 17 March 2010, QuadTrees – Hierarchical Grids. This lecture was part of the series Approximation Algorithms in Geometry, originally available here (but now apparently integrated into a published book).
key
- the PointD
key to findQuadTree.Node
whose QuadTree.Node.bounds
contain key
, if any, else null
java.lang.NullPointerException
- if key
is null
public QuadTree.Node<V> findNodeByValue(V value)
QuadTree.Node
within the QuadTree
that contains the specified value.
Iterates over all nodes()
and then over the QuadTree.Node.entries()
of each
QuadTree.Node
, until the specified value
is found, which may be null
.
This is an O(AbstractMap.size()
) operation.
This iteration sequence is arbitrary, so it is impossible to predict which
QuadTree.Node
will be returned if multiple nodes()
contain value
.
value
- the V value to findQuadTree.Node
whose QuadTree.Node.entries()
contain value
, if found, else null
public java.util.Map<PointD,V> findRange(PointD center, double radius)
QuadTree
whose keys lie within the specified circular range.
Immediately returns an empty map if the square circumscribed around the indicated
key range does not intersect with bounds
. Otherwise, performs a recursive
search starting with the rootNode
.
Depending on the size of the specified radius
relative to bounds
,
the runtime of this operation ranges from O(log m) to O(AbstractMap.size()
), where
m is the number of nodes()
.
center
- a PointD
indicating the center of the key range to searchradius
- the radius of the key range around center
to searchMap
containing all PointD
keys and associated V values
where the key lies within radius
around center
java.lang.IllegalArgumentException
- if radius
is less than zerojava.lang.NullPointerException
- if center
is null
public java.util.Map<PointD,V> findRange(RectD range)
QuadTree
whose keys lie within the specified rectangular range.
Immediately returns an empty map if the specified key range
does not
intersect with bounds
. Otherwise, performs a recursive search starting
with the rootNode
.
Depending on the size of range
relative to bounds
, the runtime
of this operation ranges from O(log m) to O(AbstractMap.size()
), where m is the number
of nodes()
.
public QuadTree.Node<V> move(PointD oldKey, PointD newKey, QuadTree.Node<V> node)
QuadTree
.
Has the same effect as calling remove(Object)
with oldKey
,
followed by put(PointD, Object)
with newKey
and the value
previously associated with oldKey
. However, move
introduces
two shortcuts to avoid the O(log m) tree search performed by each method,
where m is the number of nodes()
.
If node
is a valid leaf node that contains oldKey
, move
skips the first tree search for oldKey
. When moving multiple keys in close
proximity, always set node
to the previous move
result.
If oldKey
and newKey
both fall within the QuadTree.Node.bounds
of the same leaf node, move
skips the second tree search for newKey
and directly adjusts that leaf node’s QuadTree.Node.entries()
.
move
to an O(1) operation.oldKey
- the existing PointD
key of the entry to movenewKey
- the new PointD
key to replace oldKey
node
- an optional QuadTree.Node
to search for oldKey
before searching the entire QuadTree
QuadTree.Node
that contained oldKey
, or null
if that QuadTree.Node
was removed as the result of the movejava.lang.IllegalArgumentException
- if node
is not null
, and its
QuadTree.Node.owner()
differs from the QuadTree
, or if newKey
is outside bounds
or already exists in the QuadTree
java.util.NoSuchElementException
- if oldKey
does not exist in the QuadTree
java.lang.NullPointerException
- if oldKey
or newKey
is null
public java.util.Map<java.lang.Integer,QuadTree.Node<V>> nodes()
QuadTree.Node
instances in the QuadTree
.
Always contains at least one element with a QuadTree.Node.signature
of zero,
which is the permanent rootNode
of the QuadTree
.
Generally contains fewer than AbstractMap.size()
elements since leaf nodes may contain
up to capacity
entries, or more if they reside on MAX_LEVEL
.
Map
that maps QuadTree.Node.signature
values
to all corresponding QuadTree.Node
instances in the QuadTree
public void setProbeUseBitMask(boolean value)
findNode(PointD)
. See the source code for implementation details.value
- true
to use a bit mask, false
to use a looppublic boolean containsKey(java.lang.Object key)
QuadTree
contains the specified key.
Succeeds if findNode(PointD)
finds a QuadTree.Node
that contains the specified key
.containsKey
in interface java.util.Map<PointD,V>
containsKey
in class java.util.AbstractMap<PointD,V>
key
- the PointD
key to findtrue
if the QuadTree
contains key
, else false
java.lang.ClassCastException
- if key
cannot be cast to PointD
java.lang.NullPointerException
- if key
is null
public boolean containsValue(java.lang.Object value)
QuadTree
contains the specified value.
Succeeds if findNodeByValue(V)
finds a QuadTree.Node
that contains
the specified value
, which may be null
.containsValue
in interface java.util.Map<PointD,V>
containsValue
in class java.util.AbstractMap<PointD,V>
value
- the V value to findtrue
if the QuadTree
associates value
with at least one PointD
key, else false
java.lang.ClassCastException
- if value
cannot be cast to Vpublic java.util.Set<java.util.Map.Entry<PointD,V>> entrySet()
Set
view of all entries in the QuadTree
.
Returns a Set
view of all Entry
instances of PointD
keys and associated V values in the QuadTree
. The set is backed
by the QuadTree
, so changes to the QuadTree
are reflected
in the set, and vice-versa.
If the QuadTree
is structurally modified while an iteration over the set
is in progress, the results of the iteration are undefined. This implementation
does not support Iterator.remove()
on set iterators, but it does support
Set.add(E)
and Set.addAll(java.util.Collection<? extends E>)
on the set itself. The latter operations
will replace values for existing keys, returning true
if so.
public V get(java.lang.Object key)
QuadTree
.
Calls findNode(PointD)
to find the QuadTree.Node
that contains the
specified key
. Note that get
may return null
even
if key
is found, namely if its associated value is null
.get
in interface java.util.Map<PointD,V>
get
in class java.util.AbstractMap<PointD,V>
key
- the PointD
key whose V value to getkey
if found, else null
java.lang.ClassCastException
- if key
cannot be cast to PointD
java.lang.NullPointerException
- if key
is null
public V put(PointD key, V value)
QuadTree
.
Calls findNode(PointD)
to find the QuadTree.Node
for the specified
key
, but may then create one or more child nodes if key
is not already present. Any existing value associated with key
is overwritten and returned.
May return null
even if there was a previous value associated
with key
, namely if that value was itself null
.
put
in interface java.util.Map<PointD,V>
put
in class java.util.AbstractMap<PointD,V>
key
- the PointD
key of the entry to storevalue
- the V value of the entry to storekey
,
if already present, else null
java.lang.IllegalArgumentException
- if key
is outside of bounds
java.lang.NullPointerException
- if key
is null
public void putAll(java.util.Map<? extends PointD,? extends V> map)
Map
in the QuadTree
.
Iterates over the specified map
and calls put(org.kynosarges.tektosyne.geometry.PointD, V)
for each
PointD
key and associated V value. Note this means that any
values associated with existing keys will be overwritten.putAll
in interface java.util.Map<PointD,V>
putAll
in class java.util.AbstractMap<PointD,V>
map
- the Map
whose PointD
keys and V values to addjava.lang.IllegalArgumentException
- if map
contains any keys outside of bounds
java.lang.NullPointerException
- if map
or any of its keys is null
public V remove(java.lang.Object key)
QuadTree
.
Calls findNode(PointD)
to find the QuadTree.Node
that contains the specified
key
. Also removes the QuadTree.Node
itself, and possibly recursively its chain
of QuadTree.Node.parent
nodes, if removing key
leaves it empty.remove
in interface java.util.Map<PointD,V>
remove
in class java.util.AbstractMap<PointD,V>
key
- the PointD
key whose entry to removekey
,
or null
if key
was not foundjava.lang.ClassCastException
- if key
cannot be cast to PointD
java.lang.NullPointerException
- if key
is null
public boolean remove(java.lang.Object key, java.lang.Object value)
QuadTree
.
Calls findNode(PointD)
to find the QuadTree.Node
that contains the
specified key
. The entry is removed only if key
is currently
associated with the specified value
.
Also removes the QuadTree.Node
itself, and possibly recursively its chain of
QuadTree.Node.parent
nodes, if removing the specified entry leaves it empty.
key
- the PointD
key of the entry to removevalue
- the V value of the entry to removetrue
if key
and value
were found and removed, else false
java.lang.ClassCastException
- if key
cannot be cast to PointD
or value
cannot be cast to Vjava.lang.NullPointerException
- if key
is null
public V replace(PointD key, V value)
findNode(PointD)
to find the QuadTree.Node
that contains
the specified key
. The associated value is replaced with
value
only if an existing association was found.
May return null
even if there was a previous value associated
with key
, namely if that value was itself null
.
key
- the PointD
key whose value to replacevalue
- the new V value to associate with key
key
if found, else null
java.lang.NullPointerException
- if key
is null
public boolean replace(PointD key, V oldValue, V newValue)
findNode(PointD)
to find the QuadTree.Node
that contains
the specified key
. The associated value is replaced with
newValue
only if it currently equals oldValue
.key
- the PointD
key whose value to replaceoldValue
- the old V value associated with key
newValue
- the new V value to associate with key
true
if key
and oldValue
were found and
oldValue
replaced with newValue
, else false
java.lang.NullPointerException
- if key
is null