package rtree
Install
Dune Dependency
Authors
Maintainers
Sources
sha256=408c9600703ea96f3ccd9f99dea853d5cb6c76c05e7e546ac18d90fc42426147
sha512=0d658adce2995dbe2de8bf5a93161fe0013872152417472cbf5bb00d8eed99a073e3942ad7cc6bb4e9d37d90853a58adb712fa5e9837301e4cd5c2ed68ebbaa5
doc/index.html
Rtree
An Rtree is a data-structure for indexing geospatial information. They are quite closely related to B-trees. They make it quicker to perform geospatial queries on data such as "what are all the items that are inside this area?".
This library provides in-memory Rtrees that are parameterised over both the envelope (minimal bounding box) and the values stored in the the rtree. Note that the values are tied to the envelope as you must provide a means of calculating an envelope from any value.
To this end you probably want to start with Rtree.Make
and for must two-dimensional use cases the Rtree.Rectangle
envelope it probably what you are looking for.
Core Modules
Guide
There are two key elements to an rtree. The type of envelopes used and the type of the values being store in the tree. These values must come with a function to calculate an envelope.
The core library comes with an implementation of envelopes as two-dimensional Rtree.Rectangle
.
If you wanted to store lines in your rtree, one possible implementation might be the following.
module Line = struct
type t = { p0 : float * float; p1 : float * float }
let t =
let open Repr in
record "line" (fun p0 p1 -> { p0; p1 })
|+ field "p0" (pair float float) (fun t -> t.p0)
|+ field "p1" (pair float float) (fun t -> t.p1)
|> sealr
type envelope = Rtree.Rectangle.t
let envelope { p0 = (x1, y1); p1 = (x2, y2) } =
let x0 = Float.min x1 x2 in
let x1 = Float.max x1 x2 in
let y0 = Float.min y1 y2 in
let y1 = Float.max y1 y2 in
Rtree.Rectangle.v ~x0 ~y0 ~x1 ~y1
end
module R = Rtree.Make(Rtree.Rectangle)(Line)
Insertion
To insert into an rtree, you simply pass a value into a pre-existing rtree. You can create an empty rtree where you control the maximum node load size. This is essentially the branching factor in the tree. The correct value is hard to guess.
# let index = R.empty 8;;
val index : R.t = <abstr>
# let index = R.insert index Line.{ p0 = (1., 2.); p1 = (3., 3.) };;
val index : R.t = <abstr>
# let index = R.insert index Line.{ p0 = (4., 4.); p1 = (5., 5.) };;
val index : R.t = <abstr>
Loading
If you have a list of values to put into an rtree, then you are better off using the `load` function instead of folding and inserting. This uses the OMT algorithm and should give you a more optimised rtree layout.
let lines =
Line.[
{ p0 = (0., 0.); p1 = (1., 1.) };
{ p0 = (1., 1.); p1 = (2., 2.) };
{ p0 = (2., 2.); p1 = (3., 3.) };
{ p0 = (3., 3.); p1 = (4., 4.) };
]
in
R.load ~max_node_load:2 lines
Find
Finding values requires you to pass in a search envelope. A list of result, perhaps empty, will be returned.
# R.find index (Rtree.Rectangle.v ~x0:0. ~y0:0. ~x1:3. ~y1:3.);;
- : Line.t list = [{Line.p0 = (1., 2.); p1 = (3., 3.)}]
# R.find index (Rtree.Rectangle.v ~x0:0. ~y0:0. ~x1:5. ~y1:5.);;
- : Line.t list =
[{Line.p0 = (4., 4.); p1 = (5., 5.)}; {Line.p0 = (1., 2.); p1 = (3., 3.)}]