Graphics.Gloss.Data.QuadTree

A QuadTree can be used to recursively divide up 2D space into quadrants. The smallest division corresponds to an unit Extent, so the total depth of the tree will depend on what sized Extent you start with.

Documentation

data QuadTree a

The quad tree structure.

Constructors

TNil

An empty node.

TLeaf a

A leaf containint some value.

TNode (QuadTree a) (QuadTree a) (QuadTree a) (QuadTree a)

A node with four children.

Instances

Show a => Show (QuadTree a)

Methods

showsPrec :: Int -> QuadTree a -> ShowS

show :: QuadTree a -> String

showList :: [QuadTree a] -> ShowS

emptyTree :: QuadTree a

A TNil tree.

emptyNode :: QuadTree a

A node with TNil. for all its branches.

takeQuadOfTree :: Quad -> QuadTree a -> Maybe (QuadTree a)

Get a quadrant from a node. If the tree does not have an outer node then Nothing.

liftToQuad :: Quad -> (QuadTree a -> QuadTree a) -> QuadTree a -> QuadTree a

Apply a function to a quadrant of a node. If the tree does not have an outer node then return the original tree.

insertByPath :: [Quad] -> a -> QuadTree a -> QuadTree a

Insert a value into the tree at the position given by a path. If the path intersects an existing TLeaf then return the original tree.

insertByCoord :: Extent -> Coord -> a -> QuadTree a -> Maybe (QuadTree a)

Insert a value into the node containing this coordinate. The node is created at maximum depth, corresponding to an unit Extent.

lookupNodeByPath :: [Quad] -> QuadTree a -> Maybe (QuadTree a)

Lookup a node based on a path to it.

lookupByPath :: [Quad] -> QuadTree a -> Maybe a

Lookup an element based given a path to it.

lookupByCoord

Arguments

:: Extent

Extent that covers the whole tree.

-> Coord

Coordinate of the value of interest.

-> QuadTree a

-> Maybe a

Lookup a node if a tree given a coordinate which it contains.

flattenQuadTree

Arguments

:: Extent

Extent that covers the whole tree.

-> QuadTree a

-> [(Coord, a)]

Flatten a QuadTree into a list of its contained values, with coordinates.

flattenQuadTreeWithExtents

Arguments

:: Extent

Extent that covers the whole tree.

-> QuadTree a

-> [(Extent, a)]

Flatten a QuadTree into a list of its contained values, with coordinates.