道路中心线提取及网络建立的算法研究

《道路中心线提取及网络建立的算法研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第33卷第3期2008年5月测绘科学ScienceofSurveyingandMappingVol133No13May1道路中心线提取及网络建立的算法研究①,闫喜凤②钟世彬(①江西省基础地理信息中心,南昌　330046;②江西科技师范学院,南昌　330038)【摘　要】提取道路中心线并建立道路网络是网络分析和地图综合中的基本问题,本文提出了利用约束Delaunay算法形成道路约束三角形网,并在此基础上提取道路中心线,形成道路中心线及建立网络。强调在提取过程中要注意的几个关键问题,并提出了解决方法。【关键词】中心线;Delaunay三角网;网络分析;地图综合【中图分类号】P2

2、82　　　　【文献标识码】A　　　　【文章编号】100922307(2008)0320105203 DOI:1013771/j1issn11009223071200810310371　引言大的[3]。D三角网的特性可以最大可能地消除狭长三角形的出网络分析是GIS应用中的基本工具,最优路径和资源现,这就使得它在工程中具有了很大的应用价值。同时,D分配都是在地理要素的网络图上进行的。在三维系统中的道路漫游,在城市中的道路的最短路径分析,都是在道路三角网与Voronoi图在计算几何上是对偶的,通过前者可以方便地计算出后者,扩展为更广泛的应用[4]。网络上进行的。在制图中,道路是用

3、两条线表示,而要形一般情况下在街区线上的点太少,很容易形成生成小 成道路网络,则需要进行道路中心线的提取,变双线为单内角的狭长三角形(如图1)。为解决保持Delaunay特性与 线的问题。约束条件之间的矛盾,我们对街区多边形边界弧段上的矢 而在城市地图数据库中,街区边界的表达具有双重角量点作加密处理,使得有更多的间距接近的点参与构网。 色,既是组成街区多边形的弧段又是道路网络的边,是跨我们采用方法是:当边界线上两点之间的距离大于平 接面状目标与网络状目标的桥梁。城市用地规划、土地利均道路宽度时,就添加点,直到边界上相邻两点之间的距用分析是基于街区多边形为主的空间分析,交通路

4、径设置、离小于平均道路宽度。平均道路宽度可根据经验预设定。城建设施布线选址是基于网络目标为主的空间分析。对于街区图的综合则要同时考虑道路网分布的图结构(连通性、邻接关系、关联关系、子图层次性)和街区多边形几何信从中可看出加密后既保证约束条件又保证了Delaunay不出现狭长三角形的特性。(如图1)顾及后继中心线提取及建网过程中多边形、三角形顶息、拓扑信息结构(面积、形状、相邻关系)。为满足这些点、边之间关系的表达,对选取的每个三角形元建立如下 应用要求,完备的城市地图数据库必须同时建立道路网络的数据存贮结构:模型和街区多边形模型,并在两者之间建立有效的联系。首先将需要三角剖

5、分的点分为散点和边界点,边界点 以上述的关联规则获取为基础,可以为中小比例尺地图中按一定的顺序(逆时针或顺时针)排列。点的数据结构为单道路网络建立提供数据源,其中将桥梁和居民地视为网络向链表,定义如下。 中的节点,如阻抗点或能源中心等,将道路段视为链。typedefstructVertex{本文就将基于街区矢量数据的基础上,介绍道路中心intID;//ID号线提取及网络建立的算法。doublex,y,z;//坐标值2　利用约束Delaunay算法形成道路约束三角形网空间离散点集上不规则三角网在与几何形体有关的信息数据分析处理中得到了广泛应用,其中Delaunay三角网cha

6、rmark;//材料、边界标记,区分散点、外边界点、内边界点structVertex3next;//下一个节点}3PVERTEX,VERTEX;(以下简称D三角网)由于其优良的数学性质而成为是最常用的一种[1,2]。D三角网具有两个独特的性质:[1,2]。D三角网具有两个独特的性质:三角形单元的定义是三角剖分的基础,必须定义很好的结构表达三角形的拓扑结构,以提高算法的效率,并且①空外接圆性质:离散点集P的D三角网中,每一个 三角形的外接圆不包含P中除该三角形三个顶点外的其他必须方便三角形单元在三角网中脱离拓扑结构。本文定义如下。任何点;②三角形最小角最大:离散点集P上的所有

7、不规则三角网中,D三角网的每个三角形的最小角度是最typedefstructTriangle{structEdge3pe[3];//指向三角形的三个边structVertex3pv[3];//指向三角形的三个顶点作者简介:钟世彬(19782),男,硕士,江西万载人,专业是地图制图学与地理信息工程,现从事GIS开发与应用研究。E2mail:shibinzhong@1631com收稿日期:2007020822intID;//ID号structTriangle3next,3pre;//指向前后的三角形}3PTRIANGL