nox-rtree #

Warning. This is a work-in-progress experimental fork of rtree. Do not use it in production; use rtree instead.

An R-tree spatial index in pure OCaml, after Guttman's 1984 paper: node splitting is the quadratic algorithm from that paper, and bulk loading is OMT (Overlap Minimising Top-down, Lee and Lee 2003). OMT builds the tree from the root down: at each level it sorts the values along one axis, cuts them into slices, cuts each slice along the next axis, and recurses, so that sibling nodes overlap little and each node is filled.

nox-rtree is a fork of geocaml/ocaml-rtree, whose design it keeps: the envelope type is a functor parameter, so the same tree indexes two-dimensional rectangles, three-dimensional cubes, or anything else with a bounding box. This fork drops the repr dependency, and with it the runtime type representations and the persistence they supported; value equality is a function on the value module instead.

Usage #

A value supplies its own envelope and an equality:

# module Box = struct
    type t = { id : int; env : Rtree.Rectangle.t }
    let equal a b = a.id = b.id
    type envelope = Rtree.Rectangle.t
    let envelope t = t.env
  end
module Box :
  sig
    type t = { id : int; env : Rtree.Rectangle.t; }
    val equal : t -> t -> bool
    type envelope = Rtree.Rectangle.t
    val envelope : t -> envelope
  end
# module R = Rtree.Make (Rtree.Rectangle) (Box)
module R :
  sig
    type t = Rtree.Make(Rtree.Rectangle)(Box).t
    module Envelope :
      sig
        type t = Box.envelope
        val dimensions : int
        val compare_dim : int -> t -> t -> int
        val empty : t
        val intersects : t -> t -> bool
        val merge : t -> t -> t
        val merge_many : t list -> t
        val area : t -> float
        val contains : t -> t -> bool
      end
    module Value :
      sig
        type t = Box.t
        val equal : t -> t -> bool
        type envelope = Envelope.t
        val envelope : t -> envelope
      end
    type tree =
      Rtree.Make(Rtree.Rectangle)(Box).tree =
        Node of (Value.envelope * tree) list
      | Leaf of (Value.envelope * Value.t) list
      | Empty
    val tree : t -> tree
    val empty : int -> t
    val insert : t -> Value.t -> t
    val remove : t -> Value.t -> Value.t list * t
    val remove_eq : t -> (Value.t -> bool) -> Value.t list * t
    val remove_env : t -> Value.envelope -> Value.t list * t
    val find : t -> Value.envelope -> Value.t list
    val size : t -> int
    val bounds : t -> Value.envelope option
    val values : t -> Value.t list
    val load : ?max_node_load:int -> Value.t list -> t
    val depth : t -> int
    val iter : t -> (tree -> unit) -> unit
  end

Bulk load, then query:

# let boxes =
    List.init 4 (fun i ->
        let x = float_of_int i in
        { Box.id = i; env = Rtree.Rectangle.v ~x0:x ~y0:0. ~x1:(x +. 0.5) ~y1:1. })
val boxes : Box.t list =
  [{Box.id = 0; env = <abstr>}; {Box.id = 1; env = <abstr>};
   {Box.id = 2; env = <abstr>}; {Box.id = 3; env = <abstr>}]
# let t = R.load ~max_node_load:4 boxes
val t : R.t = <abstr>
# R.size t
- : int = 4
# R.find t (Rtree.Rectangle.v ~x0:0.9 ~y0:0. ~x1:2.1 ~y1:1.)
  |> List.map (fun v -> v.Box.id) |> List.sort compare
- : int list = [1; 2]

find is intersection, not containment: a value straddling the edge of the query envelope comes back, and so does one merely touching it.

Prefiltering and exact tests #

A bounding box is not the shape inside it. When the values are discs, polygons or anything else with a boundary of its own, the tree narrows the query to the few worth looking at and an exact test of yours decides those:

# module Disc = struct
    type t = { id : int; cx : float; cy : float; r : float }
    let equal a b = a.id = b.id
    type envelope = Rtree.Rectangle.t
    let envelope t =
      Rtree.Rectangle.v
        ~x0:(t.cx -. t.r) ~y0:(t.cy -. t.r)
        ~x1:(t.cx +. t.r) ~y1:(t.cy +. t.r)
  end
module Disc :
  sig
    type t = { id : int; cx : float; cy : float; r : float; }
    val equal : t -> t -> bool
    type envelope = Box.envelope
    val envelope : t -> envelope
  end
# module D = Rtree.Make (Rtree.Rectangle) (Disc)
module D :
  sig
    type t = Rtree.Make(Rtree.Rectangle)(Disc).t
    module Envelope :
      sig
        type t = Disc.envelope
        val dimensions : int
        val compare_dim : int -> t -> t -> int
        val empty : t
        val intersects : t -> t -> bool
        val merge : t -> t -> t
        val merge_many : t list -> t
        val area : t -> float
        val contains : t -> t -> bool
      end
    module Value :
      sig
        type t = Disc.t
        val equal : t -> t -> bool
        type envelope = Envelope.t
        val envelope : t -> envelope
      end
    type tree =
      Rtree.Make(Rtree.Rectangle)(Disc).tree =
        Node of (Value.envelope * tree) list
      | Leaf of (Value.envelope * Value.t) list
      | Empty
    val tree : t -> tree
    val empty : int -> t
    val insert : t -> Value.t -> t
    val remove : t -> Value.t -> Value.t list * t
    val remove_eq : t -> (Value.t -> bool) -> Value.t list * t
    val remove_env : t -> Value.envelope -> Value.t list * t
    val find : t -> Value.envelope -> Value.t list
    val size : t -> int
    val bounds : t -> Value.envelope option
    val values : t -> Value.t list
    val load : ?max_node_load:int -> Value.t list -> t
    val depth : t -> int
    val iter : t -> (tree -> unit) -> unit
  end
# let index =
    D.load ~max_node_load:4
      [ { Disc.id = 0; cx = 0.; cy = 0.; r = 1. };
        { Disc.id = 1; cx = 3.; cy = 0.; r = 1. } ]
val index : D.t = <abstr>
# let covering x y =
    D.find index (Rtree.Rectangle.v ~x0:x ~y0:y ~x1:x ~y1:y)
    |> List.filter (fun d ->
           Float.hypot (x -. d.Disc.cx) (y -. d.Disc.cy) <= d.Disc.r)
    |> List.map (fun d -> d.Disc.id)
val covering : float -> float -> int list = <fun>
# covering 0.5 0.5
- : int list = [0]
# covering 0.9 0.9
- : int list = []

The last query is why the pair exists: (0.9, 0.9) is inside the bounding square of disc 0, so find returns it as a candidate, and only the exact test rules it out. Geographic areas work the same way, with a point-in-ring test on the survivors; latlon pairs the two that way.

Licence #

BSD-3-Clause. See LICENSE.md.