刘欣 LIU Xin
（承德石油高等专科学校社科与数理部，承德 067000）
（Department of Social science and Mathematics，Chengde Petroleum College，Chengde 067000，China）
摘要：由于一般图形形状和位置的任意性，一般图形Voronoi图往往比较复杂，难以将传统的构造法直接应用到一般图形Voronoi图的构造中。本文介绍了一般图形Voronoi图的离散构造法，并给出算法步骤及优势分析。
Abstract： Because of the random graph shape and position， the general Voronoi graph is often more complex， it is difficult to construct the traditional method of direct application to the general structure of Voronoi graph. This paper introduces the construction method of general discrete Voronoi graph， and puts forword the algorithm steps and its advantages.
教育期刊网 http://www.jyqkw.com
关键词 ：一般图形；Voronoi图；离散生成
Key words： general graphs；Voronoi diagram；discrete generation
中图分类号：TP391 文献标识码：A 文章编号：1006-4311（2015）19-0162-02
基金项目：河北省高等学校科学技术研究项，编号为QN20131159；承德市软科学研究计划项目（承德市公交线路的发展现状与优化分析）：201422123。
作者简介：刘欣（1977－），女，河北承德人，承德石油高等专科学校社科数理部讲师，硕士，研究方向为计算几何、算法设计等。
0 引言
一般图形Voronoi图（泰森多边形）的传统构造方法主要来自于普通Voronoi图的构造。但由于一般图形的任意性，一般图形Voronoi图的Voronoi边的形状往往比较复杂，从而使得难以将传统的构造方法直接应用到一般图形Voronoi图的构造中。本文主要介绍一般图形Voronoi图的离散构造方法。
1 普通Voronoi图的定义
本文主要研究二维平面内的一般图形Voronoi图，先介绍二维平面普通Voronoi图。在不混淆的情况下，简称普通Voronoi图为Voronoi图，普通Voronoi多边形为Voronoi多边形。下面给出精确的数学语言描述。
2 基本思想
一般图形Voronoi图的离散构造法的基本理念是：首先，对每一生成元指定一种颜色，在各个生成元的边界上选择具有代表性的母点（详见图2），再用母点所在生成元的颜色围绕母点向外扩展画圆（详见图3）。已有颜色的点一律越过，或者按指定颜色为该像素点着色，直到将整个屏幕内所有像素点都画上了颜色才可结束。此时不同颜色区域的边界即为一般图形Voronoi图的近似曲线（图4），将之抽出。当母点充分密集时，这种近似效果往往能达到很高的程度。
算法概述：
⑤对整个屏幕进行横向扫描和纵向扫描，如果发现某一像素点与其后继像素点颜色不一致，就将该像素点设置为黑色，将其余像素点设为白色，结束。
3 离散构造法创新
本文所研究的Voronoi图离散构造法具有传统一般图形Voronoi图的构造法无法实现的功能优势：①算法的实现与生成元的具体形状和具体位置无关，生成元互相交叉的情况不增加算法的复杂性；②算法不关心生成元之间的Voronoi边的几何形状，无需复杂计算；③由于光栅扫描显示器的显示屏幕由有限个像素点构成，而算法的时间复杂度主要与像素点个数有关，与母点个数无关，因而增加生成元的个数对提高或降低图形生成速度没有意义，从而可使近似效果与理想效果保持高度一致，在算法上没有任何误差。
4 结论推广
一般图形Voronoi图是许多已知Voronoi图的一般化。譬如当定义中的生成元g1，g2，…，gn为线段时，该图便是以线为生成元的Voronoi图，当生成元g1，g2，…，gn均为平面上的圆时，该图便是以圆为生成元的Voronoi图。
一般Voronoi图在其它许多方面如：数据压缩、图象处理、树皮皮肤纹路的模拟、神经网络、城市及地域规划以及物理学、生态学、经营学、地质学、结晶学、调查学、考古学等学科都有着广泛的应用。同时，对不少领域应用对Voronoi图理论提出了新的要求，算法结论也可需推广。
教育期刊网 http://www.jyqkw.com
参考文献：
[1]H Imai，M Iri，K Murota.Voronoi diagram in the Laguerre geometry and its application[J]. SIAM Journal on Computing. 1985.
[2]Sugihara K.Voronoi Diagrams.
[3]滑斌杰，林立忠，柴忠良.粗糙域Voronoi图离散生成算法研究[J].计算机工程与应用，2013（23）.
[4]赵志辉，张有会，赵晔，吴敬.线段障碍Voronoi图的离散生成[J].计算机应用与软件，2004（01）.
[5]陈建国，王铮.基于面向对象的Voronoi图生成算法[J].测绘与空间地理信息，2004（02）.
[6]董蕊，张有会，刘淑娟，弓小影，王丹丹.线段加权Voronoi图的离散生成算法的研究与实现[J].计算机应用与软件，2009（07）.
[7]张静，张有会，王会英，刘淑娟.一般图形Voronoi图在版面分割中的应用[J].计算机应用与软件，2007（02）.
[8]赵晔，张有会，赵志辉.Power图的离散生成[J].计算机辅助设计与图形学学报，2003（09）.
[9]兰连意.一般城市Voronoi图结晶生成算法研究[D].河北师范大学，2008.
[10]刘玉珍.关于障碍Voronoi图的研究[D].哈尔滨理工大学，2008.