Location : Home > Languages > Perl > Package
Title : Algorithm::Points::MinimumDistance
 		Toolbox Logo

名称

　Algorithm::Points::MinimumDistance - 最も近い近傍への距離を計算

説明

　所与の n 次元ユークリッド空間内の点の集合に対し、各点についての最近傍点を求める（最近傍点がすぐ近くにいなくても）。距離計量はメソッドであり、非ユークリッド空間に対してはオーバーライドする。

概要

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

メソッド

new

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

　points は対象となる全ての点を含む配列参照でなければならない。
　点の表現は N-要素の配列参照であり、N は次元の数である。全ての点が正しい次元にあるかを確認はしていない。最初の点の次元が全ての点の次元であるとみなす。そのように設定すること。
　boxsize のデフォルト値は 20 である。

box

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

　点を記述するボックスの識別子を返す。ボックスは左下隅からラベル付けされる。

distance

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

　指定した点とその最近傍点までの距離を返す。その点は最初の点集合に含まれていなければならない。この条件に関する確認はない。点が最近傍点を持たなければ替わりに boxsize を返す。

min_distance

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

　点集合における、最小最近傍距離を返す。または互いに近い点がなければ boxsize を返す。

アルゴリズム

　空間を切り抜くための適当な古典的計量としてハッシュを用いている。box を格子サイズで定義された空間内のセルのこと、region は box とその全方向の隣接 box とする。すなわち以下の条件を満たすような box を考えるとよい。

 d-∞ 計量において  d(b, c) <= 1

　d(b, c) はこの場合全て整数値であることに留意すること。

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

　Now all points outside the region defined by the box b 及びその近傍 x で定義される region の全ての外部の点は b から最大半径 $C 内には入れない。
　逆に box 内の点をテストするときに b 及び x のハッシュリストの中に box b の点を入れる。こうして box 内の全ての点及びその近傍 box（region）のリストを作成する。

著者

　アルゴリズムは Shevek, 実装は Kake Pugh, （kake@earth.li>)

著作権

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

　本モジュールはフリーソフトウェアであり、 Perl 本体と同等の条件で修正／再配布してもよい。

謝辞

　Shevek は極めて優秀で問題の解法を教えてくれた。Greg McCarroll も優秀で、モジュールで何を呼び出すべきかを教えてくれた。

Toolbox Logo
 Updated : 2006/09/27