首页|行业资讯|企业名录|周边产品|数字城市|增强现实|工业仿真|解决方案|虚拟医疗|行业仿真|图形处理|军事战场
资讯首页
行业资讯 >> 专业文献>>正文
三维GIS模型构造及算法设计研究
2010年10月28日    评论:    分享:

    来源:第三维度
    作者:未知

    摘  要:本文分析实现真三维GIS的技术难点,从2.5维GIS可视化基础出发,选用TIN模型作为地形可视化的数据模型,介绍了程序中所采用的TIN模型的拓扑数据结构,并以凸壳技术和Bowyer-Watson算法的思想为基础,实现一种由任意离散点生成Delaunay三角网格的算法。

    引  言

    计算机软硬件的发展水平一直是制约地理信息系统(GIS)发展的主要问题之一,特别是三维可视化方面的研究。近年来,虽然计算机的数据处理能力以及图形显示能力已经大大提高,但对于真三维的地理信息系统的实现而言,仍然存在诸多尚未解决的技术难点。

    首先,空间三维数据的采集,其成本相当昂贵;

    其次,真三维GIS的空间数据量大,种类多,结构复杂;

    第三,三维空间的点、线、面和体之间的拓扑关系复杂,技术尚不成熟;

    第四,空间分析困难。

    因此,在地理信息的三维可视化(特别是地形三维可视化)的研究中,通常采用2.5维的GIS可视化的方法来实现地理信息的三维可视化。该方法主要是以高质量的数字高程模型(DEM)和高逼真度的三维显示技术为基础。其中DEM的质量,对地形三维可视化的效果有着不容忽视的影响;而影响DEM质量的关键是生成DEM的算法。所以,采用一种实用性强、精度较高、生成速度快,使用方便的DEM的生成算法是十分必要的。

    1  数字高程模型

    在地理信息中,DEM主要有三种表示模型:规则格网模型(Grid)、等高线模型和不规则三角网模型(Triangulated Irregular Network,TIN).但这三种不同数据结构的DEM表征方式在数据存储以及空间关系等方面,则各有优劣,见表1.

三维GIS模型构造及算法设计研究
表1  不同数据结构数字高程模型的比较

    从表1我们可以看出,虽然TIN在存储空间的要求上相对较高,但在处理任意复杂的地形上具有绝对的优势,加之大多数图形显示硬件都针对三角形进行了特殊优化;因此,在可视化研究中以TIN的数据结构作为我们研究的数据模型。

    生成DEM的数据通常以矢量化的等高线和其它特征点、线数据或者直接从各类矢量数据库中取出的等高线矢量数据为主要数据源。这些数据从数字化仪获得,主要以离散点为主。对于离散点转换成TIN,最常用的方法是Delaunay三角剖分法,选用一种合适的算法来生成Delaunay三角网是我们研究的主要目的。

    2  TIN的数据结构

    考虑到生成TIN的算法中点、线、面之间的拓扑关系,我们采用了如下的数据结构作为TIN的存储结构。该数据结构能够较好的建立TIN数据模型的拓扑关系,并且能在其点、边以及三角形之间建立快速索引,有利于我们在TIN生成算法中的实现,具体如下。

    2.1  离散点表

    离散点表作为所有点坐标数据的数据库,建立其索引便于以后的边表和三角形表中点索引的查询。

    class DiscretedPoint:public Object

    { float x,y;// 离散点的坐标

    int index;//点的索引 }

    2.2  有序边表

    记录三角网生成期间所使用过的边,以及最后存储的三角形间边的信息。

    class Edge:public Object

    {int Start;// 边的起点

    int End;//边的终点

    int LeftTriangle;// 边的左三角形索引

    int RightTriangle;// 边的右三角形索引

    int index;// 边的索引}

    2.3  三角形网表

    记录最终生成的TIN数据模型中的三角网之间的拓扑关系。该数据结构是以经典的LTL(Lawson's Triangle List)表结构来存放三角网信息的。

    class TriangleNet:public Object

    {int NodeA;// 三角形的顶点A的坐标索引

    int NodeB;// 三角形的顶点B的坐标索引

    int NodeC;// 三角形的顶点C的坐标索引

    int AdjTriangleA;// 三角形的顶点A的对边相邻的三角形

    int AdjTriangleB;// 三角形的顶点B的对边相邻的三角形

    int AdjTriangleC;// 三角形的顶点C的对边相邻的三角形

    int index;// 三角形的索引}

    3  TIN的实现

    我们所采用的Delaunay生成算法主要分为两步:首先要生成一个包括所有离散数据点的凸壳;再利用该凸壳生成一个初始的三角网,并在此基础之上,逐个加入其它离散点,生成最终的三角网。对于凸壳的生成我们采用格雷厄姆算法,该算法是求解平面点集凸壳问题的最佳算法,算法复杂度为O(n logn).对于三角网上加入其他数据点的算法是基于Bowyer-Watson算法的思想,该算法能很好的生成符合Delaunay法则的三角网,也就是我们在地形可视化时需要的TIN模型。
   
    3.1  格雷厄姆算法的实现

    首先我们选取值最小的点作为参考点,将离散数据点按照它们与参考点之间的角度的大小对数组进行排序。其中选取x坐标最小点作为参考点有两个原因:①x最小的数据点必定是凸壳的顶点;②选取x最小的点作为参考点,可以使其它数据点与参考点之间的夹角在[-π2,π2]之间,在这个区间中,角度的正切值是随角度的增大而增大的,有利于编程实现。另外,我们使用离散数据数目加1的数组来存储数据点,并将排序后的数据点的第一点的坐标存入数组的最末位置上。

    int  Convex()

    { 假设凸壳顶点数目等于离散点的数目;

    j=1;

    for (k=3;k<=凸壳顶点数目;k++)

    while (j

    { if (j+1点不是凸壳的顶点)

    { 删除该点,其后所有数据点前移一位;

    k=k-1;j=j-1;

    凸壳顶点数目减1;}

    else j=j+1;}

    return 凸壳顶点数目; }

    3.2  Bowyer-Watson算法的思想与实现

    Bowyer-Watson算法的基本思想:①假定已生成了连接若干个顶点的Delaunay三角网格;②加入一个新的节点,找出所有外接圆包含新加入节点的三角形,并将这些三角形删除,形成一个空腔;③将空腔的节点与新加入的节点连接,形成新的Delaunay三角网格;④调整数据结构,新生成的三角形的数据填充被删除三角形的数据,余者添加在数组的尾部;⑤返回第二步,直至所有的节点都加入为止。

    在初始网格的实现中,我们采用的是将凸壳看作是一个空腔,对其进行分割,形成一个符合Delaunay标准的初始三角网。再在此初始三角网格的基础上,应用Bowyer-Watson算法的思想生成最终的三角网。下面是该算法实现的伪代码(假定初始三角网已经生成):

    void Gernerate_Delaunay_Net( )

    { 初始三角形数组

    将所有待加入的离散数据点放入点堆栈中

    while(点堆栈不为空)

    { 初始化边列表为空;

    点堆栈进行出栈操作,即弹出一个待加数据点;

    for (i=0;i<三角形数组中元素的个数;i++)

    { 计算三角形的外接圆的圆心和半径;

    if (待加数据点在三角形的外接圆内)

    { 将该三角形的三条边与边列表中的所有边进行比较;

    { if (该边已经在边列表中存在)
   
    边列表中的这条边的权值变为2;

    else if (该边不在边列表中)

    则将该边加入边列表;}

    将该三角形从三角形数组中移出;}

    for (i=0;i<边列表的长度;i++)

    { if (边的权值为1)

    { 将边与待加数据点形成的所有三角形加入到三角形数组中;

    }}}}

    4  实验结果与分析

    对于前述算法,笔者已经用VC++6.0在计算机上实现,实验表明对于TIN模型的生成,该算法是行之有效的。在图1中展示了离散点生成Delaunay三角网的实验结果。以上实验结果,实际上只是地形可视化研究的基础工作,在以后还将涉及到大量数据的试验。造成这样结果的原因是由于数据来源的限制,因此,在我们的实验结果中并非是直接针对实际地形数据做出的模拟;只是一些由笔者自行输入的几十个点数据,目的旨在验证算法的有效性和可行性。对于大幅地形图而言,由于数据的采集量很大,一般都在上万个数据点以上,与这样的数据量相比,实验中所涉及的数据量显然是很小的。实验结果表明,用小数据量的离散点来生成Delaunay三角网时,算法能得到很好的结果;而对于大数据量而言,算法的效率可能会很低,这取决于在计算过程中所生成的三角形的数目。假定输入离散点的数目为n,生成一个由m个顶点构成的凸壳的时间复杂度为O(n logn),生成初始三角网的时间复杂度为O(n2),这期间将对初始三角网进行调整,使其符合Delaunay法则,需要对至多(3n-6-m)条边的搜索,其时间复杂度为O(n),插入点时间复杂度约为O(n2),那么该算法总的时间复杂度约为[O(n2)+O(n)+O(n2)],即O[2n(n+1)].

图1  由任意离散点生成Delaunay三角网格
图1 由任意离散点生成Delaunay三角网格

    5、结束语

    今后,我们将针对海量的实验数据、特征线、特征点等问题,对算法程序进行完善和修改,此外还将对TIN模型,即Delaunay三角网的三维显示进行研究。

标签:GIS算法
上一篇:石油勘探钻井中的虚拟现实三维可视化技术
下一篇:基于三维GIS的虚拟现实数字城市实现方法研究
网友评论:三维GIS模型构造及算法设计研究
评论
留名: 验证码:
您可能还需要关注一下内容:
·基于ArcGIS创建三维虚拟城市流程
·三维虚拟地球的海洋信息适用性分析及原型研究
·组件式 GIS 技术在军事仿真系统中的应用
·海岛礁及周边复杂环境动态三维建模
·基于虚拟环境的黄河仿真系统构建
·超大规模分布式虚拟现实系统
·用 GIS与虚拟现实技术模拟火灾过程
·地理信息科学研究进展
·论虚拟地理实验思想与方法
·论天地一体化对地观测网与新地理信息时代
☏ 推荐产品

Ladybug5全景
商家:力方国际

ProJet®
商家:力方国际

ProJet®
商家:视科创新

Premium1.5
商家:视科创新

巴可HDX主动立体投
商家:德浩科视

巴可HDF-W26投
商家:德浩科视

巴可30000流明2
商家:德浩科视

巴可4万流明2K投影
商家:德浩科视
☞ 外设导航
☏ 企业名录
【广州】中科院广州电子技术有限公司
【北京】第二空间(北京)科技有限公司
【北京】幻维世界(北京)网络科技有限公司
【厦门】厦门惠拓动漫科技有限公司
【厦门】厦门幻眼信息科技有限公司
【深圳】深圳南方百捷文化传播有限公司
【北京】北京思源科安信息技术有限公司
【上海】上海殊未信息科技有限公司
【北京】北京赢康科技开发有限公司
【武汉】武汉科码软件有限公司
友情链接 关于本站 咨询策划 行业推广 广告服务 免责声明 网站建设 联系我们 融资计划
北京第三维度科技有限公司 版权所有 京ICP备09001338
2008-2016 Beijing The third dimension Inc. All Rights Reserved.
Tel:010-57255801 Mob:13371637112(24小时)
Email:d3dweb@163.com  QQ:496466882
扫一扫 第三维度
官方微信号