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