|
Define an adaptive k-d tree as per "The Design and Analysis of
Spatial Data Structures" pp. 70-71. Basically, given a set
of k-dimensional points (each dimension referred to as an
"attribute") with associated data, they are partitioned into
leaf nodes. Each leaf nodes hold lists of associated data
whose corresponding attributes vary by less than an initially-
supplied threshold (sepVal). Also, each leaf node holds a
bounding box of the leaf data.
The interior nodes of the tree contain details of the
partitioning. In particular, what attribute this node
partitions along (axis), and what value (median)
partitions left child node from right child node. Whether
a node is interior or leaf is stored in type.
|
Methods
|
|
__init__
bboxSearchTree
searchTree
|
|
|
__init__
|
__init__ (
self,
attributeData,
leafData,
sepVal,
)
attributeData is a sequence of sequences. Each individual
sequence is attribute data. For example, in a 3D space
partitioning, the attribute data is x, y, and z values.
leafData ia a sequence of the same length as attributeData.
Each item is what is to put into leaf nodes after tree
partitioning.
sepVal is the value at which a tree will no longer be
decomposed, i.e. if the maximum variance of each attribute
is less than sepVal, then a leaf node is created.
|
|
|
bboxSearchTree
|
bboxSearchTree ( self, bbox )
Search tree for all leaves within a bounding box.
Mostly similar to searchTree. bbox is a sequence of
lower-bound / upper-bound pairs defining the bounds on
each axis.
|
|
|
searchTree
|
searchTree (
self,
target,
window,
zero=0.0,
)
Search tree for all leaves within window of target.
The cumulative difference of all attributes from target must
be less than window.
Note that this search only identifies leaf nodes that could
satisfy the window criteria and returns all leaf data in
those nodes. Each individual leaf data may not satisfy the
window criteria.
For attributes that aren't floats or ints but that otherwise
obey numeric operations and comparisons, the zero parameter
may be specified so that the searches know how to initialize
their difference totals.
|
|