Space partition data structures. Currently only a QuadTree.

Latest on Hackage:

This package is not currently in any snapshots. If you're interested in using it, we recommend adding it to Stackage Nightly. Doing so will make builds more reliable, and allow to host generated Haddocks.

BSD3 licensed and maintained by Corey O'Connor
This library is still in the early stages. Expect the interface to change.

- rename Boundary data type
- rename HasBoundary type class.
- query should accept any suitable region.
- At least any axis aligned boxes not just square ones
- partition query into two forms:
- inclusive: Any element with bounds entirely within or partially the query bounds.
- exclusive: Any element with bounds entirely within the query bounds.
- Improve verification tests
- Test for proper distribution of inserted elements to nodes.
- Improve visualization tool
- interactive querying
- interactive insert
- remove FBO dependency.

- The following element_bounds_query_is_element_prop instance takes a significant amount of
Boundary {boundary_corner = (-8.6,-25.0), boundary_size = 0.1875}
Boundary {boundary_corner = (-23.541666666666668,11.666666666666666), boundary_size = 20.7}

The script "run_verify" compiles and executes the Verify.hs program. This is done in such a way
that any data-spacepart package installed is hidden and the modules are sourced directly from
the src folder.
The Verify.hs program just runs whatever QuickCheck tests I have thrown together. For each
module under src there is a corresponding module under Verify that contains it's Arbitrary
instances and verification properties.

The script "run_visualize" compiles and executes the QuadTreeVisualize program. This will be
compiled against the installed data-spacepart package.
The purpose of QuadTreeVisualize is to, well, visualize a random quadtree instance. in order to
run this program it's necessary to have OpenGL bindings that support FBO. I have a branch with
the required patches here:

The controls are:
- arrow keys move left, up, right, down.
- Shift-up and shift-down zoom in and zoom out respectively.

This visualization program should not require the FBO dependency. However it was pulled from a
different visualization system which did require FBOs. Removing this dependency is on the TODO

The version number of the library tries to follow the standard package version policy:

with the following addition: For the versiom number A.B.C.D D will be even for production releases
and odd for development versions.


- Renamed Math.Geometry to Data.SpacePart.AABB
- Renamed Data.QuadTree to Data.SpacePart.QuadTree
- Added Data.SpacePart.QuadTree.query. Returns all elements that intersect a given boundary.
- The inclusive nature of the boundary's min extent should take precedence of the exclusive
nature of the max extent.
Before this change many of the tests failed when boundaries of 0 area were involved. One case
that did not work was constructing a quadtree containing elements of 0 area. This change
corrected this.
The tests all_elements_inserted_query_prop and element_bounds_query_is_element_prop stil
fail if the element is of 0 area.
- Cannot create quadtrees with initial bounds of 0 area.
- Removed requirement on elements being an instance of the Intersectable class. The only
required instance is of Data.SpacePart.AABB.HasBoundary.
- Changed package name to spacepart instead of data-spacepart. The last release of
data-spacepart used a data based version number. This version number policy did not work well
with the standard package version policy.
- Added some QuickCheck based checks. Run with test/run_verify
- Cleaned up the module exports.

- Initial release.
Depends on 2 packages:
Used by 1 package:
comments powered byDisqus