Algorithms.Geometry.WSPD

Algorithm to construct a well separated pair decomposition (wspd).

Documentation

fairSplitTree :: (Fractional r, Ord r, Arity d, 1 <= d, Show r, Show p) => NonEmpty (Point d r :+ p) -> SplitTree d p r ()

Construct a split tree

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

wellSeparatedPairs :: (Floating r, Ord r, Arity d, Arity (d + 1)) => r -> SplitTree d p r a -> [WSP d p r a]

Given a split tree, generate the Well separated pairs

running time: \(O(s^d n)\)

data NodeData d r a

Data that we store in the split tree

Constructors

NodeData !Int !(Box d () r) !a

Instances

Semigroup v => Measured v (NodeData d r v)

Defined in Algorithms.Geometry.WSPD.Types

Methods

measure :: NodeData d r v -> v

Functor (NodeData d r)

Defined in Algorithms.Geometry.WSPD.Types

Methods

fmap :: (a -> b) -> NodeData d r a -> NodeData d r b

(<$) :: a -> NodeData d r b -> NodeData d r a

Foldable (NodeData d r)

Defined in Algorithms.Geometry.WSPD.Types

Methods

fold :: Monoid m => NodeData d r m -> m

foldMap :: Monoid m => (a -> m) -> NodeData d r a -> m

foldMap' :: Monoid m => (a -> m) -> NodeData d r a -> m

foldr :: (a -> b -> b) -> b -> NodeData d r a -> b

foldr' :: (a -> b -> b) -> b -> NodeData d r a -> b

foldl :: (b -> a -> b) -> b -> NodeData d r a -> b

foldl' :: (b -> a -> b) -> b -> NodeData d r a -> b

foldr1 :: (a -> a -> a) -> NodeData d r a -> a

foldl1 :: (a -> a -> a) -> NodeData d r a -> a

toList :: NodeData d r a -> [a]

null :: NodeData d r a -> Bool

length :: NodeData d r a -> Int

elem :: Eq a => a -> NodeData d r a -> Bool

maximum :: Ord a => NodeData d r a -> a

minimum :: Ord a => NodeData d r a -> a

sum :: Num a => NodeData d r a -> a

product :: Num a => NodeData d r a -> a

Traversable (NodeData d r)

Defined in Algorithms.Geometry.WSPD.Types

Methods

traverse :: Applicative f => (a -> f b) -> NodeData d r a -> f (NodeData d r b)

sequenceA :: Applicative f => NodeData d r (f a) -> f (NodeData d r a)

mapM :: Monad m => (a -> m b) -> NodeData d r a -> m (NodeData d r b)

sequence :: Monad m => NodeData d r (m a) -> m (NodeData d r a)

(Arity d, Eq r, Eq a) => Eq (NodeData d r a)

Defined in Algorithms.Geometry.WSPD.Types

Methods

(==) :: NodeData d r a -> NodeData d r a -> Bool

(/=) :: NodeData d r a -> NodeData d r a -> Bool

(Arity d, Show r, Show a) => Show (NodeData d r a)

Defined in Algorithms.Geometry.WSPD.Types

Methods

showsPrec :: Int -> NodeData d r a -> ShowS

show :: NodeData d r a -> String

showList :: [NodeData d r a] -> ShowS

type WSP d p r a = (PointSet d p r a, PointSet d p r a)

type SplitTree d p r a = BinLeafTree (NodeData d r a) (Point d r :+ p)

nodeData :: forall d r a a. Lens (NodeData d r a) (NodeData d r a) a a

data Level

Constructors

Level

Fields

• _unLevel :: Int
• _widestDim :: Maybe Int

Instances

Eq Level

Defined in Algorithms.Geometry.WSPD.Types

Methods

(==) :: Level -> Level -> Bool

(/=) :: Level -> Level -> Bool

Ord Level

Defined in Algorithms.Geometry.WSPD.Types

Methods

compare :: Level -> Level -> Ordering

(<) :: Level -> Level -> Bool

(<=) :: Level -> Level -> Bool

(>) :: Level -> Level -> Bool

(>=) :: Level -> Level -> Bool

max :: Level -> Level -> Level

min :: Level -> Level -> Level

Show Level

Defined in Algorithms.Geometry.WSPD.Types

Methods

showsPrec :: Int -> Level -> ShowS

show :: Level -> String

showList :: [Level] -> ShowS

reIndexPoints :: (Arity d, 1 <= d) => Vector d (PointSeq d (Idx :+ p) r) -> Vector d (PointSeq d (Idx :+ p) r)

Given a sequence of points, whose index is increasing in the first dimension, i.e. if idx p < idx q, then p[0] < q[0]. Reindex the points so that they again have an index in the range [0,..,n'], where n' is the new number of points.

running time: O(n' * d) (more or less; we are actually using an intmap for the lookups)

alternatively: I can unsafe freeze and thaw an existing vector to pass it along to use as mapping. Except then I would have to force the evaluation order, i.e. we cannot be in reIndexPoints for two of the nodes at the same time.

so, basically, run reIndex points in ST as well.

distributePoints :: (Arity d, Show r, Show p) => Int -> Vector (Maybe Level) -> Vector d (PointSeq d (Idx :+ p) r) -> Vector (Vector d (PointSeq d (Idx :+ p) r))

Assign the points to their the correct class. The Nothing class is considered the last class

distributePoints'

Arguments

:: Int

number of classes

-> Vector (Maybe Level)

level assignment

-> PointSeq d (Idx :+ p) r

input points

-> Vector (PointSeq d (Idx :+ p) r)

Assign the points to their the correct class. The Nothing class is considered the last class