Math::Vector::Real::kdTree - kd-Tree implementation on top of Math::Vector::Real
use Math::Vector::Real::kdTree; use Math::Vector::Real; use Math::Vector::Real::Random; my @v = map Math::Vector::Real->random_normal(4), 1..1000; my $tree = Math::Vector::Real::kdTree->new(@v); my $ix = $tree->find_nearest_neighbor(V(0, 0, 0, 0)); say "nearest neighbor is $ix, $v[$ix]";
This module implements a kd-Tree data structure in Perl and some related algorithms.
The following methods are provided:
Creates a new kdTree containing the gived points.
Creates a duplicate of the tree. The two trees will share internal read only data so this method is more efficient in terms of memory usage than others performing a deep copy.
Inserts the given points into the kdTree.
Returns the index assigned to the first point inserted.
Returns the number of points inside the tree.
Returns the point at the given index inside the tree.
Moves the point at index $ix to the new given position readjusting the tree structure accordingly.
$ix
Find the nearest neighbor for the given point $p and returns its index and the distance between the two points (in scalar context the index is returned).
$p
If $max_d is defined, the search is limited to the points within that distance
$max_d
If $but_ix is defined, the point with the given index is not considered.
$but_ix
Returns the index of the nearest neighbor for every point inside the tree.
It is equivalent to (though, internally, it uses a better algorithm):
@ix = map { scalar $t->nearest_neighbor($t->at($_), undef, $_) } 0..($t->size - 1);
Finds the points inside the tree contained in the hypersphere with center $z and radius $d.
$z
$d
In scalar context returns the number of points found. In list context returns the indexes of the points.
If the extra argument $but is provided. The point with that index is ignored.
$but
Returns the indexes of the points in an ordered where is likely that the indexes of near vectors are also in near positions in the list.
http://en.wikipedia.org/wiki/K-d_tree
Math::Vector::Real
Copyright (C) 2011-2013 by Salvador Fandiño <sfandino@yahoo.com>
This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.12.3 or, at your option, any later version of Perl 5 you may have available.
To install Math::Vector::Real::kdTree, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Math::Vector::Real::kdTree
CPAN shell
perl -MCPAN -e shell install Math::Vector::Real::kdTree
For more information on module installation, please visit the detailed CPAN module installation guide.