线段障碍城市VORONOI图的结晶生成

《线段障碍城市VORONOI图的结晶生成》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、河北师范大学硕士学位论文线段障碍城市Voronoi图的结晶生成姓名：安志宏申请学位级别：硕士专业：基础数学指导教师：张有会20070501i

2、I『北9I

3、j范人学顾I。研究生学位论文摘要线段障碍城市Voronoi图是在城市Voronoi图基础上的扩展。城市Voronoi图的提出是基于一种平面为厶的度量，要求交通网络路线是水平和竖直方向，并且可以在任意点自由进出交通网络的具体模型。但客观世界中没有障碍而直接通行的情况是相对较少的，绝大部分交通网络都被一个个各种形状的障碍隔开，在各种形状的障碍中，又以线段障碍最为重要，许多障碍可以近似为线段障碍来处理，因此研究线段障碍的城市Voron

4、oi图是很有必要的。本文给出了线段障碍城市Voronoi图的定义、性质和相关性质的简单证明，同时，给出了线段障碍城市Voronoi图的结晶生成算法和程序实现，该算法简单，无需复杂的数据结构，可读性好，还可推广到任意障碍的几何图形，文中结合实例给出了线段障碍城市Voronoi图的应用，较好地解决了有障碍的基于平面厶度量、交通路线为水平和竖直方向且以时间距离考虑的对平面区域的分割。关键词Voronoi图、城市Voronoi图、线段障碍城市Voronoi图、结晶生长河北师范大学硕I：研究生学位论文AbstractThecityVoronoidiagramwith1inesegmento

5、bstacleisthedevelopmentofthecityVoronoidiagram，whichisbasedonaplanedistance厶andrequiresthetraffic1ineisonthelevelorverticalandamodelwhichcanpassinandoutthetrafficnetfreely．However，intherealworld，thedirecttransitwithoutobstructionidnearlyimpossible．Mostofthetrafficnetsaredividedbya11kindsofobs

6、truction，inwhichthesegmentobstacleisthemostimportantandmanyobstaclescanbehandledassegmentobstacles，thus，itisnecessarytostudythecityVoronoidiagramwithlinesegmentobstacle．Thistestgivesthedefinition，thenaturesoftierelativesimpleprovementandcrystalgrowthalgorithmanditspracticeprogram，whichissimpl

7、eandneedn’tthecomplicateddatastructure．Itcanbeusedtoanyobstacleofdifferentgeometryfigures．ThetestalsoprovidessomeexampletoexplainthepracticeofthecityVoronoidiagramwithlinesegmentobstacle，whichsolvestheproblemofthedivisionoftheobstructionplaneareabasedonthe厶distance．thetrafficlineonlevelandver

8、ticalandtheconsiderationofthetimedistance．Kelnvords：Voronoidiagram，ThecityVoronoidiagram，ThecityVoronoidiagramwithlinesegmentobstacle，Crystalgrowth．2．河北师范人学顾I：研究生学位论文第一章绪论1．1Voronoi图的历史及应用Voronoi图是一个关于空间分割的基础数据结构，也是经典计算几何学的一个重要几何结构，Voronoi图在求解点集或其它几何对象与距离有关的问题时起重要作用，它描述的是空间点集对于包含该点集的研究区域的一种剖分

9、结果，这种剖分结果能够很好地表达点与点之间的邻近关系以及点的影响范围等重要的空间关系信息。Voronoi图的历史相当古老，许多自然现象都可用Voronoi图描述。早在1644年，Descartes就使用了类似Voronoi图的结构对太阳系进行分割⋯；第一个有关Voronoi图的概念是在PeterGustavLejeune(1805—1859)与6eorgesVoronoi(1868—1908)著作里出现的：数学家Dirichlet(1850)和Voronoi(1907，1908，