NAME
    Algorithm::Points::MinimumDistance - Works out the distance from each
    point to its nearest neighbour. Kinda.

DESCRIPTION
    Given a set of points in N-dimensional Euclidean space, works out for
    each point the distance to its nearest neighbour (unless its nearest
    neighbour isn't very close). The distance metric is a method; subclass
    and override it for non-Euclidean space.

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";

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

        "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.

        "boxsize" defaults to 20.

    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.

    distance
          my $nn = Algorithm::Points::MinimumDistance->new( ... );
          my $nn_dist = $nn->distance( point => [1, 4] );

        Returns the distance between the specified point and its nearest
        neighbour. The point should be one of your original set. There is no
        check that this is the case. Note that if a point has no
        particularly close neighbours, then "boxsize" will be returned
        instead.

    min_distance
          my $nn = Algorithm::Points::MinimumDistance->new( ... );
          my $nn_dist = $nn->min_distance;

        Returns the minimum nearest-neighbour distance for all points in the
        set. Or "boxsize" if none of the points are close to each other.

ALGORITHM
    We use the hash as an approximate conservative metric to basically do
    clipping of space. A box is one cell of the space defined by the grid
    size. A region is a box and all the neighbouring boxes in all
    directions, i.e. all the boxes b such that d(b, c) <= 1 in the
    d-infinity metric Noting that d(b, c) is always an integer in this case.

      +-+-+-+-+-+
      | | | | | |
      +-+-+-+-+-+
      | |x|x|x| |
      +-+-+-+-+-+
      | |x|b|x| |
      +-+-+-+-+-+
      | |x|x|x| |
      +-+-+-+-+-+
      | | | | | |
      +-+-+-+-+-+ 

    Now all points outside the region defined by the box b and the
    neighbours x can not be within maximum radius $C of any point in box b.

    So we reverse the stunt and shove any point in box b into the hash lists
    for all boxes b and x so that when testing a point in any box, we have a
    list of all points in that box and any neighbouring boxes (the region).

AUTHOR
    Algorithm by Shevek, modularisation by Kake Pugh (kake@earth.li).

COPYRIGHT
         Copyright (C) 2003 Kake Pugh.  All Rights Reserved.

    This module is free software; you can redistribute it and/or modify it
    under the same terms as Perl itself.

CREDITS
    Shevek is utterly fab for telling me how to solve this problem. Greg
    McCarroll is also fab for telling me what to call the module.