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

Data.Trees.KdTree

Synopsis

Documentation

class Point p whereSource

Methods

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.

Instances

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

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

data KdTree point Source

Constructors

KdNode 

Fields

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

Instances

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

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.

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.