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 (
[email protected]).
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.
