Portability | not portable |
---|---|

Stability | experimental |

Maintainer | Birte Wagner, Sebastian Philipp (sebastian@spawnhost.de) |

Safe Haskell | None |

R-Tree is a spatial data structure similar to Quadtrees or B-Trees.

An R-Tree is a balanced tree and optimized for lookups. This implemetation useses an R-Tree to privide a map to arbitrary values.

Some function names clash with Prelude names, therefore this module is usually
imported `qualified`

, e.g.

import Data.RTree (RTree) import qualified Data.RTree as RT

this implemetation is incomplete at the moment. Feel free to send comments, patches or merge requests.

- data MBB
- mbb :: Double -> Double -> Double -> Double -> MBB
- data RTree a
- empty :: RTree a
- singleton :: MBB -> a -> RTree a
- insert :: MBB -> a -> RTree a -> RTree a
- insertWith :: (a -> a -> a) -> MBB -> a -> RTree a -> RTree a
- delete :: MBB -> RTree a -> RTree a
- mapMaybe :: (a -> Maybe b) -> RTree a -> RTree b
- union :: RTree a -> RTree a -> RTree a
- unionWith :: (a -> a -> a) -> RTree a -> RTree a -> RTree a
- lookup :: MBB -> RTree a -> Maybe a
- lookupRange :: MBB -> RTree a -> [a]
- lookupRangeWithKey :: MBB -> RTree a -> [(MBB, a)]
- length :: RTree a -> Int
- null :: RTree a -> Bool
- keys :: RTree a -> [MBB]
- values :: RTree a -> [a]
- fromList :: [(MBB, a)] -> RTree a
- toList :: RTree a -> [(MBB, a)]

`MBB`

:: Double | x - coordinate of first point |

-> Double | y - coordinate of first point |

-> Double | x - coordinate of second point |

-> Double | x - coordinate of second point |

-> MBB |

created a minimal bounding box (or a rectangle) The first point must be smaller, than the second one. This is unchecked.

# Data Type

# Constructors

# Modification

insert :: MBB -> a -> RTree a -> RTree aSource

Inserts an element whith the given `MBB`

and a value in a tree. An existing value will be overwritten with the given one.

insert = insertWith const

insertWith :: (a -> a -> a) -> MBB -> a -> RTree a -> RTree aSource

Inserts an element whith the given `MBB`

and a value in a tree. The combining function will be used if the value already exists.

delete :: MBB -> RTree a -> RTree aSource

Delete a key and its value from the RTree. When the key is not a member of the tree, the original tree is returned.

## Merging

union :: RTree a -> RTree a -> RTree aSource

Unifies the first and the second tree into one.
If an `MBB`

is a key in both trees, the value from the left tree is chosen.

union = unionWith const

unionWith :: (a -> a -> a) -> RTree a -> RTree a -> RTree aSource

Unifies the first and the second tree into one. The combining function is used for elemets which exists in both trees.

# Searching and Properties

lookupRange :: MBB -> RTree a -> [a]Source

returns all values, which are located in the given bounding box.

lookupRangeWithKey :: MBB -> RTree a -> [(MBB, a)]Source

returns all keys and values, which are located in the given bounding box.