障碍Voronoi图的结晶生成及其应用

用结晶方法来生成障碍Voronoi图.该方法的思想框架是:以生成元为生长点进行4-模板或8-模板的结晶生长,遇到障碍则将障碍边界加入生成元点集继续选择这两个模板结晶,最后得到不同结晶区域的交线图即为障碍Voronoi图.该方法可得到城区距离、棋盘距离下的两种Voronoi图,所用数据结构简单,已用VC 编程实现.并给出具体应用实例.

THE CRYSTAL GROWTH OF VORONOI DIAGRAMS WITH OBSTACLES AND ITS APPLICATION

An algorithm called crystal growth is introduced to construct Voronoi diagrams with obstacles.In its fundamental idea,generators of Voronoi diagrams are regarded as vegetated points,and the crystal growth begins from them with 4-point template and 8-point template.Once the growth meets with obstacles,the borders of the obstacles will also be regarded as vegetated points and the growth continues.Finally,the boundaries of the different crystal regions construct the Voronoi diagrams with obstacles.With this method two kinds of Voronoi diagrams with two different distances,the City Zone Distance and the Chessboard Distance,are obtained.It has simple data structure and has been realized in Visual C .A practical model is given.