K-Tree

Join the chat at https://gitter.im/flajann2/k-tree

K-Tree is a data structure that generalizes the notion of Quadtrees and Octrees. The nodes subdivides the n-dimentional space into equal subsections of 2^n k-tants (quadrants for 2-dimensional spaces, octants for 3-dimensional) down to your desired level of resolution, and during the creation allows you to decide whether or not to keep the child nodes based on your criteria for whether or not there's enough variance.

The coordinats of the midpoint of all these sections are maintained by k-tree and are therefore enumerable.

Gem Version

Gem Version Travis

Usage

Examples

For now, I will use the spec as example of usage. This is lame, I'll admit, but I will improve this shortly.

require 'k-tree'
include KTree

let(:ktree) do
  KTree.create do |node, vchildren|
    rand(3) != 5
  end
end

it "created a tree" do
  expect(ktree).to_not be_nil
end

it "has nodes" do
  expect(ktree.root).to_not be_nil
end

it "upper and lower coords are never equal" do
  ktree.each do |node|
    expect(node.upper).to_not eq node.lower
  end
end

Known Issues

Currently K-Tree does not support “nearest neighbor” queries, as this is beyond the scope of the current needs of the author. Check out kd-tree amd r-tree for that. Or feel free to add that functionality and do a pull request.

Contributing to k-tree

Copyright © 2014 Fred Mitchell. See LICENSE.txt for further details.