第３３卷第２期 测绘与空间地理信息 Ｖ０１．３３．Ｎｏ．２ ２０１０年４月 ＧＥＯＭＡＴＩＣＳ＆ＳＰＡＴＩＡＬ ｌＮＦｏＲＭＡＴＩｏＮ ＴＥＣＨＮＯＬＯＧＹ Ａｐｒ．，２０１０ 不规则三角网生成算法及其应用探讨 李梅 ，张学雷 （１．郑州大学水利与环境学院，河南郑州４５０００１； ２．郑州大学自然资源与生态环境研究所，河南郑州４５０００１）） 摘要：不规则三角网（ＴＩＮ）是数字高程模型的一个重要表示方法，其传统算法一再被优化，也得到广泛地应用。 本文在传统算法的基础上总结了一些改进算法，并且提出了相关的应用前景。 关键词：ＴＩＮ；生成算法；Ｄｅｌａｕｎａｙ三角网 中图分类号：Ｐ２３５．１ 文献标识码：Ｂ 文章编号：１６７２—５８６７（２０１０）０２—００４４—０２ ． Ｒｅｓｅａｒｃｈ ｏｎ ｔｈｅ Ａｌｇｏｒｉｔｈｍ ｏｆ ＴＩＮ Ｂｕｉｌｄｉｎｇ ａｎｄ ｉｔｓ Ａｐｐｌｉｃａｔｉｏｎ ＬＩ Ｍｅｉ ｌ－．ＺＨＡＮＧ Ｘｕｅ—ｌｅｉ’， （１．Ｓｃｈｏｏｌ ｏｆ Ｈｙｄｒａｕｌｉｃ ａｎｄ Ｅｎｖｉｒｏｎｍｅｎｔａｌ Ｅｎｇｉｎｅｅｒｉｎｇ ｏｆ Ｚｈｅｎｇｚｈｏｕ Ｕｎｉｖｅｒｓｉｔｙ，Ｚｈｅｎｇｚｈｏｕ ４５０００１，Ｃｈｉｎａ； ２．Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｎａｔｕｒａｌ Ｒｅｓｏｕｒｃｅｓ ａｎｄ Ｅｃｏ—ｅｎｖｉｒｏｎｍｅｎｔ ｏｆ Ｚｈｅｎｇｚｈｏｕ Ｕｎｉｖｅｒｓｉｙｔ，Ｚｈｅｎｇｚｈｏｕ ４５０００１，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：ＴＩＮ ｉｓ ａｎ ｉｍｐｏｒｔａｎｔ ｍｅｔｈｏｄ ｔｏ ｅｘｐｒｅｓｓ ＤＥＭ，ｗｈｏｓｅ ｔｒａｄｉｔｉｏｎａｌ ａｌｇｏｒｉｔｈｍｓ ｈａｖｅ ａｌｒｅａｄｙ ｂｅｅｎ ｏｐｔｉｍｉｚｅｄ ｃｏｎｓｔａｎｔｌｙ ａｎｄ ｂｅｅｎ ａｌｓｏ ａｐｐｌｉｅｄ ｗｉｄｅｌｙ．Ｔｈｉｓ ｐａｐｅｒ ｉｎｔｒｏｄｕｃｅｄ ｓｏｍｅ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍｓ ｂａｓｅｄ ｏｎ ｔｒａｄｉｔｉｏｎａｌ ａｌｇｏｒｉｔｈｍｓ ａｎｄ ｂｒｏｕｇｈｔ ｆｏｒｗａｒｄｓ ｓｏｍｅ ｒｅｌａｔｉｖｅ ｐｅｒｓｐｅｃｔｉｖｅ ｏｆ ｔｈｅ ａｐｐｌｉｃａｔｉｏｎｓ． Ｋｅｙ ｗｏｒｄｓ：ＴＩＮ；ａｌｇｏｒｉｔｈｍ ｏｆ ｂｕｉｌｄｉｎｇ；Ｄｅｌａｕｎａｙ ０引 言 系列相连的但不重叠的三角形的集合，而且这些三角形 的外接圆不包含这个面域的其他任何点 。构造ＴＩＮ的 数字地面模型（ｄｉｇｉｔｌａ ｔｅｒｒａｉｎ ｍｏｄｅｌｓ，简称ＤＴＭ）是以 方法一般都归结到Ｄｅｌａｕｎａｙ三角网，１９３４年，数学家 数字的形式存储地球表面上所有信息的总和，是描述地 Ｂ．Ｄｅｌａｕｎａｙ由Ｖｏｒｏｎｏｉ图演化出了更易于分析应用的 面诸特征空间分布的数值的集合。主要用于描述地面起 Ｄｅｌａｕｎａｙ三角网（如图１所示），它具有以下性质： 伏的状况，可用于提取各种地形参数，如坡度、坡向、粗糙 度等，并进行通视分析、流域结构生成等应用分析 。 ＤＴＭ的表示方法主要有３种：等高线、规则格网和不 规则三角网（ＴＩＮ）。其中，ＴＩＮ具有高精度、高效率和易 于处理地形线等特点，它是按一定的规则将离散点连接 成覆盖整个区域且互不重叠、结构最佳的三角形，建立离 散点之间的空间关系。其目的是克服利用离散点计算地 球表面上任意点高程的困难，近年来得到较快的发 图１虚线是Ｖｏｒｏｎｏｉ图。实线是Ｄｅｌａｕｎａｙ图 展 －４］。ＴＩＮ的构建方法已经成为ＧＩＳ的一个研究热点， Ｆｉｇ．１ Ｖｏｒｏｎｏｉ ｃｈａｒｔ（ｄｏｔｔｅｄ ｌｉｎｅ）ａｎｄ 一些改进算法也陆续的被提出。 Ｄｅｌａｕｎａｙ ｃｈａｒｔ（ｓｏｌｉｄ Ｈｎｅ） Ｄｅｌａｕｎａｙ三角网及传统算法 １）唯一性 Ｄｅｌａｕｎａｙ三角网具有良好的形态，在表达地表形态方 即不论从何处开始联网，最终将得到一致的结果。 面表现较为出色 ，是目前公认的最优的三角网，它是一 ２）空圆特性 收稿日期：２００９—０６—２０ 基金项目：河南省重大公益基金项目（０８１１００９１１６００—１）资助 作者简介：李梅（１９８５一），女，湖北孝感人，地理信息系统与地图学专业在读硕士研究生，主要研究方向为地理信息与资源评价。 第２期 李梅等：不规则三角网生成算法及其应用探讨 ４５ 即在任意一个三角形的外接圆范围内不包含点集Ｍ 中的任何其他点。 ３）最大最小角特性 即如果任意两个相邻三角形组成的凸四边形的对角 线可以互换的话，那么可以获得等角性最好的三角形。 这些性质决定了Ｄｅｌａｕｎａｙ三角网是最优的，具有极 减少搜寻时间，彭李 ” 等人提出了一种以动态正方形 的方式限定目标点的搜索范围，即以扩展基边的中点坐 标为中心做正方形，正方形的大小根据参与构网的点数 及点的密度动态确定，将搜寻范围定位于正方形内。在 正方形内找一点，使得该点在扩展边的右边，且与基边两 端点连成直线的夹角最大。经验证该算法稳定，构网速 度明显提高。 大的应用价值Ｈ 。 根据实现过程，把生成Ｄｅｌａｕｎａｙ三角网的各种算法 徐青 等提出了一种基于自适应分块思想的ＴＩＮ三 分为逐点插入法、三角网生长法和分治算法等３类。 Ｌａｗｓｏｎ提出的逐点插入法，Ｌｅｅ和Ｓｃｈａｃｈｔｅｒ等人先 后进行了改进和完善，该算法的思路比较简单，先建立初 始三角网，然后将余下的点逐一插入，Ｌａｗｓｏｎ提出的局部 最优化方法（ＬＯＰ）确保了Ｄｅｌａｕｎａｙ三角网的生成。该算 法虽然容易实现，空间要求也不大，但是时间效率较低。 Ｇｒｅｅｎ Ｓｉｂｓｏｎ首次实现了Ｄｅｌａｕｎａｙ三角网的生长算法，其 基本思路是，首先找出点集中相距最短的两点连线成为 一条Ｄｅｌａｕｎａｙ三角网的边，然后按照Ｄｅｌａｕｎａｙ三角网的 判断法则找出包含此边的另一端点，依次处理所有生成 的边，直至最后完成。该算法的优点是占用内存空间较 小，但时间效率也较低。Ｓｈａｍｏｓ和Ｈｏｅｙ提出的分治算法 基本思路是递归地分割点集至足够小，使其易于生成三 角网，然后把子集中的三角网合并，经优化生成最终的三 角网。该算法的优点是时间效率高，但需要大量递归运 算，因此占用内存空间较多。 ２算法的改进 由于以上算法各有不足，相关的学者陆续做出了很 多的改进，向传杰＂ 等采用将采样数据分块建网再合并 的技术，建网和合并都遵循Ｄｅｌａｕｎａｙ原则，使得建网的效 率与整张网采样点数量增长在一定范围内呈线性递减， 从而大大提高了建网效率。另外一种方法就是章孝灿提 出的利用凸壳构建ＴＩＮ，其原理为 ：将用于建网的点集 划分为互不相交的凸壳，生成凸壳集，然后从里到外进行 凸壳或凸壳问环域的剖分，并在此过程中逐渐优化，最后 得到三角网。其实质就是从里到外不断地进行凸壳三角 剖分并优化的过程。利用从总体到局部，先控制后细部 的思想，提高了点集建ＴＩＮ的速度。唐丽玉 等针对李 伟青提出的以有序点为着眼点的三角化方法中存在着大 量交点测试以及优化的不合理，效率不高的问题，借助 ｃ＋＋语言中的标准模板库ＳＴＬ，采用凸壳技术算法，充分 利用有序点集的凸壳特性，采用拓扑结构进行优化，从而 大大提高了ＴＩＮ的生成速度。 姚圣华等 对凸壳剖分的算法进行了改进，即提出了 一种利用凸壳直径对凸壳进行剖分的算法，剖分时直接将 凸壳直径顶点与其前后两点组成三角形。并基于“分而治 之”的思想提出了一种格网数据筛选法（每次求凸壳时，将 不可能成为凸壳顶点的数据弃之不用），极大地提高了利用 凸壳建ＴＩＮ的速度，经测试，该算法表现出色。 由于传统算法中大部分时间都是在大量离散数据中 搜寻符号要求的邻域点，极大地降低了构网速度。为了 角网构建算法，结果表明该算法建立的三角网无交叉和 重复，具有Ｄｅｌａｕｎａｙ三角网的特性，有较高的执行效率。 宋哲 等在三角剖分算法的基础上，提出在三角化 前，将数据域划分为矩形网格，在数据点以及在运算过程 中产生的三角形对应的矩形域中快速地找到包含新加入 点的三角形。并且运用ｃ＋＋６．０编程实现了本算法，证 明该算法生成的ＴＩＮ模型满足Ｄｅｌａｕｎａｙ规则，精度高，能 够较好地反映地性线特征。 另外，对无约束条件生成的数字高程模型不能正确 表达地表的复杂关系，也不能满足实际应用的需要的这 些问题，朱庆、刘学军等将无约束的原始数据与约束数据 一起构网取得了较好的效果，江帆 等针对可能出现的 平三角情况，根据等高线间的相关关系，设计了自动提取 特征点的算法，进行了ＴＩＮ的优化，快速消除平三角形，取 得了较好的效果。张立朝” 等提出一种平三角修正算法 来修正模型中可能出现的平三角区域，结果表明该算法 效果很好，而且生成的三角网对地形描述更为精确。刘 少华 等在基于自适应分块建立网格索引算法过程中， 提出了一种空外接圆判断的简易表达式，简化了ＴＩＮ的 优化过程，提高了构网速度。 ３不规则三角网的应用 ＴＩＮ模型已经有很广泛的应用领域，例如在铁路公路 的勘察和设计工作，绘制断面图和坡面图等，实质都是分 析或研究２维或３维空间离散点数据的分布情况。 简季 等利用不规则三角网模型对区域温度进行建 模，利用空间场的自相关性，通过相邻采样点来局部插值 出未知点的温度值，从而达到了通过离散的温度特征点 对区域温度分布状况进行掌控的目的。在对成都理工大 学主校区的实验结果表明，ＴＩＮ模型在温度场中的应用效 果良好。且与传统方法相比，具有调查时间短，可重复性 强，经济效益好等特点。王建民¨ 、韦廖军 ｊ、王丽华 等利用ＴＩＮ建立了储煤场的３维模型，运用双层Ｄｅｌａｕｎａｙ 三角剖分的方法计算底面不平的煤堆的体积，并且设计 开发了相应的系统，证明了该方法的可行性。李顺新 等利用不规则三角网绘制等值线的方法在ＭａｐＸ图层上 生成三峡雨量等值线，结果表明该方法保证了较高的精 度，而且节省了人力物力。张继令 将不规则三角网应 用于岩溶探测，异常值处理可靠，精度较高。不仅如此， ＴＩＮ模型在地理信息系统虚拟现实中也有应用，能够有效 地表达城市３维实体及其空间关系。而且，笔者认为在任 （下转第４８页） ４８ 测绘与空间地理信息 ２０１０年 分析和操作进行控制；服务器响应了用户的请求以后，用 户即可进行数据的分析操作，而无须再通过Ｉｎｔｅｒｎｅｔ传送 信息。 但是，由于客户机通常缺乏处理大型和复杂数据集 的能力，在客户机上运行复杂的ＧＩＳ分析操作，会影响数 据分析的质量；同时，对于非专业的用户，由于缺少培训 他们可能难以正确地操作数据和使用ＧＩＳ分析功能；而且 服务器针对每一个用户的需求都要进行大量数据的传 主要在服务器端完成数据操作，从而提供持续的数据请 求和传输。 混合模型的特点在于：当需要执行大数据的处理和 分析时，可以在高性能的服务器上执行；当需要由用户来 控制处理任务的时候，则可在客户端进行。在这种混合 模型中，客户端和服务器共享彼此的功能，数据和应用程 序可以根据不同的需要，让来自客户端的请求，或者在客 户端执行，或者在服务器执行，从而使系统的执行效率达 输，这样就造成了网络的繁忙而影响了系统的响应时间。 到最优化 。 ２．３混合模型 单纯的瘦客户端模式和胖客户端模式都存在着明显 ３结束语 的不足：对于瘦客户端模式，当需要频繁的数据传输时， 通过以上分析我们可以看出，瘦客户端模型主要适 系统的执行效率将会受到带宽和网络流量的制约；对于 用于一般用户，这类用户对ＧＩＳ分析能力要求不是很高， 胖客户端模式，系统的执行效率将受到客户端运算能力 仅仅完成一些图形的放大、缩小、查询、浏览等功能即可。 的影响，当处理需求和处理能力之间发生矛盾时，执行效 而胖客户端模型则对客户端的要求比较高，因此比较适 率将会大大降低。因此，将两种模式的优点结合在一起 用于局域网范围内那些比较专业的ＧＩＳ用户，使得用户能 构成一种混合模式是解决这些问题的一种理想方法。混 够完成数据的上传、更新和数据制作等功能。 合模型的数据处理过程如图３所示。 针对空间数据的特点，我们可以采取混合模型来进 行基于ＷｅｂＧＩＳ的空间数据发布，通过身份认证来界定用 Ｗｅｂ浏览器 ① ① ＧＩＳ ＩＰｌｕｇ一１ｎ Ｉ 户的身份，一般用户将采用瘦客户端的模式来对数据进 ② 服 ② － Ｗｅｈ － 应用服务器 Ｉ ＡＳＰ Ｉ 行操作，而会员用户将会采用胖客户端的模式来对数据 ＩＡｃｔｉｖｅ＿Ｘ Ｉ 务 ｌ Ｓｅｒｖｌｅｔ ｌ 进行操作。根据不同用户的需求，采用不同的数据发布 Ｉ Ｊａｖａ－Ａｐｐｌｅｔ Ｉ ．． 器 √ Ｉ ＪＳＰ Ｉ 模式，这种混合模型充分发挥了客户机和服务器的最优 性能，更好地实现了空间数据的发布。 图３混合模式数据发布实现模型 参考文献： Ｆｉｇ．３ Ｉｍｐｌｅｍｅｎｔ Ｍｏｄｅｌ ｏｆ Ｍｉｘ—ｍｏｄｅ Ｄａｔａ Ｐｒｏｍｕｌｇａｔｉｏｎ ［１］杨超伟，李琦．Ｗｅｂ空间信息发布研究［Ｊ］．北京大学学 报：自然科学版，２００１，３７（３）：４１３—４２０． ［２］ 马冠锋．基于ＡｒｃＩＭＳ的ＷｅｂＧＩＳ技术在青岛电力通讯系 ①客户端发出数据请求； 统中的应用研究［Ｄ］．武汉：武汉大学，２００５． ②按照用户的请求，一部分数据和小应用程序返回， ［３］ 尚颖娟．基于ＡｒｃＩＭＳ的ＷｅｂＧＩＳ研究与应用［Ｄ］．武汉： 在客户端完成对数据的各项操作； 武汉大学，２００５． ③对于一些大数据量和复杂的数据请求，系统将会 ［责任编辑：栾丽杰】 （上接第４５页） 何可作为离散点处理的环境中，都可以用到不规则三角 王家耀．空间信息系统原理［Ｍ］．北京：科学出版 网，比如声音、图像。 社，２００４． 胡金星，潘懋，马照亭，等．高效构建Ｄｅｌａｕｎａｙ三角网数 ４结束语 字地形模型算法研究［Ｊ］．北京大学学报（自然科学 本文就ＴＩＮ的生成算法及其应用作了概括，目前对 版），２００３，３９（５）：７３６—７４２． 于ＴＩＮ的算法优化研究仍是一个热点话题，如何进一步 邵春丽，胡鹏，黄承义，等．Ｄｅｌａｕｎａｙ三角网的算法详述及 提高精度，节省时间，并且考虑怎样将其应用于声音图像 其应用发展前景［Ｊ］．测绘科学，２Ｏ０４，２９（６）：６８—７１． 等领域都值得我们去研究。 向传杰，朱玉文．一种高效的Ｄｅｌａｕｎａｙ三角网合并生成 技术［Ｊ］．计算机应用，２００２，２２（１１）：３４—３９． 参考文献： 程效军，孙晋岳．基于凸壳的ＴＩＮ建立技术［Ｊ］．东北测 绘，２００１，２４（１）：６—９． ［１］邬伦，刘瑜，张晶，等．地理信息系统——原理、方法和 姚圣华，方源敏．利用凸壳建ＴＩＮ的算法研究［Ｊ］．昆明 应用［Ｍ］．北京：科学出版社，２００１． 理工大学学报（理工版），２００６，３１（２）：８—１３． ［２］李志林，朱庆．数字高程模型［Ｍ］．武汉：武汉大学出版 刘少华，彭李，何贞铭，等．基于搜索范围动态确定ＴＩＮ 社，２００１． 的一种构建算法［Ｊ］．测绘与空间地理信息，２００７，３０ ［３］唐丽玉，朱泉锋，石松．基于ＳＴＬ的Ｄｅｌａｕｎａｙ ＴＩＮ构建的 （３）：ｌ９—２０． 研究与实现［Ｊ］．遥感技术与应用，２００５，０２（３）：３４６—３４９． （下转第５１页）
