Copyright	(C) Frank Staals
License	see the LICENSE file
Maintainer	Frank Staals
Safe Haskell	None
Language	Haskell2010

Data.Geometry.KDTree

Description

Synopsis

newtype Coord (d :: Nat) = Coord {
- unCoord :: Int
}
data Split d r = Split !(Coord d) !r !(Box d () r)
type Split' d r = SP (Coord d) r
newtype KDTree' d p r = KDT {
- unKDT :: BinLeafTree (Split d r) (Point d r :+ p)
}
data KDTree d p r
- = Empty
- | Tree (KDTree' d p r)
toMaybe :: KDTree d p r -> Maybe (KDTree' d p r)
buildKDTree :: (Arity d, 1 <= d, Ord r) => [Point d r :+ p] -> KDTree d p r
buildKDTree' :: (Arity d, 1 <= d, Ord r) => NonEmpty (Point d r :+ p) -> KDTree' d p r
ordNub :: Ord a => NonEmpty a -> NonEmpty a
toPointSet :: (Arity d, Ord r) => LSeq n (Point d r :+ p) -> PointSet (LSeq n) d p r
compareOn :: (Ord r, Arity d) => Int -> (Point d r :+ e) -> (Point d r :+ e) -> Ordering
build :: (1 <= d, Arity d, Ord r) => Coord d -> PointSet (LSeq 1) d p r -> BinLeafTree (Split' d r) (Point d r :+ p)
reportSubTree :: KDTree' d p r -> NonEmpty (Point d r :+ p)
searchKDTree :: (Arity d, Ord r) => Box d q r -> KDTree d p r -> [Point d r :+ p]
searchKDTree' :: (Arity d, Ord r) => Box d q r -> KDTree' d p r -> [Point d r :+ p]
boxOf :: (Arity d, Ord r) => BinLeafTree (Split d r) (Point d r :+ p) -> Box d () r
containedIn :: (Arity d, Ord r) => Box d q r -> Box d p r -> Bool
type PointSet seq d p r = Vector d (seq (Point d r :+ p))
splitOn :: (Arity d, KnownNat d, Ord r) => Coord d -> PointSet (LSeq 2) d p r -> (PointSet (LSeq 1) d p r, Split' d r, PointSet (LSeq 1) d p r)
asSingleton :: (1 <= d, Arity d) => PointSet (LSeq 1) d p r -> Either (Point d r :+ p) (PointSet (LSeq 2) d p r)

Documentation

newtype Coord (d :: Nat) Source #

Constructors

Coord
Fields unCoord :: Int

Instances

Instances details

KnownNat d => Enum (Coord d) Source #
Instance details Defined in Data.Geometry.KDTree Methods succ :: Coord d -> Coord d # pred :: Coord d -> Coord d # toEnum :: Int -> Coord d # fromEnum :: Coord d -> Int # enumFrom :: Coord d -> [Coord d] # enumFromThen :: Coord d -> Coord d -> [Coord d] # enumFromTo :: Coord d -> Coord d -> [Coord d] # enumFromThenTo :: Coord d -> Coord d -> Coord d -> [Coord d] #
KnownNat d => Eq (Coord d) Source #
Instance details Defined in Data.Geometry.KDTree Methods (==) :: Coord d -> Coord d -> Bool # (/=) :: Coord d -> Coord d -> Bool #
KnownNat d => Show (Coord d) Source #
Instance details Defined in Data.Geometry.KDTree Methods showsPrec :: Int -> Coord d -> ShowS # show :: Coord d -> String # showList :: [Coord d] -> ShowS #

data Split d r Source #

Constructors

Split !(Coord d) !r !(Box d () r)

Instances

Instances details

(Eq r, Arity d, KnownNat d) => Eq (Split d r) Source #
Instance details Defined in Data.Geometry.KDTree Methods (==) :: Split d r -> Split d r -> Bool # (/=) :: Split d r -> Split d r -> Bool #
(Show r, Arity d, KnownNat d) => Show (Split d r) Source #
Instance details Defined in Data.Geometry.KDTree Methods showsPrec :: Int -> Split d r -> ShowS # show :: Split d r -> String # showList :: [Split d r] -> ShowS #

type Split' d r = SP (Coord d) r Source #

newtype KDTree' d p r Source #

Constructors

KDT
Fields unKDT :: BinLeafTree (Split d r) (Point d r :+ p)

Instances

Instances details

(Eq p, Eq r, Arity d, KnownNat d) => Eq (KDTree' d p r) Source #
Instance details Defined in Data.Geometry.KDTree Methods (==) :: KDTree' d p r -> KDTree' d p r -> Bool # (/=) :: KDTree' d p r -> KDTree' d p r -> Bool #
(Show p, Show r, Arity d, KnownNat d) => Show (KDTree' d p r) Source #
Instance details Defined in Data.Geometry.KDTree Methods showsPrec :: Int -> KDTree' d p r -> ShowS # show :: KDTree' d p r -> String # showList :: [KDTree' d p r] -> ShowS #

data KDTree d p r Source #

Constructors

Empty
Tree (KDTree' d p r)

Instances

Instances details

(Eq p, Eq r, Arity d, KnownNat d) => Eq (KDTree d p r) Source #
Instance details Defined in Data.Geometry.KDTree Methods (==) :: KDTree d p r -> KDTree d p r -> Bool # (/=) :: KDTree d p r -> KDTree d p r -> Bool #
(Show p, Show r, Arity d, KnownNat d) => Show (KDTree d p r) Source #
Instance details Defined in Data.Geometry.KDTree Methods showsPrec :: Int -> KDTree d p r -> ShowS # show :: KDTree d p r -> String # showList :: [KDTree d p r] -> ShowS #

toMaybe :: KDTree d p r -> Maybe (KDTree' d p r) Source #

buildKDTree :: (Arity d, 1 <= d, Ord r) => [Point d r :+ p] -> KDTree d p r Source #

Expects the input to be a set, i.e. no duplicates

running time: \(O(n \log n)\)

buildKDTree' :: (Arity d, 1 <= d, Ord r) => NonEmpty (Point d r :+ p) -> KDTree' d p r Source #

ordNub :: Ord a => NonEmpty a -> NonEmpty a Source #

Nub by sorting first

toPointSet :: (Arity d, Ord r) => LSeq n (Point d r :+ p) -> PointSet (LSeq n) d p r Source #

compareOn :: (Ord r, Arity d) => Int -> (Point d r :+ e) -> (Point d r :+ e) -> Ordering Source #

build :: (1 <= d, Arity d, Ord r) => Coord d -> PointSet (LSeq 1) d p r -> BinLeafTree (Split' d r) (Point d r :+ p) Source #

reportSubTree :: KDTree' d p r -> NonEmpty (Point d r :+ p) Source #

searchKDTree :: (Arity d, Ord r) => Box d q r -> KDTree d p r -> [Point d r :+ p] Source #

Searches in a KDTree

running time: \(O(n^{(d-1)/d} + k)\)

searchKDTree' :: (Arity d, Ord r) => Box d q r -> KDTree' d p r -> [Point d r :+ p] Source #

boxOf :: (Arity d, Ord r) => BinLeafTree (Split d r) (Point d r :+ p) -> Box d () r Source #

containedIn :: (Arity d, Ord r) => Box d q r -> Box d p r -> Bool Source #

type PointSet seq d p r = Vector d (seq (Point d r :+ p)) Source #

splitOn :: (Arity d, KnownNat d, Ord r) => Coord d -> PointSet (LSeq 2) d p r -> (PointSet (LSeq 1) d p r, Split' d r, PointSet (LSeq 1) d p r) Source #

running time: \(O(n)\)

asSingleton :: (1 <= d, Arity d) => PointSet (LSeq 1) d p r -> Either (Point d r :+ p) (PointSet (LSeq 2) d p r) Source #