一种新的构建Voronoi图的栅格方法

鉴于构建复杂发生元的Voronoi图的矢量方法的困难性，提出了一种新的栅格方法．该方法是通过确定每个栅格的归属来定义Voronoi区域．为了减少计算时间，设计了一种搜索某个栅格所属最近发生元的方法，它是根据对于该栅格而言发生元栅格所处的象限位置来计算的．利用了地理信息系统软件Arc／Info的功能模块Grid来实现矢-栅数据、栅-矢数据的转换和图形显示．该方法是实现发生元为任意复杂图形的Voronoi图的一种有效方法，与矢量方法相比只有一个栅格的误差，其计算机时随着栅格变小而增加，但随着发生元所占栅格数量的增加而减小。

New Raster-Based Method for Constructing Voronoi Diagrams

Most vector based algorithms of computing Voronoi diagram have some difficulties in handling complex generators (such as curves and areas). A new raster based method was developed, in which the Voronoi regions were defined by deciding each grid's character. In order to save the CPU time, the approach of searching its nearest generator for a grid was developed, which was based on the quadrantal location of generator grids in a raster space. The module Grid of Arc/Info software was employed to implement vector raster and raster vector data conversion and graphic display. The developed method can construct Voronoi diagrams with generators of any forms, and it has only one grid error compared with the vector based method. The CPU time increases with the reducing of the grid size but decreases with the increasing of the number of generator grids.