このデモは、指定された多角形に対するボロノイ図を計算します。 青い線で描いた図形がそのボロノイ図です。 緑の図形は、多角形を構成している点のボロノイ図です。

　多角形の頂点をマウスでドラッグして移動させると、 それに応じてボロノイ図も計算しなおされます。 ただし、多角形が互いに交差してはいけません。 なぜなら、多角形が交差する場合は，ボロノイ図が定義できないからです。 でもこのプログラムは、多角形が交差しても何か図形を描きます。 この図形をよく観察すると，このプログラムでどのように多角形ボロノイ図を計算しているかがわかってくるでしょう。

　このプログラムの詳しい内容に関しては、次の文献を参照してください。

K. Sugihara: Approximation of generalized Voronoi diagrams by ordinary Voronoi diagrams. Computer Vision, Graphics, and Image Processing --- Graphical Models and Image Processing, vol. 55 (1993), pp.522-531.

杉原：FORTRAN計算幾何プログラミング. 岩波書店, 1998.

杉原厚吉(東大）

---

このデモは 東京大学 杉原厚吉 教授 のプログラムを利用しています。