多角形のVoronoi Diagram

著者: Philippe PIGNON, 電総研ゲスト研究者

このプログラムは，Common Lispで書かれている。 "A sweepline algorithm for Voronoi diagrams", Proceedings of the 2nd Annual ACM symposium on computational geometry, 1986, 313-322.を 手法として用い、 多角形の場合への応用を行った。これは，サンプルプログラム付きの簡単な説明である。 このプログラムは，ETLのEuslisp環境で書かれているため， 画像への出力もサポートしている。 どのCommon Lisp上でも使用することはできるが， utilities.lで与えられている画像への関数を自分のディスプレイ環境へ 合うように書き換える必要がある。この節の最後にその関数を示す。

目的:

多角形の集合のvoronoi diagramの計算を行う。 語彙を理解するために上記の文献を読んで、使用してください。 ここでは、このプログラムに対する説明をしません。

入力:

多角形のリストと囲むための枠は，次のように定義する。

DATA= (
       (x11 y11 x12 y12 x13 y13 ...) first polygon,
                                     counterclocwise enumeration of vertices
       (x21 y21 x22 y22 x23 y23 ...) second polygon
               ... 
       (xn1 yn1 xn2 yn2 xn3 yn3 ...) nth polygon
	     
       (xf1 yf1 xf2 yf2 xf3 yf3 xf4 yf4) enclosing frame
      )

囲む枠は，DATA内のどの位置にも配置することができる。また， 内部と外部が矛盾しないように時計方向の順番でなければならない。 多角形は交差の無い簡単な図形でなければならない。 一直線あるいは平坦なエッジは受け付けない。 独立した点あるいは線分も受け付けない。

出力:

*diagram*:2重に接続されたエッジリストのリスト (utilities.lファイルを参照)を返す。それぞれのエッジは，symbolであり，次に示す ようなfieldを含むproperty-listを持っている。

(start <pointer to a vertex>)
       (end <pointer to a vertex>)
       (pred <pointer to an edge>)
       (succ <pointer to an edge>)
       (left <pointer to a site>)
       (right <pointer to a site>)
       (type <:endpoint or :point-point or :segment-segment or :point-segment>)
       (outflag <t or nil>)

vertexは，symbolで"pos"fieldを含むproperty-listを持つ。 このfieldは，cons(x,y)を含み，vertexの平面座標を示す。 predとsuccのfieldは，decl形式にしたがって反時計方向の 前者と後者を与える(ShamosとPreparataの, Computational Geometry: An introduction, 1985, pp 15-17を参照)。 siteもsymbolであり，関連した情報を含むproperty-listを持つ。 siteは，元の入力データを記述しており，多角形の頂点であるpoint あるいは多角形のエッジであるsegmentを持つ。

typeは，2等分線の中点であり，それを分割するsiteの型より 決定される。 規約により，外側はstart-endエッジの右側である。 voronoi diagramは，2等分線の内部と同様に外側を計算する。 必要とするoutflagを保つためにoutflagをソートする。

サンプル:

サンプルプログラムを実行するためには，以下のようなステップを実施してください。

1. 自分の環境に以下のプログラムをコピーする。
   

   utilities.l	幾何学ユーティリティ関数とeusxの画像出力関数
   polygonalvoronoi.l	プログラム本体
   testdata.l	上記の書式によるデモデータ

2. もし，Euslispを使用しないなら，命令にしたがってutilities.lを書き換え， "compatibility package"を修正する。。
3. 以下の3つのファイルをコンパイルしてロードするか、あるいはそのままロードする。
   

   utilities.l
   polygonalvoronoi.l
   testdata.l	上記の書式によるデモデータを含んでいる。

4. (pv demoworld)でデモデータ上でプログラムが実行される。 グローバル変数*diagram*には，voronoi diagramの2等分線が含まれている。

eusx(Xwindowインターフェースを持つEuslisp)のもとでは，以下の命令でdiagramの結果を画面上に表示することができる。

       (make-display)          ;;Initializes the *display* window object
       (dps demoworld *thick*) ;; Shows original data in thick lines
       (dbs *diagram*)         ;; Shows the result

pv data [関数]

上記の書式で書かれたdataから多角形のvoronoi diagramを計算する。