著者

稲垣 宏 杉原 厚吉

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.1994, no.26, pp.41-48, 1994-03-17

被引用文献数

1

---

筆者らは,文献[1][2]において,位相構造を優先することで数値的安定化を図った3次元Voronoi図構成法を提案した.また,文献[3]では,このアルゴリズムを利用して,双対図形である3次元Delaunay図を生成する方法を提案した.本稿では,位相構造を優先させたVoronoi図構成法が,制約つきDelaunay図の構成にも利用できることを示す.ここで提案する算法では,制約を満たすように数値判定をねつ造しているために,正しいボロノイ図は出力されない.しかし,その双対を求めると,制約つきDelaunay図になっているのである.また,本算法を適用した3次元の制約つきDelaunay図構成プログラムを作成し,計算機実験により,その有効性を実証した.In our previous paper[2], we proposed a numerically robust algorithm for constructing the three-dimensional Voronoi diagram. In this paper, we show that this algorithm can be applied not only to the construction of the ordinary Delaunay triangulation but also to the construction of the constrained Delaunay triangulation. In order to construct the constrained Delaunay triangulation, we invent numerical results on the way to the construction of the Voronoi diagram in such a way that they satisfy the constraints. Moreover we implemented the algorithm as a computer program, and verified the validity of the algorithm by computational experiments.