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 kdTree containing the gived points.
- $t->insert($p)
- 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.
- @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, 2012 by Salvador FandiA~Xo <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.