Voronoi分割とDelaunay三角形網

Voronoi分割

Voronoi: ボロノイ、20世紀初めのロシアの数学者

平面内の領域を、「もよりの」(距離がいちばん近い)データ点ごとに 区分する。つまり、データ点の垂直二等分線で区分することになるが、 全部の組み合わせの垂直二等分線が使われるわけではない。

立地・配分問題でよく使われる。

また、水文学で降水量の集計法として使われるThiessen(ティーセン)法 は、Voronoi多角形の面積の重みをつけて集計することにあたる。

Delaunay三角形網

Delaunay: ドロネー[この読みは杉原厚吉先生の本に従った]、ソ連の数 学者。

データ点でかこまれた領域を、各データ点を頂点とする三角形網で 区分する方法のうち、三角形の最小の内角を最大にする (三角形をなるべく細長くしない)という基準に従って最適なもの。

Voronoi多角形が相互に接する辺があるようなデータ点どうしを結ぶ ことに相当している。

例: Voronoi分割(色分け)とDelanuy三角形網(白線)

(この例の計算と作図のプログラムの説明は 「GKSによるデータの可視化」教材の 「格子点でないデータの扱い: 三角形分割」参照。)


2000-05-08, 2001-04-20, 2005-08-10
増田 耕一

[目次へ]