Documentation
¶
Overview ¶
kdtree is a two dimensional kd-tree implementation
Index ¶
Constants ¶
This section is empty.
Variables ¶
var ErrDuplicateNode = errors.New("duplicate node")
Functions ¶
Types ¶
type DistanceFunc ¶
DistanceFunc specifies how to calculate the distance from a point to the extent.
In most cases the default EuclideanDistance function will do just fine.
type KdNode ¶
type KdNode struct {
// contains filtered or unexported fields
}
KdNode structure contains the nodes within the tree. Both leaf and non-leaf nodes store the point data.
If a node has a nil left & right child it is a leaf node.
func (*KdNode) MarshalJSON ¶
MarshalJSON is the marshalling function for JSON.
type KdTree ¶
type KdTree struct {
// contains filtered or unexported fields
}
KdTree is an index for 2 dimensional point data.
Limitations:
- Bulk inserts and balancing are not supported. If you have a large amount of data to insert it is best to randomize the data before inserting.
- Duplicate points are not supported and will return an error.
See the *_iterator.go files for how to query data out of the kd-tree.
type NearestNeighborIterator ¶
type NearestNeighborIterator struct {
// contains filtered or unexported fields
}
func NewNearestNeighborIterator ¶
func NewNearestNeighborIterator(p geom.Pointer, kdTree *KdTree, df DistanceFunc) *NearestNeighborIterator
NewNearestNeighborIterator creates an iterator that returns the neighboring points in descending order. Retrieving all the results will occur in O(n log(n)) time. Results are calculated in a lazy fashion so retrieving the nearest point or the nearest handful should still be quite efficient.
Algorithm:
- Initialize by calculating the distance from the source point to the root node and the root node's bounding box. Push both these values onto their respective heaps (nodeHeap & bboxHeap)
- While there is still data to return:
- If the distance on the top of the nodeHeap is < the distance on the top of bboxHeap we know that node is closer than all the remaining nodes and can be returned to the user.
- Otherwise, the node might not be closest, so pop of the next bounding box and push its children onto the nodeHeap.
The iterator design here was taken from: https://ewencp.org/blog/golang-iterators/index.html
To use this iterator:
nnit := NewNearestNeighborIterator(geom.Point{0,0}, myKdTree, EuclideanDistance)
for nnit.Next() {
n, d := nnit.Value()
// do stuff
}
func (*NearestNeighborIterator) Next ¶
func (nni *NearestNeighborIterator) Next() bool
Next iterates to the next nearest neighbor. True is returned if there is another nearest neighbor, otherwise false is returned.
Source Files