(Library) Delaunay三角形メッシュ生成

(C) Takeshi Horinouchi

LICENSE: Ruby's

Delaunay の三角形分割 (Delaunay traingulation) というのは、平面上に分 布する点から三角形メッシュを生成する手法です。ゆがみの少ないメッシュを 生成するため、各三角形の外接円内にメッシュを構成する他の点が入らないよ うにします。円上に4点以上並ぶ（という一意には選びようのない）ケースを 除き、一意に決まります。この拡張ライブラリでは、基本的な逐次加点法 (incremental method)を実行します。これは頂点数 n に対し、 O(n**2) の計算量の手法です。この部分はCで書いてますので、高速です。 なお、n が非常に大きい場合向けの、 分割統治(divide and counquer)は行いません。悪しからず。

三角形を表すクラスは TriangleI と名付けてます。ちょっと変な名前で、自 分でも反省してますが、頂点に index が振ってあってその index ベースで点 を identify することから、I がついてます。

TriangleI-2008-02-01.tar.gz

資源を展開して、トップディレクトリに cd して、次のようにします。

% ruby extconf.rb
% make
% make install

サンプルが test_trianglei.rb にあります。そこから抜粋すると、

require "narray"
require "trianglei"
px = NArray[0.0, 3.0, 1.0, 1.0, 3.5]
py = NArray[0.0, 1.0, 4.0, 5.0, 4.0]
tary = TriangleI.delaunay(px, py)

のようにすることで、tary は３角形の列を納めた配列となります。 test_trianglei.rb は、得られた結果の図示もします (dcl_001.pngが その結果です)。