Safe Haskell | None |
---|---|
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
.