一般图形voronoi图的离散生成

《一般图形voronoi图的离散生成》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、一般图形Voronoi图的离散生成刘欣LIUXin（承德石油高等专科学校社科与数理部，承德067000）（DepartmentofSocialScienceandMathematics，ChengdePetroleumCollege，Chengde067000，China）摘要：由于一般图形形状和位置的任意性，一般图形Voronoi图往往比较复杂，难以将传统的构造法直接应用到一般图形Voronoi图的构造中。本文介绍了一般图形Voronoi图的离散构造法，并给出算法步骤及优势分析。Abstract：Becauseoftherandomgraphshapeandposition，thegene

2、ralVoronoigraphisoftenmoreplex，itisdifficulttoconstructthetraditionalmethodofdirectapplicationtothegeneralstructureofVoronoigraph.ThispaperintroducestheconstructionmethodofgeneraldiscreteVoronoigraph，andputsforstepsanditsadvantages..jyqk；discretegeneration中图分类号：TP391文献标识码：A：1006-4311（2015）19-0162-0

3、2基金项目：河北省高等学校科学技术研究项，编号为QN20131159；承德市软科学研究计划项目（承德市公交线路的发展现状与优化分析）：201422123。简介：刘欣（1977－），女，河北承德人，承德石油高等专科学校社科数理部讲师，硕士，研究方向为计算几何、算法设计等。0引言一般图形Voronoi图（泰森多边形）的传统构造方法主要来自于普通Voronoi图的构造。但由于一般图形的任意性，一般图形Voronoi图的Voronoi边的形状往往比较复杂，从而使得难以将传统的构造方法直接应用到一般图形Voronoi图的构造中。本文主要介绍一般图形Voronoi图的离散构造方法。1普通Voronoi图

4、的定义本文主要研究二维平面内的一般图形Voronoi图，先介绍二维平面普通Voronoi图。在不混淆的情况下，简称普通Voronoi图为Voronoi图，普通Voronoi多边形为Voronoi多边形。下面给出精确的数学语言描述。2基本思想一般图形Voronoi图的离散构造法的基本理念是：首先，对每一生成元指定一种颜色，在各个生成元的边界上选择具有代表性的母点（详见图2），再用母点所在生成元的颜色围绕母点向外扩展画圆（详见图3）。已有颜色的点一律越过，或者按指定颜色为该像素点着色，直到将整个屏幕内所有像素点都画上了颜色才可结束。此时不同颜色区域的边界即为一般图形Voronoi图的近似曲线（图

5、4），将之抽出。当母点充分密集时，这种近似效果往往能达到很高的程度。算法概述：⑤对整个屏幕进行横向扫描和纵向扫描，如果发现某一像素点与其后继像素点颜色不一致，就将该像素点设置为黑色，将其余像素点设为白色，结束。3离散构造法创新本文所研究的Voronoi图离散构造法具有传统一般图形Voronoi图的构造法无法实现的功能优势：①算法的实现与生成元的具体形状和具体位置无关，生成元互相交叉的情况不增加算法的复杂性；②算法不关心生成元之间的Voronoi边的几何形状，无需复杂计算；③由于光栅扫描显示器的显示屏幕由有限个像素点构成，而算法的时间复杂度主要与像素点个数有关，与母点个数无关，因而增加生成元的

6、个数对提高或降低图形生成速度没有意义，从而可使近似效果与理想效果保持高度一致，在算法上没有任何误差。4结论推广一般图形Voronoi图是许多已知Voronoi图的一般化。譬如当定义中的生成元g1，g2，…，gn为线段时，该图便是以线为生成元的Voronoi图，当生成元g1，g2，…，gn均为平面上的圆时，该图便是以圆为生成元的Voronoi图。一般Voronoi图在其它许多方面如：数据压缩、图象处理、树皮皮肤纹路的模拟、神经网络、城市及地域规划以及物理学、生态学、经营学、地质学、结晶学、调查学、考古学等学科都有着广泛的应用。同时，对不少领域应用对Voronoi图理论提出了新的要求，算法结论也

7、可需推广。.jyqkai，MIri，KMurota.VoronoidiagramintheLaguerregeometryanditsapplication[J].SIAMJournalonputing.1985.[2]SugiharaK.VoronoiDiagrams.[3]滑斌杰，林立忠，柴忠良.粗糙域Voronoi图离散生成算法研究[J].计算机工程与应用，2013（23）.[4]赵志辉，张有会，赵晔，