data-spacepart-20090215.0: Deprecated. Now called "spacepart". Space partitioning data structures.

Data.SpacePart.QuadTree

Synopsis

Documentation

data QuadTree e whereSource

A 2D binary hierarchical space subdivision of a region. All elements contained in the quadtree are required to have a Boundary. This is an axis aligned box with congruent sides.

Each node of the quadtree is composed of:

  1. A list of elements who's shape can be queried for intersection with the quad. These are all the elements with a boundary that are fully enclosed by the boundary of this node but not fully enclosed by a quadrant of this node.
  2. The Boundary of this node.
  3. The child nodes of this node. Each is a quadrant of this nodes boundary.

Constructors

QuadTree :: HasBoundary e => [e] -> Boundary -> (Maybe (QuadTree e), Maybe (QuadTree e), Maybe (QuadTree e), Maybe (QuadTree e)) -> QuadTree e 

Instances

elements :: QuadTree e -> [e]Source

children :: QuadTree e -> (Maybe (QuadTree e), Maybe (QuadTree e), Maybe (QuadTree e), Maybe (QuadTree e))Source

data Quadrant Source

Constructors

NPQuad 
PPQuad 
NNQuad 
PNQuad 

Instances

map_child :: (Maybe (QuadTree e) -> Maybe (QuadTree e)) -> Quadrant -> (Maybe (QuadTree e), Maybe (QuadTree e), Maybe (QuadTree e), Maybe (QuadTree e)) -> (Maybe (QuadTree e), Maybe (QuadTree e), Maybe (QuadTree e), Maybe (QuadTree e))Source

empty :: HasBoundary e => QuadTree eSource

Returns an empty QuadTree without a specific boundary. The default bounds are centered around - (0,0) with a size of 2 - - TODO: Alternatively an empty quadtree could have no defined bounds. The bounds would then be - defined on the first insertion.

empty_with_bounds :: HasBoundary e => Boundary -> QuadTree eSource

Returns an empty QuadTree with the given bounds. - The given bounds cannot have a size of 0. This will error out on that case. - - TODO: The user may find it easier for this to accept a 0 sized boundary which is transparently - changed to a non-0 sized boundary on insert.

insert :: HasBoundary e => e -> QuadTree e -> QuadTree eSource

Inserts the given element into the quadtree. - This inserts the element into a this node or a child quadrant node if the current node encloses - the element. Otherwise this inserts the element into a new node that is a parent of the given - node.

insert_self_or_child :: HasBoundary e => e -> QuadTree e -> QuadTree eSource

Inserts the given element into either a child node of the current node if one of the quadrants - encloses the element. - Otherwise the element is added to the current node's list of elements.

quadrant_bounds :: QuadTree e -> [(Boundary, Quadrant)]Source

insert_via_parent :: HasBoundary e => e -> QuadTree e -> QuadTree eSource

Adds the element to quadtree via a parent node to the given quadtree. The parent to add e to is then the first of the possible parents nodes that enclose e.

insert_child :: HasBoundary e => (Boundary, Quadrant) -> e -> QuadTree e -> QuadTree eSource

parent_trees generates all possible parent trees of the given tree (Without memoization) in the order suitable for a breadth first search.

Inserts the element in the child identified by the given boundary and Quadrant. If there is no child at the given quadrant then a child is added and the element is inserted into the new child.

query :: HasBoundary e => Boundary -> QuadTree e -> [e]Source

Returns all elements with boundaries that intersect the given boundary - By case: - Boundary does not intersect quadtree - Boundary intersects the quadtree - All elements at the level of the quadtree could intersect the boundary. Test each element - for intersection. - Descend into the quadrants