Module Oktree

OKtree is a simple octree implementation in OCaml, intended to efficiently find the nearest match for an arbitrary point among a set of target points in 3D coordinate space.

An octree is a tree data structure in which each internal node has
exactly eight children. Octrees are most often used to partition a
three-dimensional space by recursively subdividing it into eight octants.
Octrees are the three-dimensional analog of quadtrees.

— Wikipedia

The original use case for this library was finding nearest match in a palette of RGB colours.

Basic Usage

A tree is generated from a list of 3D points.

OKtree defines a VEC3 module type for the points. This is deliberately compatible with the Gg library's Gg.V3 module type.

So first we instantiate the Oktree functor, then add points:

      open Gg

      module Okt = Oktree.Make (V3)

      let points = [ V3.zero; V3.v 0. 0.251 0.; V3.v 0. 0.23 0.; V3.v 0.2 0.1 0.2 ]
      let okt = Okt.of_list ~leaf_size:8 points

      let () = Format.printf "%a" Okt.pp okt
(*
{ Oktree.Make.leaf_size = 8;
  tree =
  (Oktree.Make.Leaf
     [(0.000000, 0.000000, 0.000000); (0.000000, 0.251000, 0.000000);
       (0.000000, 0.230000, 0.000000); (0.200000, 0.100000, 0.200000)])
  }- : unit = ()
*)

      (* find closest match from [points] *)
      let nearest = Okt.nearest okt (V3.v 0.2 0.1 0.3)

      let () = Format.printf "%a" V3.pp nearest
      (* (0.2 0.1 0.2)- : unit = () *)

Interface

More Examples

For comprehensive examples see the module types below:

Project

module type VEC3 = sig ... end

Module type for 3D vectors. See VEC3.

module type S = sig ... end

Module type for octree operations. See S.

module type MAKER = sig ... end

Functor type for creating octree modules. See MAKER.

module Make : MAKER

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