Data.KdTree.Dynamic

Usage

The KdTree is a dynamic variant of Data.KdTree.Static.KdTree that allows for insertion of new points into an existing KdTree. This algorithm was implemented using a static-to-dynamic transformation.

Here's an example of interleaving 3D point insertions and point queries using KdTree:

>>> let dkdt = singleton point3dAsList (Point3D 0.0 0.0 0.0)

>>> let dkdt' = insert dkdt (Point3D 1.0 1.0 1.0)

>>> nearestNeighbor dkdt' (Point3D 0.4 0.4 0.4)
Point3D {x = 0.0, y = 0.0, z = 0.0}

>>> let dkdt'' = insert dkdt' (Point3D 0.5 0.5 0.5)

>>> nearestNeighbor dkdt'' (Point3D 0.4 0.4 0.4)
Point3D {x = 0.5, y = 0.5, z = 0.5}

Check out Data.KdMap.Dynamic.KdMap if you want to associate a value with each point in your tree structure.

Reference

Types

type PointAsListFn a p = p -> [a]

Converts a point of type p with axis values of type a into a list of axis values [a].

type SquaredDistanceFn a p = p -> p -> a

Returns the squared distance between two points of type p with axis values of type a.

data KdTree a p

A dynamic k-d tree structure that stores points of type p with axis values of type a.

Instances

Foldable (KdTree a)

Dynamic k-d tree construction

emptyKdTree :: Real a => PointAsListFn a p -> KdTree a p

Generates an empty KdTree with the default distance function.

singleton :: Real a => PointAsListFn a p -> p -> KdTree a p

Generates a KdTree with a single point using the default distance function.

emptyKdTreeWithDistFn :: Real a => PointAsListFn a p -> SquaredDistanceFn a p -> KdTree a p

Generates an empty KdTree with a user-specified distance function.

singletonWithDistFn :: Real a => PointAsListFn a p -> SquaredDistanceFn a p -> p -> KdTree a p

Generates a KdTree with a single point using a user-specified distance function.

Insertion

insert :: Real a => KdTree a p -> p -> KdTree a p

Adds a given point to a KdTree.

Average time complexity per insert for n inserts: O(log^2(n)).

Query

nearestNeighbor :: Real a => KdTree a p -> p -> p

Given a KdTree and a query point, returns the nearest point in the KdTree to the query point.

Average time complexity: O(log^2(n)).

pointsInRadius :: Real a => KdTree a p -> a -> p -> [p]

Given a KdTree, a query point, and a radius, returns all points in the KdTree that are within the given radius of the query points.

Points are not returned in any particular order.

Worst case time complexity: O(n) for n data points.

kNearestNeighbors :: Real a => KdTree a p -> Int -> p -> [p]

Given a KdTree, a query point, and a number k, returns the k nearest points in the KdTree to the query point.

Neighbors are returned in order of increasing distance from query point.

Average time complexity: log(k) * log^2(n) for k nearest neighbors on a structure with n data points.

Worst case time complexity: n * log(k) for k nearest neighbors on a structure with n data points.

pointsInRange

Arguments

:: Real a

=> KdTree a p

-> p

lower bounds of range

-> p

upper bounds of range

-> [p]

all points within given range

Finds all points in a KdTree with points within a given range, where the range is specified as a set of lower and upper bounds.

Points are not returned in any particular order.

Worst case time complexity: O(n) for n data points and a range that spans all the points.

points :: KdTree a p -> [p]

Returns a list of all the points in the KdTree.

Time complexity: O(n)

null :: KdTree a p -> Bool

Returns whether the KdTree is empty.

size :: KdTree a p -> Int

Returns the number of elements in the KdTree.

Time complexity: O(1)

Utilities

defaultDistSqrFn :: Num a => PointAsListFn a p -> SquaredDistanceFn a p

A default implementation of squared distance given two points and a PointAsListFn.