++ed by:

1 PAUSE user
1 non-PAUSE user.

Author image Salvador Fandiño García


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:

$t = Math::Vector::Real::kdTree->new(@points)

Creates a new kdTree containing the gived points.


Inserts the given point into the kdTree.

$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)

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

If $but_ix is defined, the point with the given index is not considered.

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





Copyright (C) 2011 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.

1 POD Error

The following errors were encountered while parsing the POD:

Around line 430:

Non-ASCII character seen before =encoding in 'Fandiño'. Assuming UTF-8