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

Description

Synopsis

# Documentation

data QuadTree v p r Source #

Constructors

 QuadTree Fields_startingCell :: !(Cell r) _tree :: !(Tree v p)

#### Instances

Instances details

tree :: forall v p r v p. Lens (QuadTree v p r) (QuadTree v p r) (Tree v p) (Tree v p) Source #

startingCell :: forall v p r r. Lens (QuadTree v p r) (QuadTree v p r) (Cell r) (Cell r) Source #

# Functions operating on the QuadTree (in terms of the Tree type)

withCells :: (Fractional r, Ord r) => QuadTree v p r -> QuadTree (v :+ Cell r) (p :+ Cell r) r Source #

withCellsTree :: (Fractional r, Ord r) => QuadTree v p r -> Tree (v :+ Cell r) (p :+ Cell r) Source #

buildOn :: Cell r -> (Cell r -> i -> Tree v p) -> i -> QuadTree v p r Source #

Given a starting cell, a Tree builder, and some input required by the builder, constructs a quadTree.

build :: (Fractional r, Ord r) => (Cell r -> i -> Split i v p) -> Cell r -> i -> QuadTree v p r Source #

The Equivalent of Tree.build for constructing a QuadTree

fromPointsBox :: (Fractional r, Ord r) => Cell r -> [Point 2 r :+ p] -> QuadTree () (Maybe (Point 2 r :+ p)) r Source #

Build a QuadtTree from a set of points.

pre: the points lie inside the initial given cell.

running time: $$O(nh)$$, where $$n$$ is the number of points and $$h$$ is the height of the resulting quadTree.

fromPoints :: (RealFrac r, Ord r) => NonEmpty (Point 2 r :+ p) -> QuadTree () (Maybe (Point 2 r :+ p)) r Source #

findLeaf :: (Fractional r, Ord r) => Point 2 r -> QuadTree v p r -> Maybe (p :+ Cell r) Source #

Locates the cell containing the given point, if it exists.

running time: $$O(h)$$, where $$h$$ is the height of the quadTree

fromZeros :: (Fractional r, Ord r, Num a, Eq a, v ~ Quadrants Sign) => Cell r -> (Point 2 r -> a) -> QuadTree v (Either v Sign) r Source #

type Signs sign = Either (Corners sign) sign Source #

fromZerosWith' :: (Eq sign, Fractional r, Ord r) => Limiter r (Corners sign) (Corners sign) sign -> Cell r -> (Point 2 r -> sign) -> QuadTree (Quadrants sign) (Signs sign) r Source #

data Sign Source #

Constructors

 Negative Zero Positive

#### Instances

Instances details
 Source # Instance detailsDefined in Data.Geometry.QuadTree Methods(==) :: Sign -> Sign -> Bool #(/=) :: Sign -> Sign -> Bool # Source # Instance detailsDefined in Data.Geometry.QuadTree Methodscompare :: Sign -> Sign -> Ordering #(<) :: Sign -> Sign -> Bool #(<=) :: Sign -> Sign -> Bool #(>) :: Sign -> Sign -> Bool #(>=) :: Sign -> Sign -> Bool #max :: Sign -> Sign -> Sign #min :: Sign -> Sign -> Sign # Source # Instance detailsDefined in Data.Geometry.QuadTree MethodsshowsPrec :: Int -> Sign -> ShowS #show :: Sign -> String #showList :: [Sign] -> ShowS #

Interpret an ordering result as a Sign

fromSignum :: (Num a, Eq a) => (b -> a) -> b -> Sign Source #

Arguments

 :: forall r sign. (Fractional r, Eq sign) => (Point 2 r -> sign) The function we are evaluating -> Splitter r (Quadrants sign) (Quadrants sign) sign

Splitter that determines if we should split a cell based on the sign of the corners.

Arguments

 :: Eq sign => sign the zero value -> Either v sign -> Bool

completeTree :: (Fractional r, Ord r) => Cell r -> QuadTree () () r Source #

Constructs an empty/complete tree from the starting width