Module type Oktree.MAKER

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

The type of the octree.

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 *)

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;
    ]

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

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 *)

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