不规则三角网(TIN)生成的算法

第五章 不规则三角网（TIN）生成的算法
5.1.1 递归生长法
递归生长算法的基本过程为如图 5.1.1 所示：
3 2
1
3 2
1
（a）形成第一个三角形 (b) 扩展生成第二个和第三个三角形 图 5.1.1 递归生长法构建 Delaunay 三角网
（1）在所有数据中取任意一点 1（一般从几何中心附近开始），查找 距离此点最近的点 2，相连后作为初始基线 1-2；
（2）在初始基线右边应用 Delaunay 法则搜寻第三点 3，形成第一个 Delaunay 三角形；
（3）并以此三角形的两条新边（2-3，3-1）作为新的初始基线； （4）重复步骤（2）和（3）直至所有数据点处理完毕。 该算法主要的工作是在大量数据点中搜寻给定基线符合要求的邻域 点。一种比较简单的搜索方法是通过计算三角形外接圆的圆心和半径来完 成对邻域点的搜索。为减少搜索时间，还可以预先将数据按 X 或 Y 坐标分 块并进行排序。使用外接圆的搜索方法限定了基线的待选邻域点，因而降 低了用于搜寻 Delaunay 三角网的计算时间。如果引入约束线段，则在确定 第三点时还要判断形成的三角形边是否与约束线段交叉。
1

5.1.2 凸闭包收缩法
与递归生长法相反，凸闭包搜索法的基本思想是首先找到包含数据区 域的最小凸多边形，并从该多边形开始从外向里逐层形成三角形网络。平 面点凸闭包的定义是包含这些平面点的最小凸多边形。在凸闭包中，连接 任意两点的线段必须完全位于多边形内。凸闭包是数据点的自然极限边界， 相当于包围数据点的最短路径。显然，凸闭包是数据集标准 Delaunay 三角 网的一部分。计算凸闭包算法步骤包括：
（1）搜寻分别对应 x-y，x+y 最大值及 x-y，x+y 最小值的各二个点。 这些点为凸闭包的顶点，且总是位于数据集的四个角上，如图 5.1.2（a）中的点 7，9，12，6 所示；
（2）将这些点以逆时针方向存储于循环链表中； （3）对链表中的点 I 及其后续点 J 搜索线段 IJ 及其右边的所有点，计
算对 IJ 有最大偏移量的点 K 作为 IJ 之间新的凸闭包顶点，如点 11 对边 7-9。 （4）重复（2）-（3）直至找不到新的顶点为止。
（a）初始边界 7，9，12，6；（b）搜索凸闭包顶点 11，5，4；（c）凸闭包 图 5.1.2 凸闭包的计算(引自 Tsai，1993)
一旦提取出数据区域的凸闭包，就可以从其中的一条边开始逐层构建 三角网，具体算法如下：
2

(a)第一个三角形 (b)第一层三角形 图 5.1.3 凸闭包收缩法形成三角网
(1) 将凸多边形按逆时针顺序存入链表结构，左下角点附近的顶点排 第一；
(2) 选择第一个点作为起点，与其相邻点的连线作为第一条基边，如 图 5.1.3（a）中的 9-5；
(3) 从数据点中寻找与基边左最邻近的点 8 作为三角形的顶点。这样 便形成了第一个 Delaunay 三角形；
(4) 将起点 9 与顶点 8 的连线换作基边，重复(3) 即可形成第二个三 角形；
(5) 重复第(4)步，直到三角形的顶点为另一个边界点 11。这样，借助 于一个起点 9 便形成了一层 Delaunay 三角形；
(6) 适当修改边界点序列，依次选取前一层三角网的顶点作为新起点， 重复前面的处理，便可建立起连续的一层一层的三角网。
该方法同样可以考虑约束线段。但随着数据点分布密度的不同，实际 情况往往比较复杂。比如边界收缩后一个完整的区域可能会分解成若干个 相互独立的子区域。当数据量较大时如何提高顶点选择的效率是该方法的 关键。
5.2 数据逐点插入法
5.1 节介绍的三角网生长算法最大的问题是计算的时间复杂性，由于每 个三角形的形成都涉及所有待处理的点，且难于通过简单的分块或排序予 以彻底解决。数据点越多，问题越突出。本节将要介绍的数据逐点插入法 在很大程度上克服了数据选择问题。其具体算法如下（见图 5.2.1）：
（1） 首先提取整个数据区域的最小外界矩形范围，并以此作为最简 单的凸闭包。
（2） 按一定规则将数据区域的矩形范围进行格网划分，为了取得比 较理想的综合效率，可以限定每个格网单元平均拥有的数据点 数。
（3） 根据数据点的（x,y）坐标建立分块索引的线性链表。 （4） 剖分数据区域的凸闭包形成两个超三角形，所有的数据点都一
定在这两个三角形范围内。
3

（5） 按照（3）建立的数据链表顺序往（4）的三角形中插入数据点。 首先找到包含数据点的三角形，进而连接该点与三角形的三个 顶点，简单剖分该三角形为三个新的三角形。
（6） 根据 Delaunay 三角形的空圆特性，分别调整新生成的三个三 角形及其相邻的三角形。对相邻的三角形两两进行检测，如果 其中一个三角形的外接圆中包含有另一个三角形除公共顶点 外的第三个顶点，则交换公共边。
（7） 重复（5）-（6）直至所有的数据点都被插入到三角网中。
（a）第一分块数据插入后 (b) 第二分块数据插入后 (c)全部三角形 图 5.2.1 逐点插入法构建 Delaunay 三角网
可见，由于步骤（3）的处理，保证相邻的数据点渐次插入，并通过搜 寻加入点的影响三角网（Influence Triangulation），现存的三角网在局部范 围内得到了动态更新。从而大大提高了寻找包含数据点的三角形的效率。
5.3 带约束条件的 Delaunay 三角网
当不相交的地形特征线、特殊的范围边界线等被作为预先定义的限制 条件作用于 TIN 的生成当中时，必须考虑带约束条件的 Delaunay 三角网。 最简单的处理方法是所谓的“加密法”，即通过加密约束线段上的数据点， 将约束数据转换为普通数据，从而按标准 Delaunay 三角形剖分即可。尽管 该方法加大了数据量并改变了原始数据集，但由于简单易行、稳定可靠， 在许多情况下可以很好地满足需要。该方法唯一的问题在于如何恰当地确 定特征线上加密数据点之间的距离，一般取平均数据点间距的一半或更小 即可。以下内容主要介绍直接处理约束线段的算法。
4

5.3.1 带约束条件的 Delaunay 三角网的定义
定义 1：给定一个 d 维欧基里德空间 E 和一个 N 点 mi 集 M。那么， 关联的 Voronoi 图 (又称 Thiessen 多边形 )为覆盖 E 的一个凸多边形序列 (V(m1 )，V(m2 )，…，V(m N))，其中，V(mi)包括 E 中所有以 M 中的 mi 为最近点的点，即 V(mi)=p∈E∶ Vj，1≤j≤N，d(p，mi)≤ d(p，mj)，d 表示欧基里德距离。Voronoi 图的几何对偶 (dual)，即把点 mi 联结起来而 得到的邻接格网称为 M 的 Delaunay 三角网。显然，Delaunay 三角网的元 素之并等于 M 的凸包之内部。Delaunay 三角网自然推广到输入数据不仅包 括点集 M，还包括不相交叉的直线段集 L。在计算几何里，这类问题称约 束 Delaunay 三角网（Constrained Delaunay Triangles，简称 CDT）问题。 对地形数据来说，L 即地形特征线段集（朱庆，陈楚江，1998）。
定义 2：令单点集 M 和线段端点集 E 之并为 V（V=M∪E），如果在 V 的每个 Delaunay 三角形的外接圆范围内不包含任何与三角形的顶点均通 视的其它点，而点 Pi 与 Pj（Pi，Pj∈V）当且仅当连线 PiPj 不与 L 中的任 何约束线段相交叉（除在端点处外）时才互相通视，那么称这个 Delaunay 三角网为 V 由 L 约束的 Delaunay 三角网（朱庆，陈楚江，1998）。
5.3.2 带约束条件的 Delaunay 法则
带约束条件的三角网仍然满足 Delaunay 法则，但其局部等角特性有较 小的改变。当需要考虑约束条件时，可视图有助于重新定义 Delaunay 法则 和 Lawson LOP 交换原则。对数据点及作为约束条件的断裂线，可视图由 互相可视的任意两点连接而成。在可视图中，除在断裂线的端点处外，连 接线与任一断裂线都不相交（图 5.3.1）。由此 Delaunay 法则及 Lawson LOP 交换可以重新定义为：
带约束条件的 Delaunay 法则：只有当三角形外接圆内不包含任何其 它点，且其三个顶点相互通视时，此三角形才是一个带约束条件的 Delaunay 三角形。
带约束条件的 DelaunayLawson LOP 交换：只有在带约束条件的 Delaunay 法则满足的条件下，由两相邻三角形组成的凸四边形的局部最佳 对角线（Locally Optimal Diagonal）才被选取。
5

图 5.3.1 9 个点与两条约束线段的通视图(引自 Tsai，1993)
5.3.3 顾及线段约束的三角网生成算法
考虑线段约束可以在形成 Delaunay 三角形的同时进行，如根据带约束 条件的 Delaunay 法则建立静态三角网的生长算法就是如此。而采用更多的 方法是在动态生成三角网的基础上，采用两步法实现 CDT 的建立。所谓两 步法即分以下两步完成：
（1） 将所有数据包括约束线段上的数据点，建立标准的 Delaunay 三角网。
（2） 嵌入线段约束，根据对角线交换法 LOP 调整每条线段影响区 域内的所有三角形。
在作为约束条件的地形特征信息存在时，当标准 Delaunay 三角网建立 起来后，便可加入预先给定的约束线段以完成带约束条件的 Delaunay 三角 网的构建。如图 5.3.2 所示，下面步骤用于完成约束线段的插入：
（1） 在三角网中插入一约束线段； （2） 确定边界与约束线段相交的三角形，如果两个这样的三角形有
公共边，则将此公共边删除，最后形成约束线段的影响多边形； （3） 将影响多边形其它各顶点与约束线段的起始节点相连； （4） 应用带约束条件的 LOP 交换，更新影响多边形内的三角网，使
约束边成为三角网中的一边； （5） 重复步骤 1-4，直至所有约束线段都加入三角网中。
6

(a)插入线段 ab，搜索其影响多边形；（b）连接节点 a 与影响多边形的所 有顶点；（c）应用带约束条件的 Lawson LOP 交换对三角网进行优化；（d） 带约束线段 ab 的三角网 图 5.3.2 约束线段 ab 插入到已有 Delaunay 三角网的过程(引自 Tsai，1993)
5.3.4 从等高线生成三角网
等高线是一种特殊的特征线，等高线也可以作为约束线段。从等高线 生成三角网一般有三种算法：等高线离散点直接生成 TIN 方法、将等高线 作为特征线的方法、自动增加特征点及优化 TIN 的方法。等高线离散点直 接生成 TIN 方法直接将等高线上的点离散化，然后采用上面所讲的从不规 则点生成 TIN 的方法。但是由于这种算法只独立地考虑了数据中的每一个 点，而并未考虑等高线数据的特殊结构，所以会导致很坏的结果，如出现 三角形的三个顶点都位于同一条等高线上（即所谓的“平三角形”）或者三 角形某一边穿过了等高线这样的情况（图 5.3.3）。这些情形按 TIN 的特性 都是不允许的。因此，在实际应用中，这种算法很少直接使用。通常将等 高线作为特征线来构建三角网。
（a） 三角形与等高线相交；（b）三角形的三个顶点都位于同一条等高线上 图 5.3.3 对等高线进行不合理三角化的例子
将等高线作为特征线生成三角网一般有两种算法：将等高线作为特征 线的方法、自动增加特征点及优化 TIN 的方法。
7

将每一条等高线当作断裂线或结构线时，对三角形而言，至多只能从 同一等高线取两个点。图 5.3.4 显示了一个考虑等高线特性的 Delaunay 三 角网。
图 5.3.4 将等高线当作断裂线以建立三角网 自动增加特征点及优化 TIN 的方法是：仍将等高线离散化建立 TIN， 但采用增加特征点的方式来消除 TIN 中的“平三角形”，并使用优化 TIN 的方式来消除不合理的三角形比如三角形与等高线相交等，另外对 TIN 中 的三角形进行处理以使得 TIN 更接近理想化的情况。使用手工方式增加特 征点线，无论在效率方面，还是在完整性、合理性等方面都是很有限的。 因此需要设计一定的算法来自动提取特征点。这些算法的原理大都基于原 始等高线的拓扑关系。对 TIN 进行优化则需对三角形进行扫描判断并以一 定的准则进行合理化的处理。 由等高线重建地形的方法中使用骨架线可以保留曲线段之间的拓扑关 系。从等高线图生成的 Voronoi 图上提取骨架线，骨架线可用于提取附加 点以消除“平三角形”。附加点的高程可由估算获得。基于该方法可以估计 出合理的地形坡度，并且为 TIN 提取有意义的中间点（Gold，2000）。 从等高线图生成的 Voronoi 图上提取骨架线的原理如图（5.3.5）所示， 当 Delaunay 三角形的外接圆不包含 Voronoi 图的顶点时，Voronoi 图顶点在 骨架线上（图 5.3.5（a））；当 Delaunay 三角形的外接圆包含 Voronoi 图的 顶点时，Delaunay 三角形的边就是边界线（图 5.3.5（b））。
8

(a)
(b)
图 5.3.5 提取骨架线的原理（引自 Gold，2000）
图 5.3.6 提取骨架线后的等高线图（引自 Gold，2000）
提取等高线图的骨架线后（图（5.3.6）），还要估计骨架线上点的高
程，其原理如图（5.3.7）所示。假设 Z c 是有新增点的等高线高程， Z b 是
相邻等高线的高程，Z i 是待估计骨架点的高程，RR是参考圆的半径，Ri
是骨架点的半径，则高程 Z i 可由下式计算：
Zi ? Zc ? (Ri / RR) ? (Zc ? Zb ) / 2
（5.3.1）
9

图 5.3.7 骨架点高程估计原理（引自 Gold，2000）
图 5.3.8 骨架线高程（引自 Gold，2000） 图 5.3.9（a）中的“平三角形”扭曲了实际地形，而使用增加了骨架 点的等高线建立 TIN 并对 TIN 进行优化后，对地形表达的效果则要好得多
10

（图 5.3.9（b））。
（a）山谷和山顶区域的平三角形
（b）地形地貌的实际表达 图 5.3.9 从相同的等高线生成的不同的 TIN 模型（引自 Gold，2000）
5.4 基于栅格的三角网生成算法
前面几种方法都是由矢量方式来形成三角网，实际上使用栅格的方式 也可建立三角网。在栅格方式下，数学形态学方法是比较好的选择之一（陈 晓勇，1991；马飞，1996）。
5.4.1 形态变换原理
数学形态学（Mathematic Morphology）是 Matheron 和 Serra 于 1965
11

年创立的，主要用于研究数字影像形态结构特征与快速并行处理方法。通 过对栅格数据形态结构的变换而实现数据的结构分析和特征提取。其中二 值形态学（函数值域定义在 0 或 1）是将图形视作集合，通过集合逻辑运 算（交、并和补）与集合形态变换（平移、扩张和侵蚀），在结构元作用下 转换到新的形态结构。
如果将要建立 TIN 的区域与一幅数字影像相对应，凡是与数据点对应 的像素灰度值为 1，其它的像素灰度值为 0，则可对这个二值影像进行形态 变换建立 TIN。运用数学形态学建立 TIN，一般要有如下步骤：
用形态学建立 TIN，主要是为了确定相邻参考点间的拓扑关系，因而 只与点之间的相对距离有关，而与点之间的实际距离无直接关系。因此， 为了能快速处理，以参考点间的最小距离为像素大小，将内插区域转化为 一幅二值影像，参考点所在的像素灰度值为 1，其它像素的灰度值为 0。
5.4.2 泰森多边形的形成
设 X 为参考点像素集合，则除去这些参考点后的剩余部分（即 X 的余 集 Xc）的骨架（skeleton），即为建立 TIN 的泰森多边形。
定义：连续影像 A 的骨架 SK（A）就是 A 的最大内切圆的圆心集合。 所谓最大内切圆是指那些与 A 的边界至少在两点相切的圆。
利用条件序贯细化形态变换可求得骨架，且能保证 A 中各分量的拓扑 邻接关系。其结果为连续单像元宽度以及各向同性的像元集合。具体算法 如下：
设 Ck 为半径为 k 的栅格圆环， A 为影像的一个子集，令
k
Ak ? ?( A?Ci ) ? Ak?1 ? ( A?Ck ) i ?1
(5.4.1)
A0 ? A
选用结构元 Li （i=1，2，…，8），则
SK ( A) ? A?{LK }；{Ak )
(5.4.2)
即 A 的骨架由 A 的条件序贯细化变换生成。迭代的终止条件为
8
?(SK(A) ? Li ) ?（空集合）
i ?1
(5.4.3)
则以上骨架算法得到 SK ( X c ) ，即所需要的泰森多边形。
12

5.4.3 三角网的形成
若 X 为参考点集， Pi ? X 是 X 的任意一参考点，将与 Pi 所在的泰森
多边形相邻的泰森多边形中的参考点与 Pi 相连接，就构成了以 Pi 为顶点 的所有的三角形的边。其步骤为:
(i) 将 Pi 所在多边形扩张至边界（即 y 的骨架）
Di ? Pi ?{H}；SK ( X c )c
(5.4.4)
?1 1 1? H ? ??1 1 1??
??1 1 1??
则将 Pi 进行条件序贯扩张，直至充满该泰森多边形，同时不越过多边形的
边界。
(ii) 提取与 Pi 所在的泰森多边形 Di 相邻的多边形集合。首先作 H 对
Di 的扩张，跨越边界，然后将 Di 的元素去掉，剩下 Di 的边界与相邻多
边形的元素，再作条件序贯扩张，条件是不超越边界（即 Xc 的骨架）。Di
相邻多边形的集合 Di' ：
Di' ? [( Di ? H ) ? Dic ] ? {H}；(SK (xc )) c
(5.4.5)
（iii）提取 Di' 中属于 X 的点，即提取位于与 Pi 所在泰森多边形相邻
的泰森多边形中的参考点集：
Qi ? Di' ? X
(5.4.6)
依次连接 Pi 与 Qi 中的点，生成 TIN 相应的边。 对 X 中的每一点作相同的处理，记录网点邻接以及有关信息并存贮， 就构建了三角网数字地面模型 TIN。图 5.4.1 所示为根据等高线数据建立的 三角网。
13

图 5.4.1 采用数学形态学方法建立 Delaunay 三角网 应当指出，将形态学的方法用于 DEM 研究还是近十几年来的事，并 且由于它的抽象性和复杂性而不为许多人所知，但使用数学形态学建立 TIN，可简化许多矢量方法所考虑的操作，而且如果进行并行处理，则建 立 TIN 的速度会大大提高（陈晓勇，1991；马飞，1996）。另外，使用形 态变换还可以很容易处理特征点和特征线约束问题，只需要在建立泰森多 边形时加上这些点线即可。
参考文献
陈晓勇，1991，数学形态学与影像分析，测绘出版社，北京，共 154 页。 马飞，1996，数学形态学在遥感和地理信息系统数据分析与处理中的应用
研究，武汉测绘科技大学博士学位论文，共 144 页。 吴华意，1999，拟三角网数据结构及其算法研究，武汉测绘科技大学博士
学位论文，共 142 页。 朱庆，陈楚江，1998，不规则三角网的快速建立及其动态更新，武汉测绘
科技大学学报，23（3）：204-207。 Aumann, G., H. Ebner, and L. Tang, 1991. “Automatic derivation of skeleton
lines from digitized contours”, ISPRS Journal of Photogrammetry and Remote Sensing, Vol. 46:259-268. Brassel, K. and Reif, D., 1979. Procedure to generate Thiesen polygon. Geographical Analysis, 11(3): 289-303. Thibault, D and Gold，C. 1999, Terrain receonstruction from contours by skeleton retraction. Proceedings of the 2nd International Workshop on Dynamic and Multi-dimensional GIS, Oct. 4-6, 1999. Beijing. 23-27. Li Zhilin, 1990, Sampling Strategy and Accuracy Assessment for Digital Terran Modelling, Ph.D. Thesis, The University of Glasgow, 298pp.
14

Mirante A. and Weingarten N., 1982, The Radial Sweep Algorithm for Constructing Triangulated Irregular Networks, IEEE Computer Graphics and Applications, 2(3):11-21。
Petrie, G. and Kennie, T. (eds.), 1990. Terrain Modelling in Surveying and Civil Engineering, Whittles Publishing, Caitness, England. 351pp.
Thibault, D. and Gold, C.M., 1999, Terrain Reconstruction from Contours by Skeleton Retraction. Proceedings of 2nd International Workshop on Dynamic and Multi-dimensional GIS, October 1999, Beijing, pp23-27。
Tsai, Victor J.D., 1993. Delaunay triangulations in TIN creation :an overview and a linear-time algorithm, International Journal of GIS, 7(6): 501-524.
15

不规则三角网的算法设计与实现10页word文档

1 引言 地球表面高低起伏，呈现一种连续变化的曲面，这种曲面无法用平面地图来确切表示。于是我们就利用一种全新的数字地球表面的方法——数字高程模型的方法，这种方法已经被普遍广泛采用。数字高程模型即DEM （Digital Elevation Model），是以数字形式按一定结构组织在一起，表示实际地形特征空间分布的模型，也是地形形状大小和起伏的数字描述。 由于地理信息系统的普及，DEM作为数字地形模拟的重要成果已经成为国家空间数据基础设施（NSDI）的基本内容之一，并被纳入数字化空间框架（DGDF）进行规模化生产，已经成为独立的标准基础产品[5]。DEM有三种主要的表示模型：规则格网模型，等高线模型和不规则三角网。格网（即GRID）DEM在地形平坦的地方，存在大量的数据冗余，在不改变格网大小情况下，难以表达复杂地形的突变现象，在某些计算，如通视问题，过分强调网格的轴方向。不规则三角网（简称TIN，即Triangulated Irregular Network）是另外一种表示数字高程模型的的方法（Peuker等，1978），它既减少了规则格网带来的数据冗余，同时在计算（如坡度）效率方面又优于纯粹基于等高线的方法。不规则三角网能随地形起伏变化的复杂性而改变采样点的密度和决定采样点的位置，因而它能够避免地形起伏平坦时的数据冗余，又能按地形特征点如山脊，山谷线，地形变化线等表示数字高程特征。

基于三角形的表面建模可适合所有的数据结构，且三角形在形状和大小方面有很大灵活性，能很容易地融合断裂线，生成线或其他任何数据，因此基于三角形的方法在地形表面建模中得到了越来越多的注意，已经成为表面建模的主要方法之一。VB语言简洁易学，对于学习GIS的学生来说无疑是接受很容易而且较快的一门计算机编程和开发语言，也是大多数学生最熟悉和了解的语言。正是基于对生成不规则三角网算法的研究和满足学GIS的学生对VB语言的喜爱和熟悉的情况下，本文就主要介绍用三角网生长算法生成不规则三角网及其在VB6.0环境下的实现。 2 TIN的算法种类及各算法特点 在介绍构成TIN各种算法之前我们要来了解认识一下一个重要法则——Delaunay三角网法则。通常构建三角网并不考虑地性线（山脊线，山谷线）的骨架作用，但是，由于用等高线数据构建三角网时，由于地形的复杂多样，有的地区存在因地形突变而形成的断裂线等特殊地貌。另外一些地区存在大面积水域等内部不需要构网的区域，因此，在精度要求较高的TIN中，必须考虑以上问题。因此此时应顾及地性线，断裂线，水域线等特殊情况，也就是应构建约束—Delaunay三角网。约束法是基于约束图计算约束D—三角剖分[1,9]（简称CDT，即Constrained Delaunay Triangulation）构造算法[8]，这种Delaunay三角网满足这样的法则：Delaunay三角网为相互邻接且互不重叠的三角形的集合，每一个三角形的外接圆内不包含其他点。Delaunay三角网由对应Voronoi多边形的点连接而成。Delaunay三角形有三个相邻点连接而成，这三个相邻顶点对应的

一种椭圆曲线快速生成算法

一种椭圆曲线参数生成的快速算法 谷勇浩 刘勇 （北京邮电大学通信网络综合技术研究所） 摘要：椭圆曲线密码体制是公钥密码中的研究热点。该文介绍了椭圆曲线密码体制的基本概念及相关知识，讨论了目前基于离散对数问题的椭圆曲线密码的研究动态。本文的创新点是针对目前椭圆曲线研究重点之一——椭圆曲线参数生成算法，给出了一种生成参数a 、b 的快速算法。这种算法利用了Jacobi 符号和二次剩余的理论，并且用matlab 计算出利用这种算法生成一个椭圆曲线的平均时间，最后我们分析了今后椭圆曲线密码系统的研究方向和重点。 关键词：椭圆曲线；离散对数问题；Jacobi 符号；二次剩余；阶 1976年Diffie 和Hellman 提出公钥密码思想以来，国际上提出了许多种公钥密码体制的实现方案。一些已经被攻破，一些被证明是不可行的。目前，只有3类公钥密码体制被认为是安全有效的，按照其所依据的数学难题划分为：基于大整数分解问题（IFP ），如RSA 体制和Rabin 体制；基于有限域离散对数问题（DLP ），如Diffie-Hellman 体制和ElGamal 体制；基于椭圆曲线离散对数问题（ECDLP ），如椭圆密码体制。椭圆曲线应用到密码学上最早是由Neal Koblitz 和Victor Miller 在1985年分别独立提出的。它是目前已知的公钥体制中，对每一比特所提供加密强度最高的一种体制。它具有安全性高、密钥量小、灵活性好的特点，受到了国际上的广泛关注。而SET(Secure Electronic Transaction)协议的制定者已把它作为下一代SET 协议中缺省的公钥密码算法。深入研究基于椭圆曲线离散对数问题的公钥密码具有很大的现实意义。 1建立椭圆曲线公钥密码体制 1.1椭圆曲线域的参数 在基于椭圆曲线的加解密和数字签名的实现方案中，首先要给出椭圆曲线域的参数来确定一条椭圆曲线。在 IEEE P1363标准中，定义其参数为一个七元组：T=(q,FR,a,b,G,n,h)，其中q 代表有限域GF(q)，q 为素数或 2 m ;FR 为域表示法，如f(x)为 2 m F 域元素的不可约 多项式的表示法；曲线的方程，当q 为素数时，方程为2 3 ax b y x =++，当q 为2m 时， 方程为 2 32 xy a b y x x +=++，a,b 是方程中的系数；G 为基点；n 为大素数并且等于点G 的阶，h 是小整数称为余因子且#()/q h E n F =。主要的安全性参数是n ，因此ECC 密钥 的长度就定义为n 的长度。 1.2椭圆曲线密码的密钥 选取了基域 q F 和椭圆曲线后，得到了在有限域 q F 上的曲线E 确定的具体形式，即 上述的椭圆曲线域参数的一个七元组。每个用户选取一个整数d(1≤d ≤n-1) 作为其私钥，而以点Q=dG(G 为基点)作其公钥，这样形成一个椭圆曲线公钥密码系统。在这个密码体制中，具体的曲线，基域 q F ，基点G 及其阶n ，以及每个用户的公钥都是该系统的公开参

不规则三角网(TIN)

不规则三角网（TIN） Ⅰ 数字高程模型（DEM）地球表面高低起伏，呈现一种连续变化的曲面，这种曲面无法用平面地图来确切表示。于是我们就利用一种全新的数字地球表面的方法——数字高程模型的方法，这种方法已被普遍广泛采用。数字 高程模型即DEM（Digital Elevation Model），是以数字形式按一定结构组织在一起，表示实际地形特征空间分布的模型，也是地形形状大小和起伏的数字描述。DEM有三 种主要的表示模型：规则格网模型，等高线模型和不规则三角网。格网（即GRID）DEM在地形平坦的地方，存在大量的数据冗余，在不改变格网大小情况下，难以表达复杂地形的突变现象，在某些计算，如通视问题，过分强调网格的轴方向。不规则三角网（简称TIN，即Triangulated Irregular Network）是另外一种表示数字高程模型的的方法（Peuker等，1978），它既减少了规则格网带来的数据冗余，同时在计算（如坡度）效率方面又优于纯粹基于等高线的方法。不规则三角网能随地形起伏变化的复杂性而改变采样点的密度和决定采样点的位置，因而它能够避免地形起伏平坦时的数据冗余，又能按地形特征点如山脊，山谷线，地形变化线等表示数字高程特征。Ⅱ TIN的基本知识在TIN中，满足最佳三角形的条件为：尽可能的保证三角形的

三个角都是锐角，三角形的三条边近似相等，最小角最大化。 TIN 是基于矢量的数字地理数据的一种形式，通过将一系列折点（点）组成三角形来构建。形成这些三角形的插值方法有很多种，例如Delaunay 三角测量法或距离排序法。ArcGIS 支持Delaunay 三角测量方法。 TIN 的单位是英尺或米等长度单位，而不是度分秒。当使用地理坐标系的角度坐标进行构建时，Delaunay 三角 测量无效。创建TIN 时，应使用投影坐标系（PCS）。 TIN 模型的适用范围不及栅格表面模型那么广泛，且构建和处理所需的开销更大。获得优良源数据的成本可能会很高，并且，由于数据结构非常复杂，处理TIN 的效率 要比处理栅格数据低。 TIN 通常用于较小区域的高精度建模（如在工程应用中），此时TIN 非常有用，因为它们允许计算平面面积、表面积和体积。Ⅲ TIN在ArcGIS中的存储TIN 表面数据模型由结点（Node）、边（Edge）、三角形（Triangle）、包面（Hull）和拓扑（Topology）组成。 与coverage 类似，TIN 以文件目录形式存储。但TIN没有关联的INFO 文件。TIN 目录由七个包含TIN 表面信息的文件组成。这些文件以二进制格式编码，因此无法通过标准文本显示或编辑程序读取。 TIN 的最大允许大小视连续可用内存资源而定。对

第三章 不规则三角网

第三章不规则三角网 教学目的与要求 通过本章的学习，让大家了解ArcView GIS 3D Analyst扩展模块，熟悉不规则三角网的生成方法，掌握工程填挖方的计算方法，掌握从3D Shapefile生成三维纵剖面和根据线状图形生成纵剖面的方法，能够进行视线与视域分析。 内容提要 5.1地表模型生成、显示 5.2工程中的土方、纵坡 5.3视线与视域分析 教学重点 工程土方量的计算方法 视域与视线分析方法 三维纵剖面图的创建方法 教学难点 不规则三角网的生成方法 5.1 地表模型生成、显示 一、由点状要素产生不规则三角网 所需数据： 点状专题 所用扩展模块： 3D Analyst 所用命令： Surface/Create TIN (Triangulated Irregular Network) from Features... 属性数据表中必须添加高程字段。 详见演示 等高线专题图的生成： 选用菜单命令Surface/Create Contours… 二、不规则三角网和距离倒数权重法插值比较 所需数据： 点状专题 所用扩展模块： Spatial Analyst 所用命令： Surface/Interpolate Grid... 属性数据表中必须添加高程字段，用于高程的计算。

详见演示 等高线专题图的生成： 选用菜单命令Surface/Create Contours… 通过比较，可知不规则三角网比较符合地形特征。 三、建立设计场地的三角网高程模型 所需数据： 设计场地高程控制点专题，并具有各个点的高程属性。 所用扩展模块： 3D Analyst 所用命令： Surface/Create TIN (Triangulated Irregular Network) from Features... 详见演示 四、在场地上添加其他要素 已知数据： 三个AutoCAD的立体图形文件。 Bldg.dwg 选polygon，多边形，建筑物 Road.dwg 选line，线，道路 Water.dwg 选polygon，多边形，水面 所用扩展模块： Cad Reader 所用命令： View/Add Theme 详见演示 五、三维显示 命令：View/3D Scene…，对系统的提示选择Themes，按OK键后系统产生3D Scenes Themes Document，该子系统具有自己的三维视图窗口和图例框，可用鼠标点击按钮Navigate(形状像帆船)，再用鼠标在三维窗口中控制观察地形的三维视角。 在三维场景中，选用菜单命令Theme/3D Properties… 详见演示 小结 不规则三角网络是描述三维表面的常用方法，除了在地形方面，还可以用于其他各种领域。在不规则三角网上还可以叠加其它空间要素，同时以三维方式显示。 5.2 工程中的土方、纵坡 一、由等高线产生不规则三角网 使用数据：设计等高线、现状等高线、场地边界线 扩展模块：3D Analyst 所用命令：Surface/Create TIN from Features 操作步骤：

基于不规则三角网的DTM若干问题的探讨

第23卷 第2期重 庆 交 通 学 院 学 报2004年4月Vo1 23No 2JOURNAL OF C HONGQI NG JIAOTONG UNIVE RSI TY Apr.,2004 基于不规则三角网的DTM若干问题的探讨 赖鸿斌, 李永树 (西南交通大学测量工程系,四川成都610031) 摘要:介绍了用不规则三角网(TIN)建立数字地面模型(DTM)的基本思路,讨论了在建模过程中所遇到问题的解决方法,分析了混合模型的应用问题及TIN数据结构.最后,运用实例说明了由TIN生成的DTM在工程中的应用方法. 关 键 词:不规则三角网;数字地面模型;数据结构 中图分类号:U412 24 文献标识码:A 文章编号:1001 716X(2004)02 0090 04 数字地形模型(Digital Terrain Mode,简称D TM)是表示地形表面的数学(数字)模型.从数学的观点看,地面模型是一个空间连续函数,或是地形模型的离散化表示.对地形表面进行表达的各种处理可称为表面重建或表面建模,重建的表面通常被认为是DTM表面[1]. DTM的核心是地面特征点的三维坐标数据和一套对地表提供连续描述的算法,最基本的DTM至少包含了相关区域内平面坐标(X,Y)与高程Z之间的映射关系,即 Z=F(X,Y) (X,Y) DTM所在区域[2]. 目前,DTM模型的建立和利用已成为地理信息系统的重要组成部分. 1 基于不规则三角网建立DTM 地形表面的建模主要有4种方法:基于点的建模方法、基于不规则三角形的建模方法、基于规则格网的建模方法和混合建模方法[1],其中用得较多的是基于不规则三角形的建模方法和基于规则格网的建模方法. 基于不规则三角形建模是直接利用野外实测的地形特征点(离散点)构造出邻接的三角形,从而组成不规则三角网结构.相对于规则格网,不规则三角网具有以下优点:利用原始资料作为网格结点;不改变原始数据和精度;能够插入地性线以保存原有关键的地形特征,以及能很好地适应复杂、不规则地形等. 不规则三角网(TI N)作为一种主要的DTM表示法,虽然其生成算法比较复杂,但却有许多优点.根据生成三角网算法的不同,可以将生成三角网的算法分为以下三种:分而治之算法、数据点逐次插入算法和三角网生长算法[1].分而治之算法的思想以及生成V 图的分治算法最先是由Shamos和Hoey提出的.Le wis和Robinson将分而治之算法思想应用于生成三角网并给出了一个简化算法:即递归地分割点集,直至子集中只包含三个点而形成三角形,然后自上而下地逐级合并生成最终的三角网;数据点逐次插入算法的思想是由Lawson提出的,以后,Lee和Schachter、Sloan、Watson、Pareschi和Macedonio、Puppo 和Floriani等人先后对这一算法做进一步的改进和完善;三角网生长算法是由Green和Sibson在1978年首先给出的.后来,Reif 、Maus和Brassel等人也发表了类似的算法.下面主要讨论利用三角网生长算法来构建不规则三角网. 如图1所示,在数据点集中任取一点A,查找距 图1 其始三角形的确定 收稿日期:2003 02 21;修订日期:2003 06 19 基金项目:国家自然科学基金项目(40371098)资助 作者简介:赖鸿斌(1978-),男,福建莆田人,硕士生,从事3S的应用研究.

基于不规则三角网构建的网格生长算法

基于基于不规则三角网不规则三角网不规则三角网构建构建构建的的网格生长算法 刘 刚，李永树李永树，，张水舰 (西南交通大学地理信息工程中心，成都 610031) 摘 要：提出一种基于离散点Delaunay 三角网快速构建的网格生长算法，采用分治算法将离散点表达为唯一网格，利用稀疏矩阵完成网格数据的压缩存储，通过标识码实现有值单元格与离散点之间的高效检索，从而提高网格构建的效率。依据有值单元格的密度获取预设正方形搜索空间，并在三角网扩展时根据需要动态建立正方形搜索空间，从而保证网格生长的准确性。实验结果表明，该算法的时间复杂度为O (n log n )，对于少量或海量离散点均具有较好的适应性。 关键词关键词：：Delaunay 三角网；不规则三角网；离散点；正方形搜素空间；网格生长算法 Grid Growing Algorithm Based on Triangular Irregular Network Construction LIU Gang, LI Yong-shu, ZHANG Shui-jian (Geography Information Engineering Center, Southwest Jiaotong University, Chengdu 610031, China) 【Abstract 】This paper presents a grid growing algorithm for fast construction of Delaunay irregular network based on discrete point. In this algorithm, a grid is achieved to express discrete point uniquely based on the divide-and-conquer method, which is compressed storage in a sparse matrix, and an efficient retrieval method is established between value cell and discrete point by identification code, which is effectively to improve the efficiency of the construction of Triangular Irregular Network(TIN). According to the density of value cells, a default square search space is acquired, and it is allowed to create the square search space dynamically in the expansion process of TIN, which ensures the accuracy of the grid growing. Experimental results show that the time complexity of the proposed algorithm is O (n log n ), and the algorithm is available to both small and massive amount of discrete points. 【Key words 】Delaunay triangular network; Triangular Irregular Network(TIN); discrete point; square search space; grid growing algorithm DOI: 10.3969/j.issn.1000-3428.2011.12.019 计 算 机 工 程 Computer Engineering 第37卷 第12期 V ol.37 No.12 2011年6月 June 2011 ·软件技术与数据库软件技术与数据库·· 文章编号文章编号：：1000—3428(2011)12—0056—03 文献标识码文献标识码：：A 中图分类号中图分类号：：P209 1 概述 不规则三角网(Triangular Irregular Network, TIN)表面建模是一种很重要的表面建模方法[1-2]。在所有生成TIN 的方法中，Delaunay 三角网最优，它尽可能避免了病态三角形的出现，常被用来生成TIN 。 目前，利用离散点构建Delaunay 三角网的方法有很多，主要有逐点插入法、三角网生长法、分治算法等[1]。逐点插入算法是Lawson C L [3]提出的，之后Bowyer A [4]、Watson D F [5]等人对其进行发展。该算法的时间复杂度一般在3/2()O n ~ (log ) O n n [6-7] ，在处理过程中每插入一个点都要判断插入点 所在的三角形，随着数据点的不断插入，三角形的个数成倍增加，将花费大量的时间在三角形的定位上，从而直接影响算法效率。三角网生长法、分治法等算法的时间复杂度的下界为(log )O n n 。三角网生长法将大部分时间花费在搜索符合 要求的给定基线的邻域点过程中，分治算法由于递归执行，算法需要较大内存空间[8]，对海量数据而言，两者的效率都 较低。 为提高不规则三角网的构建效率，本文提出一种基于离 散点构建不规则三角网的网格生长算法，重点研究如何由离 散点生成规则网格，并在此基础上建立TIN 模型。 2 一种一种构建构建构建不规则三角网的不规则三角网的不规则三角网的网格网格网格生长算法生长算法 2.1 离散点离散点网格网格网格化化 网格由许多单元格组成，通常将单元格看成一个对象。从处理效率上看，单元格值的情况越少，单元格之间的计算 速度越快。所以，从计算效率出发，针对离散数据确定如下 规则网格构建准则：规则网格包含所有离散点，每个离散点对应一个单元格，且一个单元格内的离散点数量小于2。当单元格内存在一个离散点时表示该单元格有值(用1表示)，称为有值单元格，当不存在离散点时表示该单元格无值(即为Null)，称为空值单元格，并将按照该准则建立的规则网格称为唯一网格，其唯一性体现在离散点与有值单元格的一一对应关系。原理如图1所示，图1(a)表示一个单元格只包含 1个或0个离散点，图1(b)是对有值单元格进行赋值的结果(其中，黑色表示有值单元格即为1；其余无值即为Null)。 (a)离散点与网格关系 (b)网格化结果 图1 离散点离散点网格网格网格化化 基金项目 基金项目：：“十一五”国家科技支撑计划基金资助项目(2006BAJ05 A13) 作者简介作者简介：：刘 刚(1986－)，男，硕士，主研方向：复杂网络，GIS 原理及其应用；李永树，教授、博士生导师；张水舰，博士 收稿日期收稿日期：：2011-01-08 E-mail ：liugang233666@https://www.sodocs.net/doc/624090817.html,

不规则三角网(TIN)生成的算法

第五章 不规则三角网（TIN）生成的算法
5.1.1 递归生长法
递归生长算法的基本过程为如图 5.1.1 所示：
3 2
1
3 2
1
（a）形成第一个三角形 (b) 扩展生成第二个和第三个三角形 图 5.1.1 递归生长法构建 Delaunay 三角网
（1）在所有数据中取任意一点 1（一般从几何中心附近开始），查找 距离此点最近的点 2，相连后作为初始基线 1-2；
（2）在初始基线右边应用 Delaunay 法则搜寻第三点 3，形成第一个 Delaunay 三角形；
（3）并以此三角形的两条新边（2-3，3-1）作为新的初始基线； （4）重复步骤（2）和（3）直至所有数据点处理完毕。 该算法主要的工作是在大量数据点中搜寻给定基线符合要求的邻域 点。一种比较简单的搜索方法是通过计算三角形外接圆的圆心和半径来完 成对邻域点的搜索。为减少搜索时间，还可以预先将数据按 X 或 Y 坐标分 块并进行排序。使用外接圆的搜索方法限定了基线的待选邻域点，因而降 低了用于搜寻 Delaunay 三角网的计算时间。如果引入约束线段，则在确定 第三点时还要判断形成的三角形边是否与约束线段交叉。
1

5.1.2 凸闭包收缩法
与递归生长法相反，凸闭包搜索法的基本思想是首先找到包含数据区 域的最小凸多边形，并从该多边形开始从外向里逐层形成三角形网络。平 面点凸闭包的定义是包含这些平面点的最小凸多边形。在凸闭包中，连接 任意两点的线段必须完全位于多边形内。凸闭包是数据点的自然极限边界， 相当于包围数据点的最短路径。显然，凸闭包是数据集标准 Delaunay 三角 网的一部分。计算凸闭包算法步骤包括：
（1）搜寻分别对应 x-y，x+y 最大值及 x-y，x+y 最小值的各二个点。 这些点为凸闭包的顶点，且总是位于数据集的四个角上，如图 5.1.2（a）中的点 7，9，12，6 所示；
（2）将这些点以逆时针方向存储于循环链表中； （3）对链表中的点 I 及其后续点 J 搜索线段 IJ 及其右边的所有点，计
算对 IJ 有最大偏移量的点 K 作为 IJ 之间新的凸闭包顶点，如点 11 对边 7-9。 （4）重复（2）-（3）直至找不到新的顶点为止。
（a）初始边界 7，9，12，6；（b）搜索凸闭包顶点 11，5，4；（c）凸闭包 图 5.1.2 凸闭包的计算(引自 Tsai，1993)
一旦提取出数据区域的凸闭包，就可以从其中的一条边开始逐层构建 三角网，具体算法如下：
2

实验四：不规则三角网

本科学生野外实验报告 学号姓名 学院旅游与地理科学学院专业、班级 实验课程名称地理信息系统实习教程 教师及职称 开课学期2012 至2013 学年下学期填报时间2013 年 5 月29 日 云南师范大学教务处编印

1、实验现象与结果 （1）视线分析，打开ex15.mxd,激活Data frame1，在General标签栏中，在Units框内，用下拉式菜单将Map和Display从Unknow Units改为Meters，完成后按“确定”关闭，选用菜单Tool/Extension，加载3D Analyst扩展模块，选用菜单View/Toolbars/3D Analyst，加载 3D Analyst工具条，点击产生视线按钮，出现Line of Sight对话框：

（2）基于视点的视域分析 ①产生单个观察点的视域栅格，选用3D/Options，作初始设置，初始设置完成后，选用菜单3D Analyst/Sueface Analysis/Viewshed…，出现Viewshed参数设置对话框，按ok键确定后，软件产生栅格状视域分析结果图层Visibilel。

②改变观察点的高程，视域分析中，需预先设定部分参数，其中有观察点的高度。在前面分析的视域分析中，没有作任何特别的设置，软件默认为观察点的高度比所在位置的三维面高一个地图单位，其观察点绝对高程为90m的视域： ③两次视域分析结果的比较，前一次不作任何设置，观察点高程仅仅是比对应的三维表面层

Analyst/Convert/Features to 3D，出现“Convert features to 3D”参数设置对话框进行设置，再Viewshed参数设置对话框进行设置，最后就能得到基于路径的视域分析结果图;

CASS软件三角网法计算土方量

CASS软件三角网法计算土方量 数字地面模型（DTM）可以解决一些工程实际的问题，该模型能用三维场景表示出地貌的起伏状态，可以按用户要求进一步生成坡度图、等高线图、断面图等；三角网是DTM模型中的一种，利用该模型可以较方便的计算出土方量，在工程上得到了广泛的应用。 标签：CASS软件；DTM；土方量计算 1 土方量计算概述 土方量的计算是工程费用概算及施工方案选取的重要依据，所以工程施工前的设计阶段必须对施工区域的土石方量进行计算。土石方量计算是以设计高程作为底面高程，以施工前该区域的实际地形高程作为顶面高程。土石方量的计算方法有等高线法，方格网法，断面法和三角网法等。在实际工作时，无论采用哪一种方法，都需要利用测量仪器获得大量的地形数据，其采样的间隔越小，其计算出的土方量越准确。在这几种土方量计算方法中，三角网法由于很好的拟合实际地貌的几何特征，并且能克服地形起伏不大的地区产生冗余数据的问题，其计算精度高于等高线法，方格网法，断面法精度。 2 三角网法土方量计算 2.1 建立三角网 数字高程模型（DEM）的格网间隔（数据点密度）与其同比例尺地形图高程精度相适配，并形成有规则的格网系统，根据不同的高程精度，可分为不同类型产品。为完整反映地表形态，可配套提供离散高程点数据。三角网是数字高程模型中的一种，是在一定区域内规则三角网点的三维坐标数据的集合，这个数据集合可以代表该区域地形地貌的起伏状态。利用CASS（数字地形地籍绘图软件）可以较为容易的生成三角网，其建立方法分为两种：一种是根据“坐标数据文件”生成，另一种是根据“图面高程点”生成。无论采用哪一种方法，都必须是依据坐标数据文件，必须采用如下格式：“点号，编码，Y坐标，X坐标，高程”才能在CASS软中将高程点展绘出来。需要注意的是编码一位可以是空缺的，但是“逗号”不能省略，此文件格式必须是五个“逗号”，并其需要注意横坐标在前，纵坐标在后。 因实际地貌的多样性和复杂性，自动构成的三角网模型与实际地貌会有一定偏差，如果出现了三角网与实际地形不符合的情况，可以采用如下方法进行局部的修改：（1）删除三角形：如果区域边界生成了多余的三角形，应把其删除；（2）增加三角形：如果边界区域某范围没有生产三角网，则应通过内插点生产三角形，否则没有三角形的范围不参与土方量的计算；（3）过滤三角形：如果某些三角行的某个角度过小，可以采用该方法，将这些三角行重新组合成三角形；（4）删三角形顶点：采用该方法可以将有公共点的三角形统一删除，这样该区域范围不参

不规则三角网的建立与应用

作为空间数据基础设施中的“4D”产品之一和地理信息系统的核心数据库，数字高程模型（DEM）已在测绘、遥感、农林规划、城市规划、土木水利工程、地学分析等各个领域都有了广泛的应用。数字高程模型的表示方法主要有规则格网模型、不规则三角网模型和等高线模型三种，而不规则三角网(TIN)是数字高程模型中最基本和最重要的一种模型，它能以不同层次的分辨率来描述地形表面，并可以灵活的处理特殊地形。因此，围绕基于TIN 的DEM 的构建，本文主要论述了基于TIN 结构的数字高程模型建模原理和方法，离散点的Delaunay 三角网生成算法，建立有约束条件的约束三角网，最后分析了建立的TIN模型在土方计算方面的应用。 在本论文论述的过程中，针对传统算法进行了对比和分析后，在逐点插入法的基础之上，提出了一些新的细部改进的实现方法。局部优化操作和改进的算法实现使得对大容量离散点的三角网构建速度更快，效率更高；对限制条件的嵌入满足由此计算出来的土方量更接近实际期望值。本论文中主要的研究成果和内容如下：1）在离散点的Delaunay 三角网生成方面，本文中在插入点算法的基础上，建立凸包和矩形包容盒，建立虚拟网格，对原始离散点进行一级格网自适应分块，并建立索引关系。在定位点所在三角形时引入快速点定位算法，简易的空外接圆及圆内测试公式，通过这些改进使得Delaunay 三角网的剖分更加高效。 2）在约束Delaunay 三角网理论基础之上，结合上面散点域的剖分方法，对已有的两步算法基础上改进，完成约束Delaunay 三角网的构建。在其过程中应用矢量点积等数学工具改善了计算中的凹凸点判断，继续采用上章的快速索引和最速定位方法，并且对约束线相切等特殊情形进行了处理，进一步完善了算法的稳健性。 3）对于在约束三角网构造基础上的TIN 模型的应用，文中对其在土方量计算方面精度的优越性进行了分析，在可视化表达方面最后结合广东省东莞市某高尔夫球场工程给出了例证。 关键词：不规则三角网（TIN）;逐点插入法;土方计算

不规则三角网(TIN)生成的算法

第五章 不规则三角网（TIN）生成的算法
在第四章，基于三角网和格网的建模方法使用较多，被认为是两种基 本的建模方法。三角网被视为最基本的一种网络，它既可适应规则分布数 据，也可适应不规则分布数据，即可通过对三角网的内插生成规则格网网 络，也可根据三角网直接建立连续或光滑表面模型。在第四章中同时也介 绍了 Delaunay 三角网的基本概念及其产生原理，并将三角网构网算法归纳 为两大类：即静态三角网和动态三角网。由于增量式动态构网方法在形成 Delaunay 三角网的同时具有很高的计算效率而被普遍采用。本章主要介绍 静态方法中典型的三角网生长算法和动态方法中的数据点逐点插入算法； 同时，还将给出考虑地形特征线和其他约束线段的插入算法。而其他非 Delaunay 三角网算法如辐射扫描法 Radial Sweep Algorigthm（Mirante & Weingarten, 1982）等本文将不再介绍。
5.1 三角网生长法
5.1.1 递归生长法
递归生长算法的基本过程为如图 5.1.1 所示：
3 2
1
3 2
1
（a）形成第一个三角形 (b) 扩展生成第二个和第三个三角形 图 5.1.1 递归生长法构建 Delaunay 三角网
（1）在所有数据中取任意一点 1（一般从几何中心附近开始），查找
1

距离此点最近的点 2，相连后作为初始基线 1-2； （2）在初始基线右边应用 Delaunay 法则搜寻第三点 3，形成第一个
Delaunay 三角形； （3）并以此三角形的两条新边（2-3，3-1）作为新的初始基线； （4）重复步骤（2）和（3）直至所有数据点处理完毕。 该算法主要的工作是在大量数据点中搜寻给定基线符合要求的邻域 点。一种比较简单的搜索方法是通过计算三角形外接圆的圆心和半径来完 成对邻域点的搜索。为减少搜索时间，还可以预先将数据按 X 或 Y 坐标分 块并进行排序。使用外接圆的搜索方法限定了基线的待选邻域点，因而降 低了用于搜寻 Delaunay 三角网的计算时间。如果引入约束线段，则在确定 第三点时还要判断形成的三角形边是否与约束线段交叉。
5.1.2 凸闭包收缩法
与递归生长法相反，凸闭包搜索法的基本思想是首先找到包含数据区 域的最小凸多边形，并从该多边形开始从外向里逐层形成三角形网络。平 面点凸闭包的定义是包含这些平面点的最小凸多边形。在凸闭包中，连接 任意两点的线段必须完全位于多边形内。凸闭包是数据点的自然极限边界， 相当于包围数据点的最短路径。显然，凸闭包是数据集标准 Delaunay 三角 网的一部分。计算凸闭包算法步骤包括：
（1）搜寻分别对应 x-y，x+y 最大值及 x-y，x+y 最小值的各二个点。 这些点为凸闭包的顶点，且总是位于数据集的四个角上，如图 5.1.2（a）中的点 7，9，12，6 所示；
（2）将这些点以逆时针方向存储于循环链表中； （3）对链表中的点 I 及其后续点 J 搜索线段 IJ 及其右边的所有点，计
算对 IJ 有最大偏移量的点 K 作为 IJ 之间新的凸闭包顶点，如点 11 对边 7-9。 （4）重复（2）-（3）直至找不到新的顶点为止。
（a）初始边界 7，9，12，6；（b）搜索凸闭包顶点 11，5，4；（c）凸闭包
2

三角网构造原理

VB环境下不规则三角网的算法设计与实现 江剑霞1，刘少华1,2， （1北京建筑工程学院，北京100044；2江西省数字国土重点实验室江西抚州344000；）摘要：本文对不规则三角网生长算法实现的研究，利用了VB强大的可视化用户界面及其编程语言的灵活性及简单易懂特点，基于各行业对于DEM的需要，从而开发出一种利用VB6.0语言生成基于生长算法的不规则三角网，结合数据库强大的数据库存取，编辑，查询功能，共同实现离散点的管理和三角网的构成。 关键词：不规则三角网；Delaunay三角网；VB环境；算法 Algorithm designing and realizing of TIN In VB JIANG Jian-xia1,LIU Shao-hua1,2 (1BeiJing Institute of Civil Engineering And Architecture,BeiJing,100044;2Digital Land Key Lab of JiangXi Province,Fuzhou344000) Abstract:the paper discuss the algorithm of the TIN which takes advantage of VB’s powerfully visible interface of user and flexibility and knowing easily of compiling procedure.On the basis of demanding for DEM for all professions,the author uses the VB language to develop a kind of TIN based on the growth-algorithm,in combination with the powerful function of the data base’s data accessed,edited and inquired about,achieving the management of the dispersed points and the construction of TIN Key words:TIN,Delaunay,VB,algorithm 1引言 地球表面高低起伏，呈现一种连续变化的曲面，这种曲面无法用平面地图来确切表示。于是我们就利用一种全新的数字地球表面的方法——数字高程模型的方法，这种方法已经被普遍广泛采用。数字高程模型即DEM（Digital Elevation Model），是以数字形式按一定结构组织在一起，表示实际地形特征空间分布的模型，也是地形形状大小和起伏的数字描述。 由于地理信息系统的普及，DEM作为数字地形模拟的重要成果已经成为国家空间数据基础设施（NSDI）的基本内容之一，并被纳入数字化空间框架（DGDF）进行规模化生产，已经成为独立的标准基础产品[5]。DEM有三种主要的表示模型：规则格网模型，等高线模型和不规则三角网。格网（即GRID）DEM在地形平坦的地方，存在大量的数据冗余，在不改变格网大小情况下，难以表达复杂地形的突变现象，在某些计算，如通视问题，过分强调网格的轴方向。不规则三角网（简称TIN，即Triangulated Irregular Network）是另外一种表示数字高程模型的的方法（Peuker等，1978），它既减少了规则格网带来的数据冗余，同时在计算（如坡度）效率方面又优于纯粹基于等高线的方法。不规则三角网能随地形起伏变化的复杂性而改变采样点的密度和决定采样点的位置，因而它能够避免地形起伏平坦时的数据冗余，又能按地形特征点如山脊，山谷线，地形变化线等表示数字高程特征。 基于三角形的表面建模可适合所有的数据结构，且三角形在形状和大小方面有很大灵活性，能很容易地融合断裂线，生成线或其他任何数据，因此基于三角形的方法在地形表面建模中得到了越来越多的注意，已经成为表面建模的主要方法之一。VB语言简洁易学，对于学习GIS的学生来说无疑是接受很容易而且较快的一门计算机编程和开发语言，也是大多数学生最熟悉和了解的语言。正是基于对生成不规则三角网算法的研究和满足学GIS的学 基金项目:湖北省高等学校优秀中青年团队计划项目资助(T200602);;江西省数字国土重点实验室开发研究基金资助 (DLLJ200501);;长江大学发展基金资助(2004Z0115)

CASS软件三角网法计算土方量

CASS软件三角网法计算土方量 摘要：数字地面模型（DTM）可以解决一些工程实际的问题，该模型能用三维场景表示出地貌的起伏状态，可以按用户要求进一步生成坡度图、等高线图、断面图等；三角网是DTM模型中的一种，利用该模型可以较方便的计算出土方量，在工程上得到了广泛的应用。 关键词：CASS软件；DTM；土方量计算 1 土方量计算概述 土方量的计算是工程费用概算及施工方案选取的重要 依据，所以工程施工前的设计阶段必须对施工区域的土石方量进行计算。土石方量计算是以设计高程作为底面高程，以施工前该区域的实际地形高程作为顶面高程。土石方量的计算方法有等高线法，方格网法，断面法和三角网法等。在实际工作时，无论采用哪一种方法，都需要利用测量仪器获得大量的地形数据，其采样的间隔越小，其计算出的土方量越准确。在这几种土方量计算方法中，三角网法由于很好的拟合实际地貌的几何特征，并且能克服地形起伏不大的地区产生冗余数据的问题，其计算精度高于等高线法，方格网法，断面法精度。 2 三角网法土方量计算

2.1 建立三角网 数字高程模型（DEM）的格网间隔（数据点密度）与其同比例尺地形图高程精度相适配，并形成有规则的格网系统，根据不同的高程精度，可分为不同类型产品。为完整反映地表形态，可配套提供离散高程点数据。三角网是数字高程模型中的一种，是在一定区域内规则三角网点的三维坐标数据的集合，这个数据集合可以代表该区域地形地貌的起伏状态。利用CASS（数字地形地籍绘图软件）可以较为容易的生成三角网，其建立方法分为两种：一种是根据“坐标数据文件”生成，另一种是根据“图面高程点”生成。无论采用哪一种方法，都必须是依据坐标数据文件，必须采用如下格式：“点号，编码，Y坐标，X坐标，高程”才能在CASS软中将高程点展绘出来。需要注意的是编码一位可以是空缺的，但是“逗号”不能省略，此文件格式必须是五个“逗号”，并其需要 注意横坐标在前，纵坐标在后。 因实际地貌的多样性和复杂性，自动构成的三角网模型与实际地貌会有一定偏差，如果出现了三角网与实际地形不符合的情况，可以采用如下方法进行局部的修改：（1）删除三角形：如果区域边界生成了多余的三角形，应把其删除；（2）增加三角形：如果边界区域某范围没有生产三角网， 则应通过内插点生产三角形，否则没有三角形的范围不参与土方量的计算；（3）过滤三角形：如果某些三角行的某个角

不规则三角网

不规则三角网的构建 曹宁0211555 摘要：在GIS应用领域中，Delaunay三角网通常被应用在生成不规则三角网（TIN）模型，并用于描述地表形态。本篇文章就目前较为成熟的算法做简要介绍，并对用于构建Delaunay三角网的渐次插入算法（闫浩文，2002）在VC++环境下实现的过程做较为详细的介绍。 关键词：不规则三角网；VC++；渐次插入算法 Abstract:In GIS applications, the Delaunay triangulation Netcom often used to generate atriangulated irregular network (TIN) model, and is used to describe the surface morphology. This article is a brief introduction to the more sophisticated algorithms,and detailed introduce the implementation process of gradually insert of the Delaunay triangulation algorithm (Yan Hao, 2002) in VC + + environment. Keywords：TIN；VC++; gradually insert algorithm 一、引言 TIN（Triangulated Irregular Network）即不规则三角网，Delaunay三角网是其中的一种表现形式，也是一种主要的DTM的表示法。 Delaunay三角网：它是一系列相连的但不重叠的三角形的集合，而且这些三角形的外接圆不包含这个面域的其他任何点，它具有两个特有的性质：每个Delaunay三角形的外接圆不包含面内的其他任何点，称之为Delaunay三角网的空外接圆性质，这个特性已经作为创建Delaunay三角网的一项判别标准。 它的另一个性质是最大最小角性质：在由点集V中所能形成的三角网中，Delaunay三角网中的三角形的最小角度是最大的。 Delaunay三角网的优点是结构良好，数据结构简单，数据冗余度小，存储效率高，与不规则的地面特征和谐一致，可以表示线性特征和迭加任意形状的区域边界，易于更新，可适应各种分布密度的数据等；局限性是。算法实现比较复杂和困难。 Delaunay三角网是V oronoi图的对偶图，他们两个是被普遍接受和采用的分析研究区域离散数据的有力工具。它是通过连接具有公共顶点的三个V多边形的生长中心而生成的。如图1.1。 图1.1 Delaunay三角网与V oronoi图 二、几种常见的算法 2.1 凸包插值算法 （1）凸包生成。①求出点集中满足min（x-y）、min（x+y）、max（x-y）、max （x+y）的四个点，并按照逆时针方向组成一个链表。这四个点是离散点中与包含离散点的外接矩形的四个角点最接近的点，这四个点构成的多边形作为初始凸包。 ②对于每个凸包上的点I，设它的后续点为J，计算矢量线段IJ右侧的所有点到IJ的距离，求出距离最大的点K。 ③将K插入I、J之间，并将K赋给J。