hgeometry-0.12.0.1: Geometric Algorithms, Data structures, and Data types.
Copyright(C) Frank Staals
Licensesee the LICENSE file
MaintainerFrank Staals
Safe HaskellNone
LanguageHaskell2010

Data.Geometry.KDTree

Description

 
Synopsis

Documentation

newtype Coord (d :: Nat) Source #

Constructors

Coord 

Fields

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

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 #

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 #