.\" Automatically generated by Pod::Man 2.25 (Pod::Simple 3.16)
.\"
.\" 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" ''
'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.
.ie \nF \{\
.    de IX
.    tm Index:\\$1\t\\n%\t"\\$2"
..
.    nr % 0
.    rr F
.\}
.el \{\
.    de IX
..
.\}
.\"
.\" 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 "2012-06-18" "perl v5.14.2" "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_neighbor(V(0, 0, 0, 0));
\&
\&  say "nearest neighbor is $ix, $v[$ix]";
.Ve
.SH "DESCRIPTION"
.IX Header "DESCRIPTION"
This module implements a kd-Tree data structure in Perl and some
related algorithms.
.PP
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 kdTree containing the gived points.
.ie n .IP "$t\->insert($p)" 4
.el .IP "\f(CW$t\fR\->insert($p)" 4
.IX Item "$t->insert($p)"
Inserts the given point into the kdTree.
.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_neighbor($p, $max_d, $but_ix)" 4
.el .IP "($ix, \f(CW$d\fR) = \f(CW$t\fR\->find_nearest_neighbor($p, \f(CW$max_d\fR, \f(CW$but_ix\fR)" 4
.IX Item "($ix, $d) = $t->find_nearest_neighbor($p, $max_d, $but_ix)"
Find the nearest neighbor 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
If \f(CW$but_ix\fR is defined, the point with the given index is not considered.
.ie n .IP "@ix = $t\->find_nearest_neighbor_all_internal" 4
.el .IP "\f(CW@ix\fR = \f(CW$t\fR\->find_nearest_neighbor_all_internal" 4
.IX Item "@ix = $t->find_nearest_neighbor_all_internal"
Returns the index of the nearest neighbor for every point inside the tree.
.Sp
It is equivalent to (though, internally, it uses a better algorithm):
.Sp
.Vb 3
\&  @ix = map {
\&            scalar $t\->nearest_neighbor($t\->at($_), undef, $_)
\&        } 0..($t\->size \- 1);
.Ve
.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.
.SH "SEE ALSO"
.IX Header "SEE ALSO"
http://en.wikipedia.org/wiki/K\-d_tree <http://en.wikipedia.org/wiki/K-d_tree>
.PP
Math::Vector::Real
.SH "COPYRIGHT AND LICENSE"
.IX Header "COPYRIGHT AND LICENSE"
Copyright (C) 2011, 2012 by Salvador FandiA\*~Xo <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.