ボロノイ図・各種グラフ (HTML5版 ver 1.0)

※このページではHTML5を使用しています

• 白いフィールド上でクリックすると、そこに点が現れます。 ただし、複数の点を重ねることは出来ません。
• 幾つか点を描いてから 描画 ボタンを押すと、図形が描画されます。
• 描画する図形はメニューの中から選択出来ます。

  ボロノイ図:	Voronoi diagram and Delaunay diagram
  	青線でボロノイ図を、 赤線でドロネー図を描きます。
  ガブリエルグラフ :	Gabriel graph
  	赤線でガブリエルグラフを描きます。
  相対近傍グラフ :	Relative Neighborhood graph
  	赤線で相対近傍グラフを描きます。
  最近傍グラフ :	Nearest neighborhood graph
  	赤線で最近傍グラフを描きます。 線分の向きも表示します。
  最小全域木 :	Minimum Spanning Tree
  	赤線で最小全域木を描きます。

• 描画した後は、メニューで図形を選びなおして表示させることは出来ますが、 点を加えることは出来ません。
• クリア ボタンを押せば、 点を消去して再び点を書き加えることが出来ます。
• キーボードの 5 または c で 描画、 d で点の 消去 になります。

ところでボロノイ図とか何とかって何？

尚、このプログラムは計算時間が点の数の3乗に比例する単純なアルゴリズムを使っています。 より効率の良いアルゴリズムを知りたい方は、下記の参考文献等をご覧ください。

参考文献
計算幾何学と地理情報処理 第2版 共立出版
FORTRAN 計算幾何プログラミング 杉原厚吉著 岩波書店