gloss-1.7.8.3: Painless 2D vector graphics, animations and simulations.

Safe Haskell | Safe-Inferred

Graphics.Gloss.Data.QuadTree

Description

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.

Synopsis

- data QuadTree a
  - = TNil
  - | TLeaf a
  - | TNode (QuadTree a) (QuadTree a) (QuadTree a) (QuadTree a)
- emptyTree :: QuadTree a
- emptyNode :: QuadTree a
- takeQuadOfTree :: Quad -> QuadTree a -> Maybe (QuadTree a)
- liftToQuad :: Quad -> (QuadTree a -> QuadTree a) -> QuadTree a -> QuadTree a
- insertByPath :: [Quad] -> a -> QuadTree a -> QuadTree a
- insertByCoord :: Extent -> Coord -> a -> QuadTree a -> Maybe (QuadTree a)
- lookupNodeByPath :: [Quad] -> QuadTree a -> Maybe (QuadTree a)
- lookupByPath :: [Quad] -> QuadTree a -> Maybe a
- lookupByCoord :: forall a. Extent -> Coord -> QuadTree a -> Maybe a
- flattenQuadTree :: forall a. Extent -> QuadTree a -> [(Coord, a)]
- flattenQuadTreeWithExtents :: forall a. Extent -> QuadTree a -> [(Extent, a)]

# Documentation

data QuadTree a Source

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

emptyTree :: QuadTree aSource

A `TNil` tree.

emptyNode :: QuadTree aSource

A node with `TNil`. for all its branches.

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

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 aSource

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 aSource

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

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

Lookup a node based on a path to it.

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

Lookup an element based given a path to it.

lookupByCoord Source

Arguments

:: forall a . |
=> 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 Source

Arguments

:: forall a . |
=> Extent | Extent that covers the whole tree.
-> QuadTree a |
-> [(Coord, a)] |

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

flattenQuadTreeWithExtents Source

Arguments

:: forall a . |
=> Extent | Extent that covers the whole tree.
-> QuadTree a |
-> [(Extent, a)] |

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