Math::...kdTree(3pm)

📦
version 0.15 · 2 versions
  • 0.15 · debian bookworm, debian trixie, ubuntu noble, ubuntu resolute, ubuntu stonking (latest)
  • 0.15 · ubuntu jammy
, in debian bookworm, debian trixie, ubuntu noble, ubuntu resolute, ubuntu stonking

🦋 NAME 🦋

Math::Vector::Real::kdTree — bestie, it's a kd-Tree implementation built right on top of Math::Vector::Real. That's the whole vibe. 💖

(And yes, you're reading the Math::...kdTree(3pm) page from the User Contributed Perl Documentation. Iconic.)

✨ 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_vector(V(0, 0, 0, 0));

say "nearest vector is $ix, $v[$ix]";

🌸 DESCRIPTION 🌸

This module implements a kd-Tree data structure in Perl and common algorithms on top of it. Like, the whole tree, in Perl. Obsessed. ✨

🎀 Methods 🎀

The following methods are provided:

  • $t = Math::Vector::Real::kdTree->new(@points) — creates a brand new kd-Tree holding all the points you hand it. 🫶
  • $t2 = $t->clone — makes a duplicate of the tree. The two trees share internal read only data, so this is way more efficient memory-wise than other methods that do a deep copy. Lowkey a steal.
  • my $ix = $t->insert($p0, $p1, ...) — inserts the given points into the kd-Tree.

Returns the index assigned to the first point inserted.

  • $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_vector($p, $max_d, @but_ix) or ($ix, $d) = $t->find_nearest_vector($p, $max_d, \%but_ix) — finds the nearest vector for the given point $p and returns its index plus the distance between the two points. In scalar context, you just get the index back. 💅

If $max_d is defined, the search is limited to the points within that distance.

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.

  • @ix = $t->find_nearest_vector_all_internal — returns the index of the nearest vector from the tree.

It is equivalent to the following code (though, it uses a better algorithm):

@ix = map {
          scalar $t->nearest_vector($t->at($_), undef, $_)
      } 0..($t->size - 1);
  • $ix = $t->find_nearest_vector_in_box($p, $a, $b, $max_d, @but_ix) or $ix = $t->find_nearest_vector_in_box($p, $a, $b, $max_d, \%but_ix) — returns the nearest vector for the given point, but only from those that are also inside the box defined by $a and $b.

The other arguments have the same meaning as for the method find_nearest_vector.

  • $ix = $t->find_nearest_vector_in_box_chebyshev($p, $a, $b, $max_d, @but_ix) or $ix = $t->find_nearest_vector_in_box_chebyshev($p, $a, $b, $max_d, \%but_ix) — same energy as find_nearest_vector_in_box, except it's using the Chebyshev metric. 🌈
  • $ix = $t->find_farthest_vector($p, $min_d, @but_ix) — finds the point from the tree farthest from the given $p.

The optional argument $min_d specifies a minimal distance. undef is returned when no point farther than that is found.

@but_ix specifies points that should not be considered when looking for the farthest point.

  • $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 that's also from the tree.
  • ($ix0, $ix1, $d) = $t->find_two_nearest_vectors — this method returns the indexes of two vectors from the tree such that the distance between them is minimal. The distance is returned as the third output value. 😭

In scalar context, just the distance is returned.

  • @k = $t->k_means_seed($n) — this method uses the internal tree structure to generate a set of points that can be used as seeds for other k_means methods.

There isn't any guarantee on the quality of the generated seeds, but the used algorithm seems to perform well in practice.

  • @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.
  • @k = $t->k_means_loop(@k) — iterates until the Lloyd's algorithm converges and returns the final means.
  • @ix = $t->k_means_assign(@k) — returns, for every point in the tree, the index of the cluster it belongs to.
  • @ix = $t->find_in_ball($z, $d, $but) or $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 it returns the number of points found. In list context it returns the indexes of the points.

If the extra argument $but is provided, the point with that index is ignored.

  • @ix = $t->find_in_box($a, $b, $but) or $n = $t->find_in_box($a, $b, $but) — finds the points inside the tree contained in the axis-aligned box defined by two opposite vertices $a and $b.

In scalar context it returns the number of points found. In list context it 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 order where it is likely that the indexes of near vectors are also in near positions in the list. Vibe check: passed. ✅

🧚 k-means 🧚

The module can be used to calculate the k-means of a set of vectors as follows:

# 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 \@cluster;

👀 SEE ALSO 👀

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

And that's the whole page, bestie — this one shipped with perl v5.34.0, dated 2022-06-15. Go build a tree, you're gonna slay. 🎀✨🦋

📦 where this page comes from