Math::ConvexHull - Calculate convex hulls using Graham's scan (n*log(n))

Location : Home > Languages > Perl > Package
Title : Math::ConvexHull

　Math::ConvexHull - グラハム探索を用いた凸包の計算

use Math::ConvexHull qw/convex_hull/;
$hull_array_ref = convex_hull(\@points);

説明

　Math::ConvexHull は２次元空間の点集合から凸包（convex hulls）を計算する簡単なモジュールである。 O(n*log(n)) 規模の計算量で、任意の点集合から convex hulls を求めるアルゴリズムの中では最速であるグラハム探索（Graham's scan）として知られるアルゴリズムの真正直な実装である。凸包の部分とならない点を除外する方法がいくつかあるが、これは将来のバージョンで実装するかも知れないししないかも知れない。

エクスポート

　デフォルトではなし。しかし標準的な Exporter の意味で、あなたの名前空間にエクスポートされた convex_hull() サブルーティンを選択することもできる。

convex_hull() サブルーティン

　Math::ConvexHull は、驚くなかれ、ただ１つのサブルーティン convex_hull() を実装しているだけである。convex_hull() は点の配列参照を引数とし、 convex_hull() を形成する点の配列参照を返す。
　この文脈では、点は x 座標と y 座標からなる配列である。だから convex_hull() を利用した使用例は以下のようになる。

use Data::Dumper;
use Math::ConvexHull qw/convex_hull/;

print Dumper convex_hull(
	[
		[0,0],     [1,0],
		[0.2,0.9], [0.2,0.5],
		[0,1],     [1,1],
	]
);

# [0,0], [1,0], [0,1], [1,1] を出力。

　convex_hull() はdoes not return点のコピーを返すのではなく、それらが通る配列参照を返すことに注意してほしい。

著者

　Steffen Mueller, <hull-module at steffen-mueller dot net>

参考資料

　本モジュールの新しいバージョンは http://steffen-mueller.net または CPAN で入手可能である。
　自分のCSノートからアルゴリズムを実装した後に、 Orwant et al, "Mastering Algorithms with Perl" のドイツ語訳でまったく同じ実装を見つけた。彼らのコードのほうが私のより読みやすそうなので、モジュールのソースコードの処理がわかりにくいならその本を見ることをお勧めする。

【解説】

凸包（convex hulls）とは、平面上のn個の点に対し、そのn個の点を境界または内部に含むような最少の凸角形で、その領域内の任意の2点を結ぶ線分もその領域に含まれるものである。

Updated : 2006/07/05