Documentation

Overview

kdtree is a two dimensional kd-tree implementation

Index

Constants

This section is empty.

Variables

View Source
var ErrDuplicateNode = errors.New("duplicate node")

Functions

func EuclideanDistance

func EuclideanDistance(p geom.Pointer, e *geom.Extent) float64

Types

type DistanceFunc

type DistanceFunc func(p geom.Pointer, e *geom.Extent) float64

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 NewKdNode

func NewKdNode(p geom.Pointer) *KdNode

NewKdNode creates a new node with a properly initialized bbox.

func (*KdNode) Left

func (node *KdNode) Left() *KdNode

Left is the node's left child

func (*KdNode) MarshalJSON

func (node *KdNode) MarshalJSON() ([]byte, error)

MarshalJSON is the marshalling function for JSON.

func (*KdNode) P

func (node *KdNode) P() geom.Pointer

P returns the associated point geometry.

func (*KdNode) Right

func (node *KdNode) Right() *KdNode

Right is the node's right child.

func (*KdNode) SetLeft

func (node *KdNode) SetLeft(left *KdNode)

SetLeft sets the left child.

func (*KdNode) SetRight

func (node *KdNode) SetRight(right *KdNode)

SetRight sets the right child.

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.

func (*KdTree) Insert

func (kdt *KdTree) Insert(p geom.Pointer) (*KdNode, error)

Insert the specified geometry into the kd-tree.

If a duplicate point is inserted, the currently indexed point will be returned along with an error.

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.

func (*NearestNeighborIterator) Value

func (nni *NearestNeighborIterator) Value() (geom.Pointer, float64)

Value returns the geometry pointer and distance for the current neighbor.