Copyright | Copyright (c) 2015 Birte Wagner Sebastian Philipp |
---|---|
License | MIT |
Maintainer | Birte Wagner, Sebastian Philipp (sebastian@spawnhost.de) |
Stability | experimental |
Portability | not portable |
Safe Haskell | Safe |
Language | Haskell2010 |
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.
Synopsis
- 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
- intersectWithKey :: MBB -> RTree a -> [(MBB, a)]
- intersect :: MBB -> RTree a -> [a]
- lookupRange :: MBB -> RTree a -> [a]
- lookupRangeWithKey :: MBB -> RTree a -> [(MBB, a)]
- lookupContainsRange :: MBB -> RTree a -> [a]
- lookupContainsRangeWithKey :: 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
Minimal bounding box
Instances
Eq MBB Source # | |
Ord MBB Source # | |
Show MBB Source # | |
Generic MBB Source # | |
Binary MBB Source # | |
type Rep MBB Source # | |
Defined in Data.RTree.MBB type Rep MBB = D1 (MetaData "MBB" "Data.RTree.MBB" "data-r-tree-0.6.0-HxW7KWxwR847heBr9qHG8D" False) (C1 (MetaCons "MBB" PrefixI True) ((S1 (MetaSel (Just "getUlx") SourceUnpack SourceStrict DecidedStrict) (Rec0 Double) :*: S1 (MetaSel (Just "getUly") SourceUnpack SourceStrict DecidedStrict) (Rec0 Double)) :*: (S1 (MetaSel (Just "getBrx") SourceUnpack SourceStrict DecidedStrict) (Rec0 Double) :*: S1 (MetaSel (Just "getBry") SourceUnpack SourceStrict DecidedStrict) (Rec0 Double)))) |
:: 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
Instances
Constructors
Modification
insert :: MBB -> a -> RTree a -> RTree a Source #
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 a Source #
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 a Source #
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 a Source #
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 a Source #
Unifies the first and the second tree into one. The combining function is used for elemets which exists in both trees.
Searching and Properties
intersectWithKey :: MBB -> RTree a -> [(MBB, a)] Source #
returns all keys and values, which intersects with the given bounding box.
intersect :: MBB -> RTree a -> [a] Source #
returns all values, which intersects with the given bounding box.
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.
lookupContainsRange :: MBB -> RTree a -> [a] Source #
returns all values containing the given bounding box
lookupContainsRangeWithKey :: MBB -> RTree a -> [(MBB, a)] Source #
returns all keys and values containing the given bounding box