読者です 読者をやめる 読者になる 読者になる

どせいたんさき。

ナスダヨー

gnuplot の陰線処理でボロノイ図を作成する

ボロノイ図を作成する

ボロノイ図とは何か?については Wikpedia を参照のこと.

このエントリでは陰線処理を用いてボロノイ図を作成する方法を紹介する.この手法は『データ構造とアルゴリズム』において「カーペンターズアルゴリズム」の 1 つとして紹介されていたものである.まず,ボロノイ図の母点を頂点とする円錐を 3 次元空間上に作成し,陰線処理を有効にしたした上で真上からの視点で描画する.すると描画されている円錐がそのままボロノイ領域になっている,という仕組みである.

実際に作成したボロノイ図のサンプルを以下に貼り付ける.


コード

使用した gnuplot のコードは gist に投稿した.

参考資料