.\" Automatically generated by Pod::Man 2.28 (Pod::Simple 3.28)
.\"
.\" Standard preamble:
.\" ========================================================================
.de Sp \" Vertical space (when we can't use .PP)
.if t .sp .5v
.if n .sp
..
.de Vb \" Begin verbatim text
.ft CW
.nf
.ne \\$1
..
.de Ve \" End verbatim text
.ft R
.fi
..
.\" Set up some character translations and predefined strings.  \*(-- will
.\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left
.\" double quote, and \*(R" will give a right double quote.  \*(C+ will
.\" give a nicer C++.  Capital omega is used to do unbreakable dashes and
.\" therefore won't be available.  \*(C` and \*(C' expand to `' in nroff,
.\" nothing in troff, for use with C<>.
.tr \(*W-
.ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p'
.ie n \{\
.    ds -- \(*W-
.    ds PI pi
.    if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch
.    if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\"  diablo 12 pitch
.    ds L" ""
.    ds R" ""
.    ds C` ""
.    ds C' ""
'br\}
.el\{\
.    ds -- \|\(em\|
.    ds PI \(*p
.    ds L" ``
.    ds R" ''
.    ds C`
.    ds C'
'br\}
.\"
.\" Escape single quotes in literal strings from groff's Unicode transform.
.ie \n(.g .ds Aq \(aq
.el       .ds Aq '
.\"
.\" If the F register is turned on, we'll generate index entries on stderr for
.\" titles (.TH), headers (.SH), subsections (.SS), items (.Ip), and index
.\" entries marked with X<> in POD.  Of course, you'll have to process the
.\" output yourself in some meaningful fashion.
.\"
.\" Avoid warning from groff about undefined register 'F'.
.de IX
..
.nr rF 0
.if \n(.g .if rF .nr rF 1
.if (\n(rF:(\n(.g==0)) \{
.    if \nF \{
.        de IX
.        tm Index:\\$1\t\\n%\t"\\$2"
..
.        if !\nF==2 \{
.            nr % 0
.            nr F 2
.        \}
.    \}
.\}
.rr rF
.\"
.\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2).
.\" Fear.  Run.  Save yourself.  No user-serviceable parts.
.    \" fudge factors for nroff and troff
.if n \{\
.    ds #H 0
.    ds #V .8m
.    ds #F .3m
.    ds #[ \f1
.    ds #] \fP
.\}
.if t \{\
.    ds #H ((1u-(\\\\n(.fu%2u))*.13m)
.    ds #V .6m
.    ds #F 0
.    ds #[ \&
.    ds #] \&
.\}
.    \" simple accents for nroff and troff
.if n \{\
.    ds ' \&
.    ds ` \&
.    ds ^ \&
.    ds , \&
.    ds ~ ~
.    ds /
.\}
.if t \{\
.    ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u"
.    ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u'
.    ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u'
.    ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u'
.    ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u'
.    ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u'
.\}
.    \" troff and (daisy-wheel) nroff accents
.ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V'
.ds 8 \h'\*(#H'\(*b\h'-\*(#H'
.ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#]
.ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H'
.ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u'
.ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#]
.ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#]
.ds ae a\h'-(\w'a'u*4/10)'e
.ds Ae A\h'-(\w'A'u*4/10)'E
.    \" corrections for vroff
.if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u'
.if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u'
.    \" for low resolution devices (crt and lpr)
.if \n(.H>23 .if \n(.V>19 \
\{\
.    ds : e
.    ds 8 ss
.    ds o a
.    ds d- d\h'-1'\(ga
.    ds D- D\h'-1'\(hy
.    ds th \o'bp'
.    ds Th \o'LP'
.    ds ae ae
.    ds Ae AE
.\}
.rm #[ #] #H #V #F C
.\" ========================================================================
.\"
.IX Title "Math::Vector::Real::kdTree 3pm"
.TH Math::Vector::Real::kdTree 3pm "2014-10-07" "perl v5.20.1" "User Contributed Perl Documentation"
.\" For nroff, turn off justification.  Always turn off hyphenation; it makes
.\" way too many mistakes in technical documents.
.if n .ad l
.nh
.SH "NAME"
Math::Vector::Real::kdTree \- kd\-Tree implementation on top of Math::Vector::Real
.SH "SYNOPSIS"
.IX Header "SYNOPSIS"
.Vb 1
\&  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_vector(V(0, 0, 0, 0));
\&
\&  say "nearest vector is $ix, $v[$ix]";
.Ve
.SH "DESCRIPTION"
.IX Header "DESCRIPTION"
This module implements a kd-Tree data structure in Perl and common
algorithms on top of it.
.SS "Methods"
.IX Subsection "Methods"
The following methods are provided:
.ie n .IP "$t = Math::Vector::Real::kdTree\->new(@points)" 4
.el .IP "\f(CW$t\fR = Math::Vector::Real::kdTree\->new(@points)" 4
.IX Item "$t = Math::Vector::Real::kdTree->new(@points)"
Creates a new kd-Tree containing the given points.
.ie n .IP "$t2 = $t\->clone" 4
.el .IP "\f(CW$t2\fR = \f(CW$t\fR\->clone" 4
.IX Item "$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.
.ie n .IP "my $ix = $t\->insert($p0, $p1, ...)" 4
.el .IP "my \f(CW$ix\fR = \f(CW$t\fR\->insert($p0, \f(CW$p1\fR, ...)" 4
.IX Item "my $ix = $t->insert($p0, $p1, ...)"
Inserts the given points into the kd-Tree.
.Sp
Returns the index assigned to the first point inserted.
.ie n .IP "$s = $t\->size" 4
.el .IP "\f(CW$s\fR = \f(CW$t\fR\->size" 4
.IX Item "$s = $t->size"
Returns the number of points inside the tree.
.ie n .IP "$p = $t\->at($ix)" 4
.el .IP "\f(CW$p\fR = \f(CW$t\fR\->at($ix)" 4
.IX Item "$p = $t->at($ix)"
Returns the point at the given index inside the tree.
.ie n .IP "$t\->move($ix, $p)" 4
.el .IP "\f(CW$t\fR\->move($ix, \f(CW$p\fR)" 4
.IX Item "$t->move($ix, $p)"
Moves the point at index \f(CW$ix\fR to the new given position readjusting
the tree structure accordingly.
.ie n .IP "($ix, $d) = $t\->find_nearest_vector($p, $max_d, @but_ix)" 4
.el .IP "($ix, \f(CW$d\fR) = \f(CW$t\fR\->find_nearest_vector($p, \f(CW$max_d\fR, \f(CW@but_ix\fR)" 4
.IX Item "($ix, $d) = $t->find_nearest_vector($p, $max_d, @but_ix)"
.PD 0
.ie n .IP "($ix, $d) = $t\->find_nearest_vector($p, $max_d, \e%but_ix)" 4
.el .IP "($ix, \f(CW$d\fR) = \f(CW$t\fR\->find_nearest_vector($p, \f(CW$max_d\fR, \e%but_ix)" 4
.IX Item "($ix, $d) = $t->find_nearest_vector($p, $max_d, %but_ix)"
.PD
Find the nearest vector for the given point \f(CW$p\fR and returns its
index and the distance between the two points (in scalar context the
index is returned).
.Sp
If \f(CW$max_d\fR is defined, the search is limited to the points within that distance
.Sp
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.
.ie n .IP "@ix = $t\->find_nearest_vector_all_internal" 4
.el .IP "\f(CW@ix\fR = \f(CW$t\fR\->find_nearest_vector_all_internal" 4
.IX Item "@ix = $t->find_nearest_vector_all_internal"
Returns the index of the nearest vector from the tree.
.Sp
It is equivalent to the following code (though, it uses a better
algorithm):
.Sp
.Vb 3
\&  @ix = map {
\&            scalar $t\->nearest_vector($t\->at($_), undef, $_)
\&        } 0..($t\->size \- 1);
.Ve
.ie n .IP "$ix = $t\->find_farthest_vector($p, $min_d, @but_ix)" 4
.el .IP "\f(CW$ix\fR = \f(CW$t\fR\->find_farthest_vector($p, \f(CW$min_d\fR, \f(CW@but_ix\fR)" 4
.IX Item "$ix = $t->find_farthest_vector($p, $min_d, @but_ix)"
Find the point from the tree farthest from the given \f(CW$p\fR.
.Sp
The optional argument \f(CW$min_d\fR specifies a minimal distance. Undef is
returned when not point farthest that it is found.
.Sp
\&\f(CW@but_ix\fR specifies points that should not be considered when looking
for the farthest point.
.ie n .IP "$ix = $t\->find_farthest_vector_internal($ix, $min_d, @but_ix)" 4
.el .IP "\f(CW$ix\fR = \f(CW$t\fR\->find_farthest_vector_internal($ix, \f(CW$min_d\fR, \f(CW@but_ix\fR)" 4
.IX Item "$ix = $t->find_farthest_vector_internal($ix, $min_d, @but_ix)"
Given the index of a point on the tree this method returns the index
of the farthest vector also from the tree.
.ie n .IP "@k = $t\->k_means_start($n)" 4
.el .IP "\f(CW@k\fR = \f(CW$t\fR\->k_means_start($n)" 4
.IX Item "@k = $t->k_means_start($n)"
This method uses the internal tree structure to generate a set of
point that can be used as seeds for other \f(CW\*(C`k_means\*(C'\fR methods.
.Sp
There isn't any guarantee on the quality of the generated seeds, but
the used algorithm seems to perform well in practice.
.ie n .IP "@k = $t\->k_means_step(@k)" 4
.el .IP "\f(CW@k\fR = \f(CW$t\fR\->k_means_step(@k)" 4
.IX Item "@k = $t->k_means_step(@k)"
Performs a step of the Lloyd's
algorithm <http://en.wikipedia.org/wiki/Lloyd%27s_algorithm> for
k\-means calculation.
.ie n .IP "@k = $t\->k_means_loop(@k)" 4
.el .IP "\f(CW@k\fR = \f(CW$t\fR\->k_means_loop(@k)" 4
.IX Item "@k = $t->k_means_loop(@k)"
Iterates until the Lloyd's algorithm converges and returns the final
means.
.ie n .IP "@ix = $t\->k_means_assign(@k)" 4
.el .IP "\f(CW@ix\fR = \f(CW$t\fR\->k_means_assign(@k)" 4
.IX Item "@ix = $t->k_means_assign(@k)"
Returns for every point in the three the index of the cluster it
belongs to.
.ie n .IP "@ix = $t\->find_in_ball($z, $d, $but)" 4
.el .IP "\f(CW@ix\fR = \f(CW$t\fR\->find_in_ball($z, \f(CW$d\fR, \f(CW$but\fR)" 4
.IX Item "@ix = $t->find_in_ball($z, $d, $but)"
.PD 0
.ie n .IP "$n = $t\->find_in_ball($z, $d, $but)" 4
.el .IP "\f(CW$n\fR = \f(CW$t\fR\->find_in_ball($z, \f(CW$d\fR, \f(CW$but\fR)" 4
.IX Item "$n = $t->find_in_ball($z, $d, $but)"
.PD
Finds the points inside the tree contained in the hypersphere with
center \f(CW$z\fR and radius \f(CW$d\fR.
.Sp
In scalar context returns the number of points found. In list context
returns the indexes of the points.
.Sp
If the extra argument \f(CW$but\fR is provided. The point with that index
is ignored.
.ie n .IP "@ix = $t\->ordered_by_proximity" 4
.el .IP "\f(CW@ix\fR = \f(CW$t\fR\->ordered_by_proximity" 4
.IX Item "@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.
.SS "k\-means"
.IX Subsection "k-means"
The module can be used to calculate the k\-means of a set of vectors as follows:
.PP
.Vb 2
\&  # inputs
\&  my @v = ...; my $k = ...;
\&  
\&  # k\-mean calculation
\&  my $t = Math::Vector::Real::kdTree\->new(@v);
\&  my @means = $t\->k_means_start($k);
\&  @means = $t\->k_means_loop(@means);
\&  @assign = $t\->k_means_assign(@means);
\&  my @cluster = map [], 1..$k;
\&  for (0..$#assign) {
\&    my $cluster_ix = $assign[$_];
\&    my $cluster = $cluster[$cluster_ix];
\&    push @$cluster, $t\->at($_);
\&  }
\&  
\&  use Data::Dumper;
\&  print Dumper \e@cluster;
.Ve
.SH "SEE ALSO"
.IX Header "SEE ALSO"
Wikipedia k\-d Tree entry <http://en.wikipedia.org/wiki/K-d_tree>.
.PP
K\-means filtering algorithm <https://www.cs.umd.edu/~mount/Projects/KMeans/pami02.pdf>.
.PP
Math::Vector::Real
.SH "COPYRIGHT AND LICENSE"
.IX Header "COPYRIGHT AND LICENSE"
Copyright (C) 2011\-2014 by Salvador Fandin\*~o <sfandino@yahoo.com>
.PP
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.