Safe Haskell | Safe |
---|---|

Language | Haskell2010 |

- type PointAsListFn a p = p -> [a]
- type SquaredDistanceFn a p = p -> p -> a
- data KdTree a p
- empty :: Real a => PointAsListFn a p -> KdTree a p
- singleton :: Real a => PointAsListFn a p -> p -> KdTree a p
- emptyWithDist :: Real a => PointAsListFn a p -> SquaredDistanceFn a p -> KdTree a p
- singletonWithDist :: Real a => PointAsListFn a p -> SquaredDistanceFn a p -> p -> KdTree a p
- insert :: Real a => KdTree a p -> p -> KdTree a p
- nearest :: Real a => KdTree a p -> p -> p
- inRadius :: Real a => KdTree a p -> a -> p -> [p]
- kNearest :: Real a => KdTree a p -> Int -> p -> [p]
- inRange :: Real a => KdTree a p -> p -> p -> [p]
- toList :: KdTree a p -> [p]
- null :: KdTree a p -> Bool
- size :: KdTree a p -> Int
- defaultSqrDist :: Num a => PointAsListFn a p -> SquaredDistanceFn a p

# 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) >>>`nearest`

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) >>>`nearest`

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] Source

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 Source

Returns the squared distance between two points of type
`p`

with axis values of type `a`

.

A dynamic *k*-d tree structure that stores points of type `p`

with axis values of type `a`

.

## Dynamic *k*-d tree construction

empty :: Real a => PointAsListFn a p -> KdTree a p Source

Generates an empty `KdTree`

with the default distance function.

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

Generates a `KdTree`

with a single point using the default
distance function.

emptyWithDist :: Real a => PointAsListFn a p -> SquaredDistanceFn a p -> KdTree a p Source

Generates an empty `KdTree`

with a user-specified distance function.

singletonWithDist :: Real a => PointAsListFn a p -> SquaredDistanceFn a p -> p -> KdTree a p Source

Generates a `KdTree`

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

## Insertion

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

Adds a given point to a `KdTree`

.

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

## Query

kNearest :: Real a => KdTree a p -> Int -> p -> [p] Source

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.

:: 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.

toList :: KdTree a p -> [p] Source

Returns a list of all the points in the `KdTree`

.

Time complexity: *O(n)*

## Utilities

defaultSqrDist :: Num a => PointAsListFn a p -> SquaredDistanceFn a p Source

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

.