Copyright | (c) 2016 Martin Buck |
---|---|

License | see LICENSE |

Safe Haskell | None |

Language | Haskell2010 |

Containing the definition and functions for a quad tree

- data Positioned a => QuadTree a
- = QuadEmpty
- | QuadLeaf a
- | QuadBranch (QuadTree a) (QuadTree a) (QuadTree a) (QuadTree a) BoundingBox

- data QuadDir
- fmapQuad :: (Positioned a, Positioned b) => (a -> b) -> QuadTree a -> QuadTree b
- fmapQuadRebuild :: (Positioned a, Positioned b) => (a -> b) -> QuadTree a -> QuadTree b
- buildQuadTree :: Positioned a => [a] -> QuadTree a
- calcQuadDir :: Positioned a => a -> BoundingBox -> QuadDir
- nearestQuad :: (Positioned a, Positioned b) => a -> QuadTree b -> Maybe b
- quadTreeToList :: Positioned a => QuadTree a -> [a]

# Documentation

data Positioned a => QuadTree a Source #

A QuadTree for faster search queries

QuadEmpty | |

QuadLeaf a | |

QuadBranch (QuadTree a) (QuadTree a) (QuadTree a) (QuadTree a) BoundingBox |

Posibble directions within a branch (negative x && negative y | negative x && positive y ...)

fmapQuad :: (Positioned a, Positioned b) => (a -> b) -> QuadTree a -> QuadTree b Source #

Mapping function for the QuadTree. Do not use with functions which change the position of items, since they would invalidate the search structure (use fmapQuadRebuild instead)

fmapQuadRebuild :: (Positioned a, Positioned b) => (a -> b) -> QuadTree a -> QuadTree b Source #

Mapping function for the QuadTree. This rebuilds the entire tree, but allows the usage of position changing functions. Use this only for positioned changing functions, and fmapQuad otherwise, since it is faster

buildQuadTree :: Positioned a => [a] -> QuadTree a Source #

Builds a QuadTree from a list of elements with positions.

calcQuadDir :: Positioned a => a -> BoundingBox -> QuadDir Source #

Helper function to decide into which sub-node a position belongs

nearestQuad :: (Positioned a, Positioned b) => a -> QuadTree b -> Maybe b Source #

Finds the nearest within the tree to the search position (if there is any)

quadTreeToList :: Positioned a => QuadTree a -> [a] Source #

Puts the elements of a QuadTree into a list