K-Tree¶ ↑

<img src=“https://badges.gitter.im/Join%20Chat.svg” alt=“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.

<img src=“https://badge.fury.io/rb/k-tree.png” alt=“Gem Version” /> <img src=“https://travis-ci.org/flajann2/k-tree.svg?branch=master” alt=“Travis” />

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

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.

• Check out the latest master to make sure the feature hasn’t been implemented or the bug hasn’t been fixed yet.

• Check out the issue tracker to make sure someone already hasn’t requested it and/or contributed it.

• Fork the project.

• Start a feature/bugfix branch.

• Commit and push until you are happy with your contribution.

• Make sure to add tests for it. This is important so I don’t break it in a future version unintentionally.

• Please try not to mess with the Rakefile, version, or history. If you want to have your own version, or is otherwise necessary, that is fine, but please isolate to its own commit so I can cherry-pick around it.

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