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

Data.Trees.KdTree

Synopsis

Documentation

class Point p whereSource

Methods

dimension :: p -> Int Source

dimension returns the number of coordinates of a point.

coord :: Int -> p -> Double Source

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

dist2 :: p -> p -> Double Source

dist2 returns the squared distance between two points.

Instances

compareDistance :: Point p => p -> p -> p -> Ordering Source

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

data Point3d Source

Constructors

Point3d
Fields p3x :: Double p3y :: Double p3z :: Double

Instances

Eq Point3d
Ord Point3d
Show Point3d
Arbitrary Point3d
Point Point3d

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

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

axisFromDepth :: Point p => p -> Int -> Int Source

toList :: KdTree p -> [p]Source

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

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

invariant :: Point p => KdTree p -> Bool Source

invariant tells whether the KD tree property holds for a given tree and all its subtrees. 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.

invariant' :: Point p => KdTree p -> Bool Source