KdTree-0.2.1: KdTree, for efficient search in K-dimensional point clouds.




class Point p whereSource


dimension :: p -> IntSource

dimension returns the number of coordinates of a point.

coord :: Int -> p -> DoubleSource

coord gets the k'th coordinate, starting from 0.

dist2 :: p -> p -> DoubleSource

dist2 returns the squared distance between two points.


compareDistance :: Point p => p -> p -> p -> OrderingSource

compareDistance p a b compares the distances of a and b to p.

data KdTree point Source




kdLeft :: KdTree point
kdPoint :: point
kdRight :: KdTree point
kdAxis :: Int


Functor KdTree 
Foldable KdTree 
Eq point => Eq (KdTree point) 
Ord point => Ord (KdTree point) 
Show point => Show (KdTree point) 

fromList :: Point p => [p] -> KdTree pSource

fromListWithDepth :: Point p => [p] -> Int -> KdTree pSource

fromListWithDepth selects an axis based on depth so that the axis cycles through all valid values.

toList :: KdTree p -> [p]Source

subtrees :: KdTree p -> [KdTree p]Source

subtrees t returns a list containing t and all its subtrees, including the empty leaf nodes.

nearestNeighbor :: Point p => KdTree p -> p -> Maybe pSource

nearestNeighbor tree p returns the nearest neighbor of p in tree.

nearNeighbors :: Point p => KdTree p -> Double -> p -> [p]Source

nearNeighbors tree p returns all neighbors within distance r from p in tree.

isValid :: Point p => KdTree p -> BoolSource

isValid tells whether the K-D tree property holds for a given tree. Specifically, it tests that all points in the left subtree lie to the left of the plane, p is on the plane, and all points in the right subtree lie to the right.

allSubtreesAreValid :: Point p => KdTree p -> BoolSource

allSubtreesAreValid tells whether the K-D tree property holds for the given tree and all subtrees.

kNearestNeighbors :: (Eq p, Point p) => KdTree p -> Int -> p -> [p]Source

kNearestNeighbors tree k p returns the k closest points to p within tree.

remove :: (Eq p, Point p) => KdTree p -> p -> KdTree pSource

remove t p removes the point p from t.