KdTree-0.2.1: 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

 Point Point3d

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

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

data Point3d Source

Constructors

 Point3d Fieldsp3x :: Double p3y :: Double p3z :: Double

Instances

 Eq Point3d Ord Point3d Show Point3d Arbitrary Point3d Point Point3d

data KdTree point Source

Constructors

 KdNode FieldskdLeft :: 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

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.