NAME

       Math::Vector::Real::kdTree - kd-Tree implementation on top of Math::Vector::Real

SYNOPSIS

         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]";

DESCRIPTION

       This module implements a kd-Tree data structure in Perl and some related algorithms.

       The following methods are provided:

       $t = Math::Vector::Real::kdTree->new(@points)
           Creates a new kd-Tree containing the given points.

       $t2 = $t->clone
           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.

       my $ix = $t->insert($p0, $p1, ...)
           Inserts the given points into the kd-Tree.

           Returns the index assigned to the first point inserted.

       $s = $t->size
           Returns the number of points inside the tree.

       $p = $t->at($ix)
           Returns the point at the given index inside the tree.

       $t->move($ix, $p)
           Moves the point at index $ix to the new given position readjusting the tree structure accordingly.

       ($ix, $d) = $t->find_nearest_neighbor($p, $max_d, @but_ix)
       ($ix, $d) = $t->find_nearest_neighbor($p, $max_d, \%but_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).

           If $max_d is defined, the search is limited to the points within that distance

           Optionally, a list of point indexes to be excluded from the search can be passed or, alternatively, a
           reference to a hash containing the indexes of the points to be excluded.

       @ix = $t->find_nearest_neighbor_all_internal
           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);

       @ix = $t->find_in_ball($z, $d, $but)
       $n = $t->find_in_ball($z, $d, $but)
           Finds the points inside the tree contained in the hypersphere with center $z and radius $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.

       @ix = $t->ordered_by_proximity
           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.

SEE ALSO

       http://en.wikipedia.org/wiki/K-d_tree <http://en.wikipedia.org/wiki/K-d_tree>

       Math::Vector::Real

COPYRIGHT AND LICENSE

       Copyright (C) 2011-2013 by Salvador Fandin~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.

perl v5.14.2                                       2013-06-17                    Math::Vector::Real::kdTree(3pm)