hgeometry-0.12.0.4: Geometric Algorithms, Data structures, and Data types.

Algorithms.Geometry.WSPD

Description

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

Synopsis

Documentation

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

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] Source #

Given a split tree, generate the Well separated pairs

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

data NodeData d r a Source #

Data that we store in the split tree

Constructors

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

Instances

Instances details
 Semigroup v => Measured v (NodeData d r v) Source # Instance detailsDefined in Algorithms.Geometry.WSPD.Types Methodsmeasure :: NodeData d r v -> v # Functor (NodeData d r) Source # Instance detailsDefined in Algorithms.Geometry.WSPD.Types Methodsfmap :: (a -> b) -> NodeData d r a -> NodeData d r b #(<\$) :: a -> NodeData d r b -> NodeData d r a # Foldable (NodeData d r) Source # Instance detailsDefined in Algorithms.Geometry.WSPD.Types Methodsfold :: 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) Source # Instance detailsDefined in Algorithms.Geometry.WSPD.Types Methodstraverse :: 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) Source # Instance detailsDefined 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) Source # Instance detailsDefined in Algorithms.Geometry.WSPD.Types MethodsshowsPrec :: 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) Source #

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

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

data Level Source #

Constructors

 Level Fields_unLevel :: Int _widestDim :: Maybe Int

Instances

Instances details
 Source # Instance detailsDefined in Algorithms.Geometry.WSPD.Types Methods(==) :: Level -> Level -> Bool #(/=) :: Level -> Level -> Bool # Source # Instance detailsDefined in Algorithms.Geometry.WSPD.Types Methods(<) :: Level -> Level -> Bool #(<=) :: Level -> Level -> Bool #(>) :: Level -> Level -> Bool #(>=) :: Level -> Level -> Bool #max :: Level -> Level -> Level #min :: Level -> Level -> Level # Source # Instance detailsDefined in Algorithms.Geometry.WSPD.Types MethodsshowsPrec :: 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) Source #

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)) Source #

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

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