yrf985219
路人甲
路人甲
  • 注册日期2006-05-09
  • 发帖数5
  • QQ
  • 铜币127枚
  • 威望0点
  • 贡献值0点
  • 银元0个
阅读:2645回复:1

急求规则格网生成算法(急用)

楼主#
更多 发布于:2006-05-11 10:32
<P>求助建立规则格网的算法,哪位大哥帮帮忙啊</P>
喜欢0 评分0
gis
gis
管理员
管理员
  • 注册日期2003-07-16
  • 发帖数15945
  • QQ554730525
  • 铜币25337枚
  • 威望15352点
  • 贡献值0点
  • 银元0个
  • GIS帝国居民
  • 帝国沙发管家
  • GIS帝国明星
  • GIS帝国铁杆
1楼#
发布于:2006-05-15 12:24
<P>GIS中三维可视化的模型构造及算法设计研究</P>
<P center" align=center>周雪梅,杜世培<p></p></P>
<P center" align=center>(贵州工业大学 计算机科学与信息技术学院,贵州 贵阳 550003)<p></p></P>
<P><B>摘  要:</B>分析实现真三维GIS的技术难点,从2.5维GIS可视化基础出发,选用TIN模型作为地形可视化的数据模型,介绍了程序中所采用的TIN模型的拓扑数据结构,并以凸壳技术和Bowyer-Watson算法的思想为基础,实现一种由任意离散点生成Delaunay三角网格的算法。</P>
<P><B>关键词:</B>地理信息系统;不规则三角网;Delaunay三角剖分</P>
<P><B normal">中图分类号:</B>P208;TP301.6          <B normal">文献标识码:</B>A</P>
<P> <p></p></P>
<P>0  引  言</P>
<P 21pt; mso-char-indent-count: 2.0; mso-char-indent-size: 10.5pt">计算机软硬件的发展水平一直是制约地理信息系统(GIS)发展的主要问题之一,特别是三维可视化方面的研究。近年来,虽然计算机的数据处理能力以及图形显示能力已经大大提高,但对于真三维的地理信息系统的实现而言,仍然存在诸多尚未解决的技术难点。</P>
<P 21pt; mso-char-indent-count: 2.0; mso-char-indent-size: 10.5pt">首先,空间三维数据的采集,其成本相当昂贵;</P>
<P 21pt; mso-char-indent-count: 2.0; mso-char-indent-size: 10.5pt">其次,真三维GIS的空间数据量大,种类多,结构复杂;</P>
<P 21pt; mso-char-indent-count: 2.0; mso-char-indent-size: 10.5pt">第三,三维空间的点、线、面和体之间的拓扑关系复杂,技术尚不成熟;</P>
<P 21pt; mso-char-indent-count: 2.0; mso-char-indent-size: 10.5pt">第四,空间分析困难。</P>
<P 21pt; mso-char-indent-count: 2.0; mso-char-indent-size: 10.5pt">因此,在地理信息的三维可视化(特别是地形三维可视化)的研究中,通常采用2.5维的GIS可视化的方法来实现地理信息的三维可视化。该方法主要是以高质量的数字高程模型(DEM)和高逼真度的三维显示技术为基础。其中DEM的质量,对地形三维可视化的效果有着不容忽视的影响;而影响DEM质量的关键是生成DEM的算法。所以,采用一种实用性强、精度较高、生成速度快,使用方便的DEM的生成算法是十分必要的。</P>
<P> <p></p></P>
<P>1  数字高程模型</P>
<P 21pt; mso-char-indent-count: 2.0; mso-char-indent-size: 10.5pt">在地理信息中,DEM主要有三种表示模型:规则格网模型(Grid)、等高线模型和不规则三角网模型(Triangulated Irregular Network,TIN).但这三种不同数据结构的DEM表征方式在数据存储以及空间关系等方面,则各有优劣,见表1.</P>
<P center" align=center><B>表1  不同数据结构数字高程模型的比较<p></p></B></P>
<DIV align=center>
<TABLE medium none; BORDER-TOP: medium none; BORDER-LEFT: medium none; BORDER-BOTTOM: medium none; BORDER-COLLAPSE: collapse; mso-border-alt: solid windowtext .5pt; mso-padding-alt: 0cm 5.4pt 0cm 5.4pt" cellSpacing=0 cellPadding=0 border=1>

<TR>
<TD windowtext 0.5pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: windowtext 0.5pt solid; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: windowtext 0.5pt solid; WIDTH: 89.8pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 0.5pt solid" vAlign=top width=120>
<P center" align=center> <p></p></P></TD>
<TD windowtext 0.5pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: windowtext 0.5pt solid; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 99pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 0.5pt solid; mso-border-left-alt: solid windowtext .5pt" vAlign=top width=132>
<P center" align=center>等高线<p></p></P></TD>
<TD windowtext 0.5pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: windowtext 0.5pt solid; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 98.3pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 0.5pt solid; mso-border-left-alt: solid windowtext .5pt" vAlign=top width=131>
<P center" align=center>规则格网<p></p></P></TD>
<TD windowtext 0.5pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: windowtext 0.5pt solid; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 90.7pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 0.5pt solid; mso-border-left-alt: solid windowtext .5pt" vAlign=top width=121>
<P center" align=center>不规则三角网<p></p></P></TD></TR>
<TR>
<TD windowtext 0.5pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: windowtext 0.5pt solid; WIDTH: 89.8pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 0.5pt solid; mso-border-top-alt: solid windowtext .5pt" vAlign=top width=120>
<P center" align=center>存储空间<p></p></P></TD>
<TD windowtext 0.5pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 99pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 0.5pt solid; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt" vAlign=top width=132>
<P center" align=center>很小(相对坐标)<p></p></P></TD>
<TD windowtext 0.5pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 98.3pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 0.5pt solid; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt" vAlign=top width=131>
<P center" align=center>依赖格距大小<p></p></P></TD>
<TD windowtext 0.5pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 90.7pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 0.5pt solid; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt" vAlign=top width=121>
<P center" align=center>大(绝对坐标)<p></p></P></TD></TR>
<TR>
<TD windowtext 0.5pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: windowtext 0.5pt solid; WIDTH: 89.8pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 0.5pt solid; mso-border-top-alt: solid windowtext .5pt" vAlign=top width=120>
<P center" align=center>数据来源<p></p></P></TD>
<TD windowtext 0.5pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 99pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 0.5pt solid; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt" vAlign=top width=132>
<P center" align=center>地形图数字化<p></p></P></TD>
<TD windowtext 0.5pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 98.3pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 0.5pt solid; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt" vAlign=top width=131>
<P center" align=center>原始数据插值<p></p></P></TD>
<TD windowtext 0.5pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 90.7pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 0.5pt solid; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt" vAlign=top width=121>
<P center" align=center>离散点构网<p></p></P></TD></TR>
<TR>
<TD windowtext 0.5pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: windowtext 0.5pt solid; WIDTH: 89.8pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 0.5pt solid; mso-border-top-alt: solid windowtext .5pt" vAlign=top width=120>
<P center" align=center>拓扑关系<p></p></P></TD>
<TD windowtext 0.5pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 99pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 0.5pt solid; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt" vAlign=top width=132>
<P center" align=center>不好<p></p></P></TD>
<TD windowtext 0.5pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 98.3pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 0.5pt solid; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt" vAlign=top width=131>
<P center" align=center>好<p></p></P></TD>
<TD windowtext 0.5pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 90.7pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 0.5pt solid; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt" vAlign=top width=121>
<P center" align=center>很好<p></p></P></TD></TR>
<TR>
<TD windowtext 0.5pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: windowtext 0.5pt solid; WIDTH: 89.8pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 0.5pt solid; mso-border-top-alt: solid windowtext .5pt" vAlign=top width=120>
<P center" align=center>任意点内插效果<p></p></P></TD>
<TD windowtext 0.5pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 99pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 0.5pt solid; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt" vAlign=top width=132>
<P center" align=center>不直接且内插时间长<p></p></P></TD>
<TD windowtext 0.5pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 98.3pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 0.5pt solid; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt" vAlign=top width=131>
<P center" align=center>直接且内插时间短<p></p></P></TD>
<TD windowtext 0.5pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 90.7pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 0.5pt solid; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt" vAlign=top width=121>
<P center" align=center>直接且内插时间短<p></p></P></TD></TR>
<TR>
<TD windowtext 0.5pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: windowtext 0.5pt solid; WIDTH: 89.8pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 0.5pt solid; mso-border-top-alt: solid windowtext .5pt" vAlign=top width=120>
<P center" align=center>适合地形<p></p></P></TD>
<TD windowtext 0.5pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 99pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 0.5pt solid; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt" vAlign=top width=132>
<P center" align=center>简单、平缓变换<p></p></P></TD>
<TD windowtext 0.5pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 98.3pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 0.5pt solid; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt" vAlign=top width=131>
<P center" align=center>简单、平缓变换<p></p></P></TD>
<TD windowtext 0.5pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 90.7pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 0.5pt solid; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt" vAlign=top width=121>
<P center" align=center>任意、复杂地形<p></p></P></TD></TR></TABLE></DIV>
<P 21pt; mso-char-indent-count: 2.0; mso-char-indent-size: 10.5pt">从表1我们可以看出,虽然TIN在存储空间的要求上相对较高,但在处理任意复杂的地形上具有绝对的优势,加之大多数图形显示硬件都针对三角形进行了特殊优化;因此,在可视化研究中以TIN的数据结构作为我们研究的数据模型。</P>
<P 21pt; mso-char-indent-count: 2.0; mso-char-indent-size: 10.5pt">生成DEM的数据通常以矢量化的等高线和其它特征点、线数据或者直接从各类矢量数据库中取出的等高线矢量数据为主要数据源。这些数据从数字化仪获得,主要以离散点为主。对于离散点转换成TIN,最常用的方法是Delaunay三角剖分法,选用一种合适的算法来生成Delaunay三角网是我们研究的主要目的。</P>
<P> <p></p></P>
<P>2  TIN的数据结构</P>
<P 21pt; mso-char-indent-count: 2.0; mso-char-indent-size: 10.5pt">考虑到生成TIN的算法中点、线、面之间的拓扑关系,我们采用了如下的数据结构作为TIN的存储结构。该数据结构能够较好的建立TIN数据模型的拓扑关系,并且能在其点、边以及三角形之间建立快速索引,有利于我们在TIN生成算法中的实现,具体如下。</P>
<P>2.1  离散点表</P>
<P 21pt; mso-char-indent-count: 2.0; mso-char-indent-size: 10.5pt">离散点表作为所有点坐标数据的数据库,建立其索引便于以后的边表和三角形表中点索引的查询。</P>
<P 18pt; mso-char-indent-count: 2.0; mso-char-indent-size: 9.0pt">class DiscretedPoint:public Object<p></p></P>
<P 18pt; mso-char-indent-count: 2.0; mso-char-indent-size: 9.0pt">{ float x,y;// 离散点的坐标<p></p></P>
<P 36pt; mso-char-indent-count: 4.0; mso-char-indent-size: 9.0pt">int index;//点的索引 }<p></p></P>
<P>2.2  有序边表</P>
<P 21pt; mso-char-indent-count: 2.0; mso-char-indent-size: 10.5pt">记录三角网生成期间所使用过的边,以及最后存储的三角形间边的信息。</P>
<P 18pt; mso-char-indent-count: 2.0; mso-char-indent-size: 9.0pt">class Edge:public Object<p></p></P>
<P 18pt; mso-char-indent-count: 2.0; mso-char-indent-size: 9.0pt">{int Start;// 边的起点<p></p></P>
<P 27pt; mso-char-indent-count: 3.0; mso-char-indent-size: 9.0pt">int End;//边的终点<p></p></P>
<P 27pt; mso-char-indent-count: 3.0; mso-char-indent-size: 9.0pt">int LeftTriangle;// 边的左三角形索引<p></p></P>
<P 27pt; mso-char-indent-count: 3.0; mso-char-indent-size: 9.0pt">int RightTriangle;// 边的右三角形索引<p></p></P>
<P 27pt; mso-char-indent-count: 3.0; mso-char-indent-size: 9.0pt">int index;// 边的索引}<p></p></P>
<P>2.3  三角形网表</P>
<P 21pt; mso-char-indent-count: 2.0; mso-char-indent-size: 10.5pt">记录最终生成的TIN数据模型中的三角网之间的拓扑关系。该数据结构是以经典的LTL(Lawson's Triangle List)表结构来存放三角网信息的。</P>
<P 18pt; mso-char-indent-count: 2.0; mso-char-indent-size: 9.0pt">class TriangleNet:public Object<p></p></P>
<P 18pt; mso-char-indent-count: 2.0; mso-char-indent-size: 9.0pt">{int NodeA;// 三角形的顶点A的坐标索引<p></p></P>
<P 27pt; mso-char-indent-count: 3.0; mso-char-indent-size: 9.0pt">int NodeB;// 三角形的顶点B的坐标索引<p></p></P>
<P 27pt; mso-char-indent-count: 3.0; mso-char-indent-size: 9.0pt">int NodeC;// 三角形的顶点C的坐标索引<p></p></P>
<P 27pt; mso-char-indent-count: 3.0; mso-char-indent-size: 9.0pt">int AdjTriangleA;// 三角形的顶点A的对边相邻的三角形<p></p></P>
<P 27pt; mso-char-indent-count: 3.0; mso-char-indent-size: 9.0pt">int AdjTriangleB;// 三角形的顶点B的对边相邻的三角形<p></p></P>
<P 27pt; mso-char-indent-count: 3.0; mso-char-indent-size: 9.0pt">int AdjTriangleC;// 三角形的顶点C的对边相邻的三角形<p></p></P>
<P 27pt; mso-char-indent-count: 3.0; mso-char-indent-size: 9.0pt">int index;// 三角形的索引}<p></p></P>
<P> <p></p></P>
<P>3  TIN的实现</P>
<P 21pt; mso-char-indent-count: 2.0; mso-char-indent-size: 10.5pt">我们所采用的Delaunay生成算法主要分为两步:首先要生成一个包括所有离散数据点的凸壳;再利用该凸壳生成一个初始的三角网,并在此基础之上,逐个加入其它离散点,生成最终的三角网。对于凸壳的生成我们采用格雷厄姆算法,该算法是求解平面点集凸壳问题的最佳算法,算法复杂度为O(n logn).对于三角网上加入其他数据点的算法是基于Bowyer-Watson算法的思想,该算法能很好的生成符合Delaunay法则的三角网,也就是我们在地形可视化时需要的TIN模型。</P>
<P>3.1  格雷厄姆算法的实现</P>
<P 21pt; mso-char-indent-count: 2.0; mso-char-indent-size: 10.5pt">首先我们选取值最小的点作为参考点,将离散数据点按照它们与参考点之间的角度的大小对数组进行排序。其中选取x坐标最小点作为参考点有两个原因:①x最小的数据点必定是凸壳的顶点;②选取x最小的点作为参考点,可以使其它数据点与参考点之间的夹角在[-π2,π2]之间,在这个区间中,角度的正切值是随角度的增大而增大的,有利于编程实现。另外,我们使用离散数据数目加1的数组来存储数据点,并将排序后的数据点的第一点的坐标存入数组的最末位置上。</P>
<P 18pt; mso-char-indent-count: 2.0; mso-char-indent-size: 9.0pt">int  Convex()<p></p></P>
<P 18pt; mso-char-indent-count: 2.0; mso-char-indent-size: 9.0pt">{ 假设凸壳顶点数目等于离散点的数目;<p></p></P>
<P 27pt; mso-char-indent-count: 3.0; mso-char-indent-size: 9.0pt">j=1;<p></p></P>
<P 27pt; mso-char-indent-count: 3.0; mso-char-indent-size: 9.0pt">for (k=3;k<=凸壳顶点数目;k++)<p></p></P>
<P 36pt; mso-char-indent-count: 4.0; mso-char-indent-size: 9.0pt">while (j<k-1);<p></p></P>
<P 36pt; mso-char-indent-count: 4.0; mso-char-indent-size: 9.0pt">{ if (j+1点不是凸壳的顶点)<p></p></P>
<P 45pt; mso-char-indent-count: 5.0; mso-char-indent-size: 9.0pt">{ 删除该点,其后所有数据点前移一位;<p></p></P>
<P 54pt; mso-char-indent-count: 6.0; mso-char-indent-size: 9.0pt">k=k-1;j=j-1; <p></p></P>
<P 54pt; mso-char-indent-count: 6.0; mso-char-indent-size: 9.0pt">凸壳顶点数目减1;}<p></p></P>
<P 45pt; mso-char-indent-count: 5.0; mso-char-indent-size: 9.0pt">else j=j+1;}<p></p></P>
<P 36pt; mso-char-indent-count: 4.0; mso-char-indent-size: 9.0pt">return 凸壳顶点数目; }<p></p></P>
<P>3.2  Bowyer-Watson算法的思想与实现</P>
<P 21pt; mso-char-indent-count: 2.0; mso-char-indent-size: 10.5pt">Bowyer-Watson算法的基本思想:①假定已生成了连接若干个顶点的Delaunay三角网格;②加入一个新的节点,找出所有外接圆包含新加入节点的三角形,并将这些三角形删除,形成一个空腔;③将空腔的节点与新加入的节点连接,形成新的Delaunay三角网格;④调整数据结构,新生成的三角形的数据填充被删除三角形的数据,余者添加在数组的尾部;⑤返回第二步,直至所有的节点都加入为止。</P>
<P 21pt; mso-char-indent-count: 2.0; mso-char-indent-size: 10.5pt">在初始网格的实现中,我们采用的是将凸壳看作是一个空腔,对其进行分割,形成一个符合Delaunay标准的初始三角网。再在此初始三角网格的基础上,应用Bowyer-Watson算法的思想生成最终的三角网。下面是该算法实现的伪代码(假定初始三角网已经生成):</P>
<P 18pt; mso-char-indent-count: 2.0; mso-char-indent-size: 9.0pt">void Gernerate_Delaunay_Net( )<p></p></P>
<P 18pt; mso-char-indent-count: 2.0; mso-char-indent-size: 9.0pt">{ 初始三角形数组<p></p></P>
<P 27pt; mso-char-indent-count: 3.0; mso-char-indent-size: 9.0pt">将所有待加入的离散数据点放入点堆栈中<p></p></P>
<P 27pt; mso-char-indent-count: 3.0; mso-char-indent-size: 9.0pt">while(点堆栈不为空)<p></p></P>
<P 27pt; mso-char-indent-count: 3.0; mso-char-indent-size: 9.0pt">{ 初始化边列表为空;<p></p></P>
<P 36pt; mso-char-indent-count: 4.0; mso-char-indent-size: 9.0pt">点堆栈进行出栈操作,即弹出一个待加数据点;<p></p></P>
<P 36pt; mso-char-indent-count: 4.0; mso-char-indent-size: 9.0pt">for (i=0;i<三角形数组中元素的个数;i++)<p></p></P>
<P 36pt; mso-char-indent-count: 4.0; mso-char-indent-size: 9.0pt">{ 计算三角形的外接圆的圆心和半径;<p></p></P>
<P 45pt; mso-char-indent-count: 5.0; mso-char-indent-size: 9.0pt">if (待加数据点在三角形的外接圆内)<p></p></P>
<P 45pt; mso-char-indent-count: 5.0; mso-char-indent-size: 9.0pt">{ 将该三角形的三条边与边列表中的所有边进行比较;<p></p></P>
<P 54pt; mso-char-indent-count: 6.0; mso-char-indent-size: 9.0pt">{ if (该边已经在边列表中存在)<p></p></P>
<P 63pt; mso-char-indent-count: 7.0; mso-char-indent-size: 9.0pt">边列表中的这条边的权值变为2;<p></p></P>
<P 63pt; mso-char-indent-count: 7.0; mso-char-indent-size: 9.0pt">else if (该边不在边列表中)<p></p></P>
<P 81pt; mso-char-indent-count: 9.0; mso-char-indent-size: 9.0pt">则将该边加入边列表;}<p></p></P>
<P 81pt; mso-char-indent-count: 9.0; mso-char-indent-size: 9.0pt">将该三角形从三角形数组中移出;}<p></p></P>
<P 45pt; mso-char-indent-count: 5.0; mso-char-indent-size: 9.0pt">for (i=0;i<边列表的长度;i++)<p></p></P>
<P 45pt; mso-char-indent-count: 5.0; mso-char-indent-size: 9.0pt">{ if (边的权值为1)<p></p></P>
<P 36pt; mso-char-indent-count: 4.0; mso-char-indent-size: 9.0pt">{ 将边与待加数据点形成的所有三角形加入到三角形数组中;<p></p></P>
<P 36pt; mso-char-indent-count: 4.0; mso-char-indent-size: 9.0pt">}}}}<p></p></P>
<P> <p></p></P>
<P>4  实验结果与分析</P>
<P 21pt; mso-char-indent-count: 2.0; mso-char-indent-size: 10.5pt">对于前述算法,笔者已经用VC++6.0在计算机上实现,实验表明对于TIN模型的生成,该算法是行之有效的。在图1中展示了离散点生成Delaunay三角网的实验结果。以上实验结果,实际上只是地形可视化研究的基础工作,在以后还将涉及到大量数据的试验。造成这样结果的原因是由于数据来源的限制,因此,在我们的实验结果中并非是直接针对实际地形数据做出的模拟;只是一些由笔者自行输入的几十个点数据,目的旨在验证算法的有效性和可行性。对于大幅地形图而言,由于数据的采集量很大,一般都在上万个数据点以上,与这样的数据量相比,实验中所涉及的数据量显然是很小的。实验结果表明,用小数据量的离散点来生成Delaunay三角网时,算法能得到很好的结果;而对于大数据量而言,算法的效率可能会很低,这取决于在计算过程中所生成的三角形的数目。假定输入离散点的数目为n,生成一个由m个顶点构成的凸壳的时间复杂度为O(n logn),生成初始三角网的时间复杂度为O(n<SUP>2</SUP>),这期间将对初始三角网进行调整,使其符合Delaunay法则,需要对至多(3n-6-m)条边的搜索,其时间复杂度为O(n),插入点时间复杂度约为O(n<SUP>2</SUP>),那么该算法总的时间复杂度约为[O(n<SUP>2</SUP>)+O(n)+O(n<SUP>2</SUP>)],即O[2n(n+1)].</P>
<P center" align=center><v:shapetype><v:stroke joinstyle="miter"></v:stroke><v:formulas><v:f eqn="if lineDrawn pixelLineWidth 0 "></v:f><v:f eqn="sum @0 1 0 "></v:f><v:f eqn="sum 0 0 @1 "></v:f><v:f eqn="prod @2 1 2 "></v:f><v:f eqn="prod @3 21600 pixelWidth "></v:f><v:f eqn="prod @3 21600 pixelHeight "></v:f><v:f eqn="sum @0 0 1 "></v:f><v:f eqn="prod @6 1 2 "></v:f><v:f eqn="prod @7 21600 pixelWidth "></v:f><v:f eqn="sum @8 21600 0 "></v:f><v:f eqn="prod @7 21600 pixelHeight "></v:f><v:f eqn="sum @10 21600 0 "></v:f></v:formulas><v:path connecttype="rect" gradientshapeok="t" extrusionok="f"></v:path><lock v:ext="edit" aspectratio="t"></lock></v:shapetype><v:shape><v:imagedata src="./2003xb43-7.files/image001.gif" title="7-1"></v:imagedata></v:shape><p></p></P>
<P center" align=center>(a)任意离散点     (b)包围离散数据点的凸壳    (c)Delaunay三角剖分<p></p></P>
<P center" align=center>图1  由任意离散点生成Delaunay三角网格<p></p></P>
<P> <p></p></P>
<P>5  结束语</P>
<P 21pt; mso-char-indent-count: 2.0; mso-char-indent-size: 10.5pt">今后,我们将针对大数据量的实验数据、特征线、特征点等问题,对算法程序进行完善和修改,此外,还将对TIN模型,即Delaunay三角网的三维显示进行研究。</P>
<P> <p></p></P>
<P><B>参考文献:<p></p></B></P>
<P>[1]吴信才.地理信息系统原理与方法[M].北京:电子工业出版社,2002.224-226.<p></p></P>
<P>[2]王家耀.空间信息系统原理[M].北京:科学出版社,2001.168-169.<p></p></P>
<P>[3]徐青.地形三维可视化技术[M].北京:测绘出版社,2000.11-14.<p></p></P>
<P>[4]周培德.计算几何——算法分析与设计[M].北京:清华大学出版社,2000.103-109.<p></p></P>
<P>[5]李志林,朱庆.数字高程模型[M].武汉:武汉大学出版社,2001.43-47.<p></p></P>
<P>[6]章孝灿,黄智才,戴企成,等.GIS中基于拓扑结构和凸壳技术的快速TIN生成算法[J].计算机学报,2002,25(11):1212-1218.<p></p></P>
<P>[7]邬吉明,沈隆均,张景琳.Delaunay三角网格的一种快速生成法[J].数值计算与计算机应用,2001,22(4):267-275.<p></p></P>
<P> <p></p></P>
<P center" align=center><B>Research on Data Model Construction and Algorithm Design of<p></p></B></P>
<P center" align=center><B>3D GIS Visualization<p></p></B></P>
<P center" align=center>ZHOU Xue-mei,DU Shi-pei</P>
<P center" align=center>(College of Computer Science and Information Technology,GUT,Guiyang 550003,China)</P>
<P><B>Abstract:</B>This paper analyses the technical difficulties of 3-dimensional GIS,based on the 2.5 dimensional GIS,choosing the TIN as the data model of the terrain visualization.The Data structure used in the program is offered,and according to the convex-hull technology and the idea of Bowyer-Watson algorithm,the Delaunay Triangulated network is implemented with discrete point set.</P>
<P><B>Key words:</B>geographical information system;irregular triangulated network;Delaunay triangulation</P>
<P> <p></p></P>
<P> <p></p></P>
<P> <p></p></P>
<P><B normal">收稿日期:</B>2003-03-26<p></p></P>
<P><B normal">基金项目:</B>国家自然科学基金中法合作项目<p></p></P>
举报 回复(0) 喜欢(0)     评分
游客

返回顶部