ZD-研究-提取道路中心線算法-V1.1.doc

生成道路中心线算法 研究文档 Version 1.0 文档名称：ZD-研究文档-生成道路中心线算法 -V1.1.doc 修订历史记录 日期 版本号 修改说明 修改人 核准人 2009/04/09 1.0 首次撰写 王慧敏 目录 1 引言 4 1.1 目的与范围 4 1.2 预期的读者 4 1.3 方法学 4 1.4 定义、缩写词 4 1.5 参考资料 4 2 研究内容 4 2.1 子研究内容分解 4 3 附录 4 研究文档 引言 目的与范围 本文档旨在对生成道路中心线的算法进行研究，总结提出可行的详细实现方法及相关数据结构定义。 预期的读者 [列举本文档所针对的不同读者，例如对象设计人员、开发人员、项目经理、测试人员等。描述文档的组织结构，提出最适合每一类读者阅读的阅读建议。可以用超链接技术把各角色所关心的内容列出来，进行方便地跳转。] 方法学 [说明设计所采用的方法学，对其思想、设计过程、辅助工具做简短的描述。] 定义、缩写词 约束D三角网：在多边形地图的应用中对三角网建立规定约束条件，即保证构建的三角网不穿越多边形边界，使多边形边界强制性地成为三角形的一条边。 三角元：构成三角网的基本三角形。 参考资料 [1] 艾廷华，郭仁忠.基于约束Delaunay结构的街道中轴线提取及网络模型建立.测绘学报.Vol.29.No.4. Nov..2000 [2] 艾自兴 毋河海 艾廷华 曾文华. 河网自动综合中Delaunay三角的应用.地球信息科学.No.2. 2003.06 [3] Dan Lee,Paul Hardy. Design and Experience of Generalization Tools.ESRI Inc,Redlands,California USA [4] Jan_Henrik Haunert and Monika Sester ,Area Collapse and Road Centerlines based on Straight Skeletons.2008 研究内容 提取中心线的方法： 目前已比较成熟的算法： 基于边界线的垂线族法：该算法的几何原理很直接但应用上有不少困难，街道交叉口有多个多边形相连时，该方法会产生不良结果，当零碎的街区块相遇时，中轴线的连接完全歪曲了街道间的连通关系，会出现尖锐的抖动。 栅格形态变换法：分4个步骤完成：街区多边形栅格化、栅格属性取反、减细骨架化、矢量化。该方法得到的中轴线质量主要取决于形态变换的细化算子，当街道出现瓶颈口时，难以保证细化栅格的连续性，栅格数据的大容量存储特点使得该方法的运算效率较低。该算法获得的中轴线不能与街区块多边形建立匹配关系，不能回答哪些街区与特定街道路径邻近的问题。 约束Delaunay三角网提取法：较为常见且实用的一种方法。ArCGIS 中CenterLine的功能即是采用此算法生成中心线。文档中将重点分析此算法。 TIN提取道路中心线的步骤： 构建约束D三角网 待构建数据预处理 对原始道路数据（线要素）进行拓扑造区，以便后面去除掉街区和未闭合的区域而只针对街道进行中心线的提取。 加密构建约束D三角网 直接构建三角网往往会完全破坏Delaunay的最邻近性质，约束条件产生了众多的狭长三角形，使得网结构不能正确探测到多边形目标间的邻近关系，图3(a)中01 与02间没有三角形连接，01 与02的邻近关系便不能在网结构中体现出来，为解决保持Delaunay特性与约束条件之间的矛盾，我们对街区多边形边界弧段上的矢量点作加密处理，使得有更多的间距接近的点参与构网。 设原多边形边界点为{Pi}，当长度|PiPi+1|w(w为街道平均宽度，可根据经验预设定)，则加 密点{ Qk}，有 其中: 图3(b)为边界点加密后构建的约束Delaunay三角网，从中可看出加密后既保证约束条件又保证了Delaunay不出现狭长三角形的特性，从而O1 与02的邻近关系可由其间的三角形连接体现出来。 道路区域三角元的识别 三角网建立后，对位于街区和不闭合区域内的三角元进行识别(通常选取三角元的重心P(X1+X2+X3/3,Y1+Y2+Y3/3),通过点与区的叠加进行识别),在数据结构上赋以标识位。在进行中轴线的提取时，先须进行三角元的识别目的是只对街道进行中轴线的提取。 通过D三角网生成中心线 从三角元提取中轴线 定义函数f(Ti)：T ={0，