.\" Automatically generated by Pod::Man 4.14 (Pod::Simple 3.42) .\" .\" 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 >0, 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 .\" ======================================================================== .\" .IX Title "Math::Vector::Real::kdTree 3pm" .TH Math::Vector::Real::kdTree 3pm "2022-06-15" "perl v5.34.0" "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_nearest_vector_in_box($p, $a, $b, $max_d, @but_ix)" 4 .el .IP "\f(CW$ix\fR = \f(CW$t\fR\->find_nearest_vector_in_box($p, \f(CW$a\fR, \f(CW$b\fR, \f(CW$max_d\fR, \f(CW@but_ix\fR)" 4 .IX Item "$ix = $t->find_nearest_vector_in_box($p, $a, $b, $max_d, @but_ix)" .PD 0 .ie n .IP "$ix = $t\->find_nearest_vector_in_box($p, $a, $b, $max_d, \e%but_ix)" 4 .el .IP "\f(CW$ix\fR = \f(CW$t\fR\->find_nearest_vector_in_box($p, \f(CW$a\fR, \f(CW$b\fR, \f(CW$max_d\fR, \e%but_ix)" 4 .IX Item "$ix = $t->find_nearest_vector_in_box($p, $a, $b, $max_d, %but_ix)" .PD Returns the nearest vector for the given point from those that are also inside the box defined by \f(CW$a\fR and \f(CW$b\fR. .Sp The other arguments have the same meaning as for the method \&\f(CW\*(C`find_nearest_vector\*(C'\fR. .ie n .IP "$ix = $t\->find_nearest_vector_in_box_chebyshev($p, $a, $b, $max_d, @but_ix)" 4 .el .IP "\f(CW$ix\fR = \f(CW$t\fR\->find_nearest_vector_in_box_chebyshev($p, \f(CW$a\fR, \f(CW$b\fR, \f(CW$max_d\fR, \f(CW@but_ix\fR)" 4 .IX Item "$ix = $t->find_nearest_vector_in_box_chebyshev($p, $a, $b, $max_d, @but_ix)" .PD 0 .ie n .IP "$ix = $t\->find_nearest_vector_in_box_chebyshev($p, $a, $b, $max_d, \e%but_ix)" 4 .el .IP "\f(CW$ix\fR = \f(CW$t\fR\->find_nearest_vector_in_box_chebyshev($p, \f(CW$a\fR, \f(CW$b\fR, \f(CW$max_d\fR, \e%but_ix)" 4 .IX Item "$ix = $t->find_nearest_vector_in_box_chebyshev($p, $a, $b, $max_d, %but_ix)" .PD This method is similar to \f(CW\*(C`find_nearest_vector_in_box\*(C'\fR but using the Chebyshev metric. .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 "($ix0, $ix1, $d) = $t\->find_two_nearest_vectors" 4 .el .IP "($ix0, \f(CW$ix1\fR, \f(CW$d\fR) = \f(CW$t\fR\->find_two_nearest_vectors" 4 .IX Item "($ix0, $ix1, $d) = $t->find_two_nearest_vectors" This method returns the indexes of two vectors from the three such that the distance between them is minimal. The distance is returned as the third output value. .Sp In scalar context, just the distance is returned. .ie n .IP "@k = $t\->k_means_seed($n)" 4 .el .IP "\f(CW@k\fR = \f(CW$t\fR\->k_means_seed($n)" 4 .IX Item "@k = $t->k_means_seed($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 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\->find_in_box($a, $b, $but)" 4 .el .IP "\f(CW@ix\fR = \f(CW$t\fR\->find_in_box($a, \f(CW$b\fR, \f(CW$but\fR)" 4 .IX Item "@ix = $t->find_in_box($a, $b, $but)" .PD 0 .ie n .IP "$n = $t\->find_in_box($a, $b, $but)" 4 .el .IP "\f(CW$n\fR = \f(CW$t\fR\->find_in_box($a, \f(CW$b\fR, \f(CW$but\fR)" 4 .IX Item "$n = $t->find_in_box($a, $b, $but)" .PD Finds the points inside the tree contained in the axis-aligned box defined by two opposite vertices \f(CW$a\fR and \f(CW$b\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_seed($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 . .PP K\-means filtering algorithm . .PP Math::Vector::Real .SH "COPYRIGHT AND LICENSE" .IX Header "COPYRIGHT AND LICENSE" Copyright (C) 2011\-2015 by Salvador Fandiño .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.