Data.RTree

R-Tree is a spartial 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.

Documentation

data MBB

Minimal bounding box

Instances

Eq MBB

Show MBB

Generic MBB

Binary MBB

mbb

Arguments

:: 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 RTree a

Instances

Functor RTree

Typeable1 RTree

Eq a => Eq (RTree a)

Show a => Show (RTree a)

Generic (RTree a)

Binary a => Binary (RTree a)

NFData a => NFData (RTree a)

empty :: RTree a

creates an empty tree

singleton :: MBB -> a -> RTree a

creates a single element tree

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

inserts an element whith the given MBB and a value in a tree

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

unifies the first and the second tree into one.

lookup :: MBB -> RTree a -> Maybe a

returns the value if it exists in the tree

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

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

fromList :: [(MBB, a)] -> RTree a

creates a tree out of pairs

toList :: RTree a -> [(MBB, a)]

creates a list of pairs out of a tree

toList t = zip (keys t) (values t)

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

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

length :: RTree a -> Int

returns the number of elements in a tree

null :: RTree a -> Bool

returns True, if empty

null empty = True

keys :: RTree a -> [MBB]

returns all keys in this tree

toList t = zip (keys t) (values t)

values :: RTree a -> [a]

returns all values in this tree

toList t = zip (keys t) (values t)