Module Oktree.Make

Make (V3) creates an octree module for 3D points represented by V3.

The V3 module must satisfy the VEC3 interface. The most common choice is Gg.V3.

  open Gg

  (* Create an octree module using Gg.V3 *)
  module Okt = Oktree.Make (V3)

  (* Now use Okt.of_list, Okt.nearest, etc. *)
  let tree = Okt.of_list [V3.zero; V3.v 1.0 0.0 0.0]
  let nearest = Okt.nearest tree (V3.v 0.5 0.0 0.0)
  (* Custom vector implementation *)
  module Float3 : Oktree.VEC3 with type t = float * float * float = struct
    type t = float * float * float
    let x (x, _, _) = x
    let y (_, y, _) = y
    let z (_, _, z) = z
    let of_tuple t = t
    let to_tuple t = t
    let add (x1, y1, z1) (x2, y2, z2) = (x1 +. x2, y1 +. y2, z1 +. z2)
    let sub (x1, y1, z1) (x2, y2, z2) = (x1 -. x2, y1 -. y2, z1 -. z2)
    let div (x1, y1, z1) (x2, y2, z2) = (x1 /. x2, y1 /. y2, z1 /. z2)
    let norm (x, y, z) = sqrt (x *. x +. y *. y +. z *. z)
    let map f (x, y, z) = (f x, f y, f z)
    let pp fmt (x, y, z) = Format.fprintf fmt "(%g, %g, %g)" x y z
  end

  module Okt = Oktree.Make (Float3)
  let tree = Okt.of_list [(0., 0., 0.); (1., 1., 1.)]

Parameters

module V3 : sig ... end

Signature

type vec3 = V3.t

The type of 3D vectors used as points in the octree.

type t

The type of the octree.

val pp : Stdlib.Format.formatter -> t -> unit

pp ppf tree prints a textual representation of the octree structure.

Useful for debugging and understanding tree layout.

  open Gg
  module Okt = Oktree.Make (V3)

  let tree = Okt.of_list [V3.zero; V3.v 1.0 0.0 0.0]
  let () = Format.printf "%a@." Okt.pp tree
  (* Prints the tree structure showing nodes and leaves *)
val insert : t -> vec3 -> t

insert tree point returns a new tree with point added.

The tree is persistent/immutable, so this returns a new tree rather than modifying the existing one.

Note: For bulk insertions, it is more efficient to rebuild the tree with of_list than to insert points one by one.

  open Gg
  module Okt = Oktree.Make (V3)

  (* Start with a tree *)
  let tree = Okt.of_list [V3.zero; V3.v 1.0 0.0 0.0]

  (* Add a new point *)
  let tree2 = Okt.insert tree (V3.v 0.0 1.0 0.0)

  (* Original tree unchanged, tree2 has the new point *)
  let points = Okt.to_list tree2
  (* points includes (0, 1, 0) *)
  (* Add multiple points *)
  let initial = Okt.of_list [V3.zero]
  let tree = List.fold_left Okt.insert initial [
      V3.v 1.0 0.0 0.0;
      V3.v 0.0 1.0 0.0;
      V3.v 0.0 0.0 1.0;
    ]
val of_list : ?leaf_size:int -> vec3 list -> t

of_list ?leaf_size points builds an octree from a list of points.

This is the primary way to construct an octree. The tree is built by recursively subdividing space until each leaf contains at most leaf_size points.

  • parameter leaf_size

    Maximum points per leaf before subdivision (default: 16). Smaller values create deeper trees, larger values create shallower trees. Tune based on your data distribution.

  open Gg
  module Okt = Oktree.Make (V3)

  (* Build with default leaf size *)
  let tree = Okt.of_list [
      V3.v 0.0 0.0 0.0;
      V3.v 1.0 0.0 0.0;
      V3.v 0.0 1.0 0.0;
      V3.v 0.0 0.0 1.0;
    ]
  (* Build with custom leaf size *)
  let tree = Okt.of_list ~leaf_size:4 many_points
  (* Smaller leaf size: more subdivision, faster queries *)
  (* Build from generated points *)
  let points = List.init 100 (fun i ->
      let t = float_of_int i /. 100.0 in
      V3.v t (sin t) (cos t)
    ) in
  let tree = Okt.of_list ~leaf_size:8 points
val to_list : t -> vec3 list

to_list tree returns all points stored in the tree as a list.

Useful for inspecting tree contents or extracting points after filtering.

  open Gg
  module Okt = Oktree.Make (V3)

  let points = [V3.zero; V3.v 1.0 0.0 0.0; V3.v 0.0 1.0 0.0]
  let tree = Okt.of_list points

  (* Get all points back *)
  let all_points = Okt.to_list tree
  (* all_points contains the same three points *)

  (* Count points in tree *)
  let count = List.length (Okt.to_list tree)
  (* count = 3 *)
  (* Check if a specific point is in the tree *)
  let tree = Okt.of_list [V3.zero; V3.v 1.0 0.0 0.0]
  let has_origin =
    List.exists (fun p -> V3.x p = 0. && V3.y p = 0. && V3.z p = 0.)
      (Okt.to_list tree)
  (* has_origin = true *)
val nearest : t -> vec3 -> vec3

nearest tree query finds the point in tree closest to query.

Uses Euclidean distance to determine the nearest point. This is the primary operation the octree is optimized for.

Time complexity: O(log n) average case for well-distributed points, O(n) worst case for highly clustered points.

  open Gg
  module Okt = Oktree.Make (V3)

  let tree = Okt.of_list [
      V3.v 0.0 0.0 0.0;
      V3.v 1.0 0.0 0.0;
      V3.v 0.0 1.0 0.0;
    ]

  (* Find nearest to origin *)
  let near_origin = Okt.nearest tree (V3.v 0.1 0.1 0.1)
  (* near_origin = V3.v 0.0 0.0 0.0 *)

  (* Find nearest to (0.9, 0, 0) *)
  let near_x = Okt.nearest tree (V3.v 0.9 0.0 0.0)
  (* near_x = V3.v 1.0 0.0 0.0 *)
  (* Color quantization example *)
  let palette = [
    V3.v 1.0 0.0 0.0;  (* red *)
    V3.v 0.0 1.0 0.0;  (* green *)
    V3.v 0.0 0.0 1.0;  (* blue *)
  ]
  let palette_tree = Okt.of_list palette

  (* Quantize orange to nearest palette color *)
  let orange = V3.v 1.0 0.5 0.0
  let quantized = Okt.nearest palette_tree orange
  (* quantized = V3.v 1.0 0.0 0.0 (red, closest to orange) *)
  (* Batch nearest neighbor queries *)
  let tree = Okt.of_list large_dataset

  let find_all_nearest queries =
    List.map (Okt.nearest tree) queries

  let nearest_points = find_all_nearest query_points