Project

k-tree

0.0
No commit activity in last 3 years
No release in over 3 years
This is a data structure to represent and manage k-trees, primarily created for use in RubyNEAT, but may see other possible applications. The goal here is to be roebust in the creation of your k-tree, to allow you to prune during creation, since, especially for higher-dimensional trees, the number of leaf node can become very large. So a parent will have children nodes created down to the desired resolution, and immediately after the creation of the children, will check to see if there's enough variance among the children to keep them. If not, they are pruned immediately.
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
 Dependencies

Development

Runtime

>= 2.0.2, ~> 2.0
 Project Readme

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.

Gem Version¶ ↑

<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” />

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¶ ↑

  • 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.