Spatial Queries [ocaml-rtree-004]

Patrick Ferris

The lines we loaded into the last index are really just four segments of the line y = x. Let's spatially query for the first two segments.

# R.find r (Rtree.Rectangle.v ~x0:0. ~y0:0. ~x1:2. ~y1:2.);;
- : Line.t list =
[{Line.p0 = (0., 0.); p1 = (1., 1.)}; {Line.p0 = (1., 1.); p1 = (2., 2.)};
 {Line.p0 = (2., 2.); p1 = (3., 3.)}]

You can see the query actually returned the first three, that's because all bound checks are inclusive.

Context

OCaml Rtree Examples [ocaml-rtree-002]

Patrick Ferris

An R-Tree in OCaml is created from an envelope (the kind of bounding box) and a value (for storing in the tree). The value depends on the envelope as you have to provide a function to calculate an envelope from a value. Here is one way we might define a line using the provided two-dimensional Rectangle envelope.

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

In addition to the envelope function, we also need to provide a runtime representation using Repr. In the example, we've constructed it by hand but I recommend using ppx_repr to derive it for you. From here we can create our index.

module R = Rtree.Make (Rtree.Rectangle) (Line)

Inserting Values [ocaml-rtree-003]

Patrick Ferris

There are two ways to insert values into the index -- either by inserting them one-by-one or by bulk loading them. The latter is the recommended approach where possible as the resulting layout of the R-Tree is much better.

# let r =
    let i = R.empty 4 in
    R.insert i Line.{ p0 = (1., 1.); p1 = (2., 2.) };;
val r : R.t = <abstr>

As you might expect, bulk loading takes a list of values instead.

# let r =
    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:4 lines;;
val r : R.t = <abstr>

Spatial Queries [ocaml-rtree-004]

Patrick Ferris

The lines we loaded into the last index are really just four segments of the line y = x. Let's spatially query for the first two segments.

# R.find r (Rtree.Rectangle.v ~x0:0. ~y0:0. ~x1:2. ~y1:2.);;
- : Line.t list =
[{Line.p0 = (0., 0.); p1 = (1., 1.)}; {Line.p0 = (1., 1.); p1 = (2., 2.)};
 {Line.p0 = (2., 2.); p1 = (3., 3.)}]

You can see the query actually returned the first three, that's because all bound checks are inclusive.