城市景观三维重建中的三角剖分算法.pdf.pdf

维普资讯
第卷第期测绘科学.
年月.
城市景观三维重建中的三角剖分算法
殷勇①,俞连芳②,马照亭①,李成名①
①中国测绘科学研究院,北京;②湖州市测绘院,浙江湖州
【摘要】在构建城市景观时,为了快速精确地重建建筑物、绿地、河流等三维模型,提高自动化程度,缩短建
设周期,需对用户采集的矢量地物数据进行三角剖分,再以重绘三维模型。本文提出了一种对多边形进
行三角剖分的递归分割算法,并以实现, 以实际的万多个建筑物进行三角剖分实验,充分证明其是
有效的。
【关键词】数字城市;三角剖分;三维;
【中图分类号】【文献标识码】【文章编号】——
:./.....
定义:过点作任一射线与多边形求交,如果距
引言
离点最近的交点不是多边形的顶点,则该交点所在边
在城市景观三维重建中,对于二维地理信息系统中的称为点的可见边。
面状对象,如道路、河流、绿地、建筑物等的构建绝大多定义:设。, , , ⋯,,。表示一个简
数仍停留在手工阶段,已经成为城市景观三维重建中的数单多边形,由边,..所形成的内角即位于多边
据瓶颈。为了快速、准确地构建这些模型,必须开发一套形所围成的有界区域内部的角记为,若多边形某顶点,
自动化强、效率高的三维建模工具。二维地理信息中的面的内角∈, 则该顶点是凸顶点;若∈,,则
是三维模型的重要组成部分,如何对其快速剖分是三维模该顶点是凹顶点。
型构建的关键技术之一。定义:对于一个凹多边形,去掉它的一个任意顶点产
从建立最优三角形条件的角度提出了简生一个新多边形并同时分割出一个三角形,如果生成的新
单多边形三角剖分的算法;杨杰等提出了根据顶点凹凸多边形和同时分割出的三角形互不重叠并且二者的并集为
性进行简单多边形三角剖分的算法,然而,这些算法都是原始凹多边形,则把生成的新多边形和三角形称为原凹多
基于平面的,在三维的许多应用中,需要考虑高程起边形的一个划分。把这样的操作称为对原凹多边形的划分。
伏和带洞多边形等复杂情况,典型的如河流、道路、绿地把这样的顶点称为凹多边形的一个可剖分顶点。
等;刘强、李德仁等提出基于二叉树思想的任意多边形同时由定义可以很容易导出,一个凹多边形至少有一
三角剖分递归算法,考虑了高程起伏和和简单带洞多边形, 个可剖分顶点,凸顶点不一定是可剖分顶点,但可剖分顶
但数据结构和算法实现复杂。本文直接基于城市景观三维点一定是凸顶点,本文所叙述的多边形三角剖分关键也就
应用需要,提高自动化程度,缩短建设周期,充分考虑高在可剖分顶点的自动快速搜寻。
程起伏和带洞多边形等复杂情况,提出解决三维模型快速三角剖分的基本思想:
重建中的三角剖分问题。本算法实现简单,实用性强,利首先不管多边形的凹凸性,从原始多边形中寻找一个可
用现有的二维分图层面状数据,可快速重建城市景观。剖分顶点,对原始的多边形进行划分,从而分割出一个三角
形同时产生一个新多边形,然后对新生成的多边形判断其凸
多边形剖分原理
凹性,若为凸多边形,则顺序连接多边形各点生成三角形
一般来说,多边形可以分为五类:简单多边形、退化网,算法结束;否则对新生成的凹多边形进行递归操作直到
多边形、自重叠多边形、自相交多边形和多连通多边形, 原始的多边形划分成一系列三角形