Data.Geometry.KDTree

Documentation

newtype Coord (d :: Nat)

Constructors

Coord

Fields

• unCoord :: Int

Instances

KnownNat d => Enum (Coord d)

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)

Defined in Data.Geometry.KDTree

Methods

(==) :: Coord d -> Coord d -> Bool

(/=) :: Coord d -> Coord d -> Bool

KnownNat d => Show (Coord d)

Defined in Data.Geometry.KDTree

Methods

showsPrec :: Int -> Coord d -> ShowS

show :: Coord d -> String

showList :: [Coord d] -> ShowS

data Split d r

Constructors

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

Instances

(Eq r, Arity d, KnownNat d) => Eq (Split d r)

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)

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

newtype KDTree' d p r

Constructors

KDT

Fields

• unKDT :: BinLeafTree (Split d r) (Point d r :+ p)

Instances

(Eq p, Eq r, Arity d, KnownNat d) => Eq (KDTree' d p r)

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)

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

Constructors

Empty

Tree (KDTree' d p r)

Instances

(Eq p, Eq r, Arity d, KnownNat d) => Eq (KDTree d p r)

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)

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)

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

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

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

Nub by sorting first

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]

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]

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)

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)