Defines the K-dimensional Tree and the optimized TwoDTree variation.

KD tree

A KD tree is a space-partitioning data structure to represent a collection of k-dimensional points. The structure offers efficient implementations of the following operations: To provide optimal behavior the KD trees should be balanced, however there is no efficient means to rebalance trees. In fact, the KD tree implementation provided here offers no ability to remove an IMultiPoint once it has been inserted (you can remove all IMultiPoint objects in the tree using the removeAll method). If you choose to dynamically add IMultiPoint objects to the tree, then the standard approach (much like hash tables in fact) to rebalance the tree is to remove all IMultiPoints and insert them in an order that ensures the resulting KD tree is balanced. The KDFactory class offers a static method public static synchronized KDTree generate (IMultiPoint []points) to generate a balanced KD tree using an algorithm that recursively locates medians and inserts the points "above" and "below" the median nodes as needed. The TwoDFactory class offers the same functionality for TwoDTree.

References

Bentley, J. L., Multidimensional binary search trees used for associative searching, Communications ACM 18(9), Sep. 1975, 509–517.