view release on metacpan or  search on metacpan

lib/Algorithm/Points/MinimumDistance.pm  view on Meta::CPAN

=head1 SYNOPSIS

  use Algorithm::Points::MinimumDistance;

  my @points = ( [1, 4], [3, 1], [5, 7] );
  my $dists = Algorithm::Points::MinimumDistance->new( points => \@points );

  foreach my $point (@points) {
      print "($point->[0], $point->[1]: Nearest neighbour distance is "
          . $dists->distance( point => $point ) . "\n";
  }

  print "Smallest distance between any two points is "
      . $dists->min_distance . "\n";

=head1 METHODS

=over 4

=item B<new>

  my @points = ( [1, 4], [3, 1], [5, 7] );
  my $dists = Algorithm::Points::MinimumDistance->new( points  => \@points,
                                                       boxsize => 2 );

C<points> should be an arrayref containing every point in your set.
The representation of a point is as an N-element arrayref where N is
the number of dimensions in which we are working.  There is no check
that all of your points have the right dimension.  Whatever dimension
the first point has is assumed to be the dimension of the space.  So
get it right.

C<boxsize> defaults to 20.

=cut

sub new {
    my ($class, %args) = @_;
    my @points = @{ $args{points} };
    my $dim = scalar @{ $points[0] };
    my $boxsize = $args{boxsize} || 20;

    # Precomputation for working out all boxes adjacent to a given box
    # (a point will be in all regions centred on its box or the
    # adjacent ones).
    # To find an adjacent box, vector-add one of these entries to it,
    # eg [1, 1] + [2, 0] - with a boxsize of 2, [3, 1] is adjacent to [1, 1].
    my @offsets = ( [ -$boxsize ], [ 0 ] , [ $boxsize ] );
    foreach (2..$dim) {
        @offsets = map { [ @$_, -$boxsize ], [ @$_, 0 ], [ @$_, $boxsize] }
                       @offsets;
    }

    my $self = { dimensions => $dim,
                 points     => \@points,
                 boxsize    => $boxsize,
                 offsets    => \@offsets,
                 regions    => { },
                 distances  => { }
	       };
    bless $self, $class;
    $self->_work_out_distances;

    return $self;
}

=item B<box>

  my @box = $nn->box( [1, 2] );

Returns the identifier of the box that the point lives in.
A box is labelled by its "bottom left-hand" corner point.

=cut

sub box {
    my ($self, $point) = @_;
    my @box = map { $_ - ($_ % $self->{boxsize}) } @$point;
    return @box;
}

sub _offsets {
    my $self = shift;
    return @{ $self->{offsets} };
}

# Accessor for the region centred on the box $args{centre}.  Returns a ref to
# an array of the points that are in that region.
sub region {
    my ($self, %args) = @_;
    my @centre = @{$args{centre}};
    my $key = join(",", @centre);
    my $regions = $self->{regions};
    $regions->{$key} ||= [];
    return $regions->{$key};
}

# Shevek says: "This is where the CPU time goes, but, gentle reader,
# please note that the complexity is LINEAR in the number of
# points. This is shit.  It's also trivial, so do it in XS."
# Kake says: "I don't speak XS yet."

sub _hash {
    my ($self, $point) = @_;

    # Compute the box in which $point lives.
    my @home_box = $self->box($point);

    # $point lives in the region centred on this box, plus all surrounding
    # regions.  Push it into each of these regions.  A region is
    # identified by the box at its centre.
    foreach my $delta ( $self->_offsets ) {
        my @centre = map { $delta->[$_] + $home_box[$_] } (0..$#home_box);
        my $region = $self->region( centre => \@centre );
        push @$region, $point;
    }
}

sub _work_out_distances {
    my $self = shift;
    my $points = $self->{points};