2023年12月22日发(作者：vivoiqooneo5参数)

２０１１年第１２期　总第１６２期　福　建　建　筑　Ｎｏ１２・２０１１　Ｆｕｊｉａｎ　Ａｒｃｈｉｔｅｃｔｕｒｅ＆Ｃｏｎｓｔｒｕｃｔｉｏｎ　Ｖｏ１．１６２　建ＴＩＮ的几种算法比较　陈素　（福州市勘测院福建福州３５０００３）　摘　要：ＴＩＮ是由三角形构成的一种有限元网格，它主要用来表示地形或地物表面。本文从几种不同建ＴＩＮ的算法（三角网生长　算法、凸壳算法、前沿边推进算法和贪心算法）来比较和分析各算法的优缺点。　关键词：ＴＩＮ三角网生长算法　凸壳算法前沿边推进算法贪心算法　中图分类号：ＥＰ２５８］　文献标识码：Ｂ　文章编号：１００４－－６１３５（２０１１）１２一Ｏ１ｏ２一Ｏ３　Ｔｈｅ　ｃｏｎｓｔｒｕｃｔｉｏｎ　ｏｆ　ＴＩＮ　ａｌｇｏｒｉｔｈｍｓ　ｃｏｍｐａｒｉｓｏｎ　Ｃｈｅｎ　Ｓｕ　（Ｆｕｚｈｏｕ　ｉｎｖｅｓｔｉｇａｔｉｏｎ　ａｎｄ　ｓｕｒｖｅｙｉｎｇ　ｉｎｓｔｉｔｕｔｅ　Ｆｕｚｈｏｕ　３５０００３）　Ａｂｓｔｒａｃｔ：ＴＩＮ　ｉｓ　ｃｏｎｓｔｉｔｕｔｅｄ　ｂｙ　ｔｈｅ　ｔｒｉａｎｇｌｅ　ａ　ｆｉｎｉｔｅ　ｅｌｅｍｅｎｔ　ｍｅｓｈ，ｗｈｉｃｈ　ｉｓ　ｍａｉｎｌｙ　ｕｓｅｄ　ｔＯ　ｅｘｐｒｅｓｓ　ｔｏｐｏｇｒａｐｈｙ　Ｏｒ　ｔｅｒｒａｉｎ　ｓｕｒｆａｃｅ．　Ｔｈｉｓ　ｐａｐｅｒ　ｆｒｏｍ　ｓｅｖｅｒａｌ　ｄｉｆｆｅｒｅｎｔ　ＴＩＮ　ａｌｇｏｒｉｔｈｍ（ｔｒｉａｎｇｕｌａｔｉｏｎ　ｎｅｔｗｏｒｋ　ｇｒｏｗｔｈ　ａｌｇｏｒｉｔｈｍ。ｃｏｎｖｅｘ　ｈｕｌｌ　ａｌｇｏｒｉｔｈｍ。ｆｒｏｎｔ　ｅｄｇｅ　ｐｕｓｈ　ａｌｇｏｒｉｔｈｍ　ａｎｄ　ｇｒｅｅｄｙ　ａｌｇｏｒｉｔｈｍ）ｔＯ　ｃｏｍｐａｒｅ　ａｎｄ　ａｎａｌｙｚｅ　ｔｈｅ　ａｄｖａｎｔａｇｅｓ　ａｎｄ　ｓｈｏｒｔｃｏｍｉｎｇｓ　ｏｆ　ｄｉｆｆｅｒｅｎｔ　ａｌｇｏｒｉｔｍｓ．ｈ　Ｋｅｙｗｏｒｄｓ：ＴＩＮ　Ｔｒｉａｎｇｕｌａｔｉｏｎ　ｎｅｔｗｏｒｋ　ｇｒｏｗｔｈ　ａｌｇｏｒｉｔｈｍ　Ｃｏｎｖｅｘ　ｈｕｌｌ　ａｌｇｏｒｉｔｈｍ　Ａｌｇｏｒｉｔｈｍ　Ｇｒｅｅｄｙ　ａｌｇｏｒｉｔｈｍ　ｏｆ　ａｄｖａｎｃｉｎｇ　ｆｒｏｎｔ　ｅｄｇｅ　１　ＴＩＮ模型概念　不规则三角网是按一定的规则将离散点连接成覆盖整个　壳，然后相邻凸壳进行三角剖分并优化。其基本过程为：　①求出数据中的所有凸壳顶点；　②从内到外，对相邻的凸壳进行三角连接，直到最外一个　凸壳为止；　区域且互不重叠、结构最佳的三角形，实际上是建立离散点之　间的空间关系。每个三角平面表示地形面的一部分，三角形的　形状和大小取决于不规则分布的高程数据点的位置和密度。　通常情况下，采样点应尽量均匀分布，但地形面转折处的点（如　山峰、山脊、沟槽和峡谷）一定要测到位，否则就无法表示出准　确的地形表面特征。　③对三角形进行排序，从第一个三角形开始，对其各边有　公共边的三角进行优化，直到最后一个三角形。　（３）前沿边推进算法　前沿边推进算法的基本思想是以包括所有凸壳的每一条　边作为新生成的三角形的边，向凸壳内“推进”，找到满足　Ｄｅｌａｕｎａｙ构网法则的点，直到最后一个凸壳（或一个点、或两个　点）。其基本过程为：　①对平面中的所有点找出最外层凸壳；　②以最外层凸壳的每条边向内寻找距离该条边最近的点，　２建立ＴＩＮ的几种算法简述　建立ＴＩＮ的算法有很多种，如常用的不规则三角网算法　有Ｄｅｌａｕｎａｙ三角剖分法、径向扫描法、区域生成法、逐点插入　法、三角网生长算法、分治算法、凸壳算法、前沿边推进算法和　贪心算法等。这里仅以三角网生长法、凸壳算法、前沿边推进　算法和贪心算法四种算法简述如下。　（１）三角网生长算法　三角网生长算法是由Ｂｒａｓｓｅｌ和Ｒｅｉｆ在１９７９年提出的，该　算法是从任意一点开始，在一维排序链表中以循环搜索方式查　组成新的三角形并存储下来；　③以新找出的点组成凸凹壳，重复②步，直到最后一个凸　凹壳（一个点或两个点另外处理）。　（４）贪心算法　出此任意点的泰森邻域点。其基本过程为：　①在数据中取任意一点，查找距离此点最近的点，相连后　作为初始基线；　贪心算法是凸壳算法和三角网生长算法相结合构成的。　其基本过程为：　①对平面中所有坐标求出最外层凸壳，将凸壳点一一　记录下来；　．②计算此基线的中点平面坐标，以此点查找距离它最近的　点并作为第三点生成第一个三角形；　②除去最外层凸壳点，在平面内找任意一点，找出与它距　离最近的点；　③以三角形的三边作为新的基线向外扩展，并对三角形的　每条边计数，任意相同一条边最多可以使用两次；　④重复过程②、③步直至所有基线处理完毕。　（２）凸壳算法　凸壳算法是对平面中的所有离散点从外到内找出每个凸　作者简介：陈素，女，１９７７年５月出生，助工。　收稿日期：２Ｏｌｌ—ｌ１一Ｏ７　③求这两点的中点，找出与中点距离最近的点，将这三点　归为第一个三角形；　　．④以第一个三角形的三边作为扩展边向外扩展，直到每条　边都用了两次为止（最外层凸壳除外）。　３　ＴＩＮ的数据结构　建立不规则三角网数字高程模型，首先要存贮每个点ｘ、　Ｙ、ｚ三维坐标，然后要存贮网点连接的拓扑关系、三角形及邻　接三角形等信息。常用的不规则三角网存贮结构为直接表示　三角形及邻接关系的结构。如表１、表２、表３所示：　

２０１１年１２期总第１６２期　２　１　２　３　４　５　色　２　６　３　５　～　¨　．　¨　．　¨　．　陈素－建ＴＩＮ的几种算法比较　维塞髹囊号、　表２三角形表　表３邻接三角形表　１　乱　①第一步，对平面所有点求凸壳并找出各凸壳之间所有的　三角形。　３　１　５　３　Ｎｏ　Ｘ　Ｙ　Ｚ　２　３　　ＰｚＮｏ　ＰＩ　Ｐａ　＆　色　色　５　１　４　Ｎｏ　ＡＩ　△２　Ａａ　ｊ一２　对第一圈第二点开始　４５０：Ｆｏｒ　ｉ一１　Ｔｏ　ＩｔｅｍＣｏｕｎｔ　从其余点中找下一点　Ｈ（ＰｏｉｎｔｌＤ（ｉ）＜＞Ｄｅｌｌ（Ｑ，ｊ））Ａｎｄ（ＰｏｉｎｔｌＤ（ｉ）＜＞　Ｄｅｌｌ（Ｑ，（ｊ一１）））Ｔｈｅｎ　１　２　３　４　５　¨　弘　一　’计算三角形的三边长ａａＬ、ｂｂＬ和ｃｃＬ，分为角度大于９Ｏ。　０　∞　～　０　似　～　１　２　３　４　５　¨　这种数据结构由离散点三维坐标、三角形及邻接三角形等　三个表构成，每个三角形都作为数据记录直接存贮，并用指向　弘　一　三角离散点的编号来表示。三角形中三边相邻的三角都作为　他　∞　～　数据记录直接存储，并用指向相应的三角形的编号来表示。　这种数据结构最早由Ｇｏｌ０　弘　踮　ｄ，ＭｃＣｕｌｌａｈｈ及Ｔａｒ一　ｖｙｄａｓ等人提出　并使用，其最大特点是检索网点拓扑关系效率高，便于等高　线内插、ＴＩＮ快速显示与局部结构分析，但其缺点是数据存　贮量较大。　４建立ＴＩＮ的几种算法比较及实例演示　三角网生长算法的优点是所建立的不规则三角网是直接　进行的最大优化的，但该算法大部分的计算时间都花费在基于　给定基线在大量数据点中搜寻符合要求的邻域点上。所以该　算法的最大缺陷是在大数据量建ＴＩＮ时速度会非常缓慢。　凸壳算法的优点是对大数据量建ＴＩＮ时速度非常快，由　于在本算法中将建ＴＩＮ过程分成求所有凸壳、相邻凸壳进行　三角形连接和优化三个步骤，所以将算法中的循环层次降低　了，其缺陷是不规则三角网的优化过程较为复杂，想达到每个　三角形最优是非常困难的。　前沿边推进算法和贪心算法都是一种非常优秀的算法，它　不仅结合了凸壳算法中的优点，而且还结合了三角网生长算法　的优点。两种算法所耗的时间介于三角网生长算法和凸壳算　法之间。　下面分别就四种算法示例演示如下（数据文件格式为文　本格式）：　（１）三角网生长算法的部分代码如下：　Ｄｉｍ　ｘＭｉｎ　Ａｓ　Ｓｉｎｇｌｅ，ｙＭｉｎ　Ａｓ　Ｓｉｎｇｌｅ，ｘＭａｘ　Ａｓ　Ｓｉｎｇｌｅ，　ｙＭａｘ　Ａｓ　Ｓｉｎｇｌｅ‘定义ｘ、Ｙ的最大值和最小值；　Ｄｉｍ　Ｖｅｒｌ（）Ａｓ　Ｉｎｔｅｇｅｒ，Ｖｅｒ２（）Ａｓ　Ｉｎｔｅｇｅｒ，Ｖｅｒ３（）Ａｓ　Ｉｎｔｅｇｅｒ定义存放三角形的三个点集；　Ｄｉｍ　Ｘ（）Ａｓ　Ｓｉｎｇｌｅ，Ｙ（）Ａｓ　Ｓｉｎｇｌｅ，Ｚ（）Ａｓ　Ｓｉｎｇｌｅ　定义　打开文件中的ｘ、Ｙ、ｚ三个点集。　其建立的ＴＩＮ结果如图１所示：　图１三角网生长算法建ＴＩＮ　（２）凸壳算法部分代码算法如下：　或小于９０。两种情况　Ｉｆ（ａａＬ＋ｃｃＬ～ｂｂＬ＜一Ｏ）Ｔｈｅｎ　角度大于９Ｏ。　‘找出新的凸壳点　ｎｎ３一ＰｏｉｎｔＩＤ（ｉ）‘记录下此点　Ｅｎｄ　Ｉｆ　Ｉｆ（ａａＬ＋ｅｃＬ—ｂｂＬ＜＝Ｏ）Ｔｈｅｎ’角度小于９Ｏ。　‘找出新的凸壳点　ｎｎ３＝ＰｏｉｎｔＩＤ（ｉ）‘记录下此点　Ｅｎｄ　Ｉｆ　Ｅｎｄ　Ｉｆ　Ｉｆ　ｎｎ３＝ｎｎｌ　Ｔｈｅｎ’判断是否找完一圈点　Ｔｒｉ—Ｔｒｉ一１　ＤｅｌＤａｔａＮｕｍｂｅｒ（Ｑ，１）一Ｔｒｉ’记录每一圈凸壳点个数　Ｉｆ　ＩｔｅｍＣｏｕｎｔ—Ｔｒｉ一１　Ｔｈｅｎ　Ｅｘｉｔ　Ｓｕｂ判断是否只有一　个凸壳圈　Ｅｌｓｅ　Ｃａｌｌ　ＤｅｌＰｏｉｎｔＣｉｒ（Ｑ）　’　Ｅｎｄ　Ｈ　Ｅｌｓｅ　Ｔｆｉ—Ｔｆｉ＋１　ｊ—ｊ＋１‘凸壳包内的数据点－＇ｉ＇￣ＪＪｎ　１　ＰＡｎｇｌｅｍａｘ＝１　ＧｏＴｏ　４５０跳到上面重新执行程序，求出新的凸壳点　Ｅｎｄ　Ｉｆ　其建立的ＴＩＮ结果如图２所示（优化过程代码略）：　图３凸壳算法（优化）　（３）前沿边推进算法部分代码如下：　求出平面中所有点的最外层凸壳，以最外层凸壳的每条边　向内推进。　Ｆｏｒ　ｊ一１　Ｔｏ　ＩｔｅｍＣｏｕｎｔ‘在平面中应用Ｄｅｌａｕｎａｙ构网法　则求出每一个三角形的第三点　

２０１１年１２期总第１６２期　陈素・建ＴＩＮ的几种算法比较　ＴｒｉＥｘｔｅｎｄ（ｋ）　・１０４・　Ｉｆ（（ｊ＜＞ＥＩｅｌ１（Ｑ，ｉ））Ａｎｄ（ｊ＜＞Ｄｅｌ１（Ｑ，ｉ＋１）））　Ｔｈｅｎ　４５：ｊ１一ｊ１＋１　Ｉｆ　１一ｋ　Ｔｈｅｎ　ＧｏＴｏ　４５　ａａＬ一（ＤｅＩＸ（Ｑ，ｉ）一Ｘ（ｊ））　２＋（ＤｅｌＹ（Ｑ，ｉ）一Ｙ　（ｉ））　２　Ｉｆ（（（Ｖｅｒｌ（ｋ）：Ｖｅｒ１（ｊ１））０ｒ（ｖｅｒ１（ｋ）一Ｖｅｒ２（ｊ１））Ｏｒ（ｖｅｒ１　ｂｂＬ一（Ｄｅ１Ｘ（Ｑ，ｉ＋１）一ｘｑ））　２＋（Ｄｅ１Ｙ（Ｑ，ｉ＋　１）一Ｙ（ｊ））‘２　（ｋ）一Ｖｅｒ３（ｊ１）））Ａｎｄ（（（Ｖｅｒ３（ｋ）＝Ｖｅｒ１（ｊｉ））Ｏｒ（Ｖｅｒ３（ｋ）一　Ｖｅｒ２（ｊ１））Ｏｒ（Ｖｅｒ３（ｋ）一、　ｒ３（ｊ１）））））Ｔｈｅｎ　ＧｏＴｏ　５０　Ｉｆ　ｊ１＜１　Ｔｈｅｎ　ＧｏＴｏ　４５　ｎｌ—ｖｅｒ１（ｋ）：ｎ２一Ｖｅｒ３（ｋ）：ｎ３一Ｖｅｒ２（ｋ）：Ｃａｌｌ　ｃｃＬ＝（ＤｅｌＸ（Ｑ，ｉ＋１）一ＤｅｌＸ（１，ｉ））　２＋（Ｄｅ１Ｙ（Ｑ，　ｉ＋１）一ＤｅｌＹ（Ｑ，ｉ））　２　ＣＯＳＣ一１一（ａａＬ＋ｂｂＬ—ｃｃＬ）／（２　ｂｂＬ））　Ｓａｒ（ａａＬ＊　ＴｒｉＥｘｔｅｎｄ（’ｋ）　５Ｏ：ｊ２一ｊ２＋１　Ｉｆ　２一ｋ　Ｔｈｅｎ　ＧｏＴｏ　５０　Ｉｆ　ＣＯＳＣ＞ｔｔＴｈｅｎ　ｔｔ＝ＣＯＳＣ　ｋ＝ｊ‘找出第三角点为　最大角度的三角形　Ｅｎｄ　Ｉｆ　Ｅｎｄ　Ｉｆ　Ｎｅｘｔｊ　图４第一圈凸壳边找出的三角形　图５经凸凹壳向内推进并优化后的ＴＩＮ　（４）贪心算法的部分代码如下：　三角形的扩展　ｋ一１‘对三角形各边定权为１，第一个三角形向外扩展　ＴｒｉＥｘｔｅｎｄ（ｋ）　ｎｌ—Ｖｅｒ２（ｋ）：ｎ２＝Ｖｅｒ３（ｋ）：ｎ３一Ｖ盯１（ｋ）：Ｃａｌ１　ＴｒｉＥｘｔｅｎｄ（ｋ）　２０：ｋ＝ｋ＋１‘第二个至最后一个三角形的扩展　４Ｏ：ｊ—Ｊ＋１　Ｉｆ　—ｋＴｈｅｎＧｏＴｏ　４０　Ｉｆ（（（Ｖｅｒｌ（ｋ）＝Ｖｅｒｌ（ｊ））Ｏｒ（Ｖｅｒｌ（ｋ）：Ｖｅｒ２（ｊ））Ｏｒ　（Ｖｅｒｌ（ｋ）一Ｖｅｒ３（ｊ）））Ａｎｄ（（（Ｖｅｒ２（ｋ）：Ｖｅｒｌ（ｊ））Ｏｒ　（Ｖｅｒ２（ｋ）一Ｖｅｒ２（ｊ））Ｏｒ（Ｖｅｒ２（ｋ）＝Ｖｅｒ３（ｊ）））））Ｔｈｅｎ　Ｇｏ—　Ｔ０　４５　Ｉｆ　ｉ＜１　Ｔｈａｎ　ＧｏＴｏ　４０　ｎｌ—Ｖｅｒｌ（ｋ）：ｎ２：ｖｅｒ２（ｋ）：ｎ３一Ｖｅｒ３（ｋ）：Ｃａｌｌ　Ｉｆ（（（Ｖｅｒ２（ｋ）一Ｖｅｒｌ（ｊ２））Ｏｒ（Ｖｅｒ２（ｋ）＝Ｖｅｒ２（ｊ２））Ｏｒ　（Ｖｅｒ２（ｋ）一ｖｅｒ３（ｊ２）））Ａｎｄ（（（Ｖｅｒ３（ｋ）：Ｖｅｔ１（ｊ２））Ｏｒ　（Ｖｅｒ３（ｋ）＝Ｖｅｒ２（ｊ２））Ｏｒ（Ｖｅｒ３（ｋ）＝Ｖｅｒ３（ｊ２）））））Ｔｈｅｎ　ＧｏＴｏ　２５　ｆｉ２＜ｌＴｈｅｎＧｏＴｏ　５０　５５：ｎｌ—Ｖｅｒ２（ｋ）：ｎ２一Ｖｅｒ３（ｋ）：ｎ３：Ｖｅｒｌ（ｋ）：Ｃａｌｌ　ＴｒｉＥｘｔｅｎｄ（ｋ）　２５：Ｉｆ　ｋ＜ｌ　Ｔｈｅｎ　ＧｏＴｏ　２０　图６用贪心算法先求出最外层凸壳　不规则三角网ＴＩＮ是一种重要的数字高程模型，特别是　在顾及地形线特征的条件下，具有很高的精度和逼真度。本文　从四种建ＴＩＮ的基本思路和算法着手，依次用ＶＢ６语言将其　一一实现。在编程过程中除了参考有关书籍的算法外，另对有　些算法作了进一步改进和优化，特别是如何尽可能减少存储空　间，如何加快计算速度方面。但对提高显示地形的精度和用　ＴＩＮ模型逼真显示地形地物等问题还需进一步研究。　参考文献　［１］王来生，鞠时光，郭铁雄，等．大比例尺地形图机助绘图算法　及程序［Ｍ］．北京：测绘出版社，１９９３．　［２］周培德．计算几何一算法分析与设计［Ｍ］．北京：清华大学出　版社，２０００．　［３］王家耀．空间信息系统原理［Ｍ］．北京：科学出版社，２００１．