当前位置：文档之家 › DELAUNAY三角网的算法

DELAUNAY三角网的算法

  • 格式：ppt
  • 大小：1.46 MB
  • 文档页数：10

下载文档原格式

  / 10

合集下载

Delaunay三角网建立的改进算法

Delaunay三角网建立的改进算法
的时间复杂度差， 但 运行速度
０ 引 言
２维 任 意域 内点 集 的 Ｄ ｌ ｎｙｉ角 剖 分 具 有 最 小 ｅ ｕａ ａ 角最 大 的 良好性 质 ， 被公 认 为最 优 的 三角 剖 分 ， 科 学 在
比较慢 。本文深入研究了算法的实现步骤， 对其 中的关 键环节加 以优化和改进 ， 高了算法 的执行 效率 ， 提 使算
中图分类号 ：２ ｌ Ｐ ２
文献标识码 ： Ｂ
文章编号 ：６２— ８７ ２０ ） ｌ ０ ３ — ４ １７ ５ ６ （０７ ０ 一 ０ ８ ０
Ａｎ Ｉ ｐｒ ｖ ｄ Ａｌ ｏ ｉｈ ｏ ｅ ｔｏ ｆＤｅ ａ ｎ ｙ Ｔｒａ ｇ ｌ ｔｏ ｍ ｏ ｅ ｇ ｒｔ ｍ ｆ ｒ Ｃｒ ａ ｉ ｎ ｏ ｌ ｕ ａ ｉ ｎ ｕ ａ ｉ ｎ
维普资讯
第３ ０卷 第 １ 期
２ ０ 年 ２ 月 ０７
测 绘 与 空 间地 理 信 息
ＧＥＯＭ ＡＴ ＣＳ ＆ ＳＰＡＴ ＡＬ ｌ ｏＲＭ Ａ ｏＮ ＥＣＨＮＯＬ ＧＹ Ｉ Ｉ ＮＦ Ｔｌ Ｔ Ｏ
Ｖｏ ． ０， ．１ １ ３ Ｎｏ
Ｆ ｂ ，２ ０ ｅ． ０７
响算法效率的关键环节 ， 并采用数据点 集分块 管理 、 三角形快速 定位 、 变点插入 顺序等 方法进行 了算 法优 化 ， 改
对三角形快速定位方法进行 了改进 。测试 实验的结果说 明 ， 法改进后 Ｄ ｌ ｎｙ 算 ｅ ｕａ 三角 网建立的效率提 高了 ４～ ａ ６
倍。
关 键 词 ： ｅ ｕａ 三 角 网： 点 插 入 法 ： 角 形快 速 定 位 Ｄ ｌ ｎｙ ａ 逐 三
１ 求 出点集 中 ） Ｙ和 — Ｙ的最大值 和最小值 ， 并
将 对 应 的 ４ 点 按逆 时 针方 向组 成 一 个链 表 ， 成 初 始 个 构

delaunay三角网生长准则及算法

delaunay三角网生长准则及算法

Delaunay 三角网是Voronoi(或称thiessen多边形,V 图)图的伴生图形◆Delaunay 三角网的定义:由一系列相连的但不重叠的三角形的集合, 而且这些三角形的外接圆不包含这个面域的其他任何点。

◆Voronoi图的定义：Voronoi图把平面分成N 个区，每一个区包括一个点，该点所在的区域是距离该点最近的点的集合。

◆Delaunay三角网的特性：◆不存在四点共圆；◆每个三角形对应于一个Voronoi图顶点；◆每个三角形边对应于一个Voronoi图边；◆每个结点对应于一个Voronoi图区域；◆Delaunay图的边界是一个凸壳；◆三角网中三角形的最小角最大。

空外接圆准则最大最小角准则最短距离和准则在TIN中，过每个三角形的外接圆均不包含点集的其余任何点在TIN中的两相邻三角形形成的凸四边形中，这两三角形中的最小内角一定大于交换凸四边形对角线后所形成的两三角形的最小内角一点到基边的两端的距离和为最小Delaunay三角剖分的重要的准则张角最大准则面积比准则对角线准则一点到基边的张角为最大三角形内切圆面积与三角形面积或三角形面积与周长平方之比最小两三角形组成的凸四边形的两条对角线之比。

这一准则的比值限定值，须给定，即当计算值超过限定值才进行优化Delaunay三角剖分的重要的准则不规则三角网(TIN)的建立●三角网生长算法就是从一个“源”开始，逐步形成覆盖整个数据区域的三角网。

●从生长过程角度，三角网生长算法分为收缩生长算法和扩张生长算法两类。

方法说明方法实例收缩生长算法先形成整个数据域的数据边界（凸壳），并以此作为源头，逐步缩小以形成整个三角网分割合并算法逐点插入算法扩张生长算法从一个三角形开始向外层层扩展，形成覆盖整个区域的三角网递归生长算法逐点插入算法分割合并算法12121212递归生长算法333TIN 建立过程中的几个问题:◆邵春丽.DELAUNAY 三角网的算法详述及其应用发展前景◆鲍蕊娜，等:基于凸壳技术的Delaunay 三角网生成算法研究◆于杰等：Delaunay 三角网构建方法比较研究周围点的提取 点在三角形中的查找 空外接圆判断准则 线段求交问题。

DELAUNAY三角网的算法

DELAUNAY三角网的算法

二、Delaunay（德洛内）三角网 1、定义：一系列相连但不重叠的三角形的集合，而且 这些三角形的外接圆不包含这个面域的其他人任何点。 2、性质：（1）、每个Delaunay三角形的外接圆不包 含面内其他任何点，即Delaunay三角网的空外接圆 性质。这是创建Delaunay三角网的一项判别标准。 （2）、在由点集V中所能形成的三角网中， Delaunay三角网中三角形的最小角度是最大的。
DELAUNAY三角网的算法
一、引言 TIN（Triangulated Irregular Network,不规则三角网）
是由Peuker和他的同事于1978年设计的一个系 统，它是根据区域的有限个点集将区域划分为相等的 三角面网络，数字高程由连续的三角面组成，三角面 的形状和大小取决于不规则分布的测点的密度和位置， 能够避免地形平坦时的数据冗余，又能按地形特征点 表示数字高程特征。TIN常用来拟合连续分布现象的 覆盖表面。
3、优点：结构良好，数据 结构简单，数据冗余度 小，存储效率高，可适 应各种分布密度的数据。
p1
p4
p2 p3
p6
p5
三、Voronoi图 （泰森多边形或Dirichlet图）
由一组由连接两邻点直线的垂直平分线组成的连续多 边形组成。 N个在平面上有区别的点，按照最邻近原则划分平面； 每个点与它的最近邻区域相关联。 Delaunay三角形是由与相邻Voronoi多边形共享一条 边的相关点连接而成的三角形。 Delaunay三角形的外接圆圆心是与三角形相关的 Voronoi多边形的一个顶点。 Voronoi三角形是Delaunay图的偶图 。



3、根据优化准则对局部新形成的三角形进行优化（如互 换对角线等）。将形成的三角形放入Delaunay三角形链 表。 4、循环执行上述第2步，直到所有散点插入完毕。 上述基于散点的构网算法理论严密、唯一性好，网格满足 空圆特性，较为理想。由其逐点插入的构网过程可知，在 完成构网后，增加新点时，无需对所有的点进行重新构网， 只需对新点的影响三角形范围进行局部联网，且局部联网 的方法简单易行。同样，点的删除、移动也可快速动态地 进行。 但在实际应用当中，这种构网算法不易引入地面的地性线 和特征线，当点集较大时构网速度也较慢，如果点集范围 是非凸区域或者存在内环，则会产生非法三角形。

Delaunay三角网内插多边形算法研究

Delaunay三角网内插多边形算法研究

求 首先建 立 城 市 Ｄ Ｍ， Ｅ 而城 市 的变 化 日新 月 异 ， 特别 是 旧城 区的改造 ， 求 Ｄ Ｍ模 型 能及 时更 新 １ 数据 结构 要 Ｅ 以反 映城 市 的新 面 貌 ； 如铁 路 的选 线 也需 要 在 再 更新 的方 法 有 两 种 ： 是 重 建 整 个 区域 的 Ｄ Ｍ； 一 Ｅ 算 法在设 计 数据结 构时 ， 点设计 比较 简单 ， 只 原 Ｄ Ｍ 模型 上 内插设 计 好 的 线路 多边 形 。Ｄ Ｍ Ｅ Ｅ 有点号及 ３ 维坐标信息 ， 不专门为边设计数据结
构， 将边的信息隐含在三角形数据结构 中， 以节约
二是在原 有 的 Ｄ Ｍ 基础上 ， Ｅ 局部 修改需 要 更新 的 存储空间。这里在 Ｄ三角网生成时 ， ． 三角形要求 三 数据。显然第 ２种方法即经济又省时。这种情境 顶 点按 逆 时针存 储 ， 角形 的数 据结 构 设 计 如 下 下 Ｄ Ｍ 局部 更新过程 就是在 表达 Ｄ Ｍ 的三角 网 所 述 。 Ｅ Ｅ 中 内插一个 多边 形 ， 删除原 来 的数据 。 目前 ， 并 国
Ｒｅ ｅ ｒ ｈ ｏ ｇ ｒｔ ｓ ａ ｃ ｎ Ａｌ ｏ ｉｈｍ ｆＤｅａ ａ ｉ ｎｇ ｌ ｔｏ Ｎｅ ｎｔ ｒ ｏ ａ ｉ ｌ ｇ ｎ ｏ ｌ ｕｎ ｙ Ｔｒ ａ ｕ ａ ｉ ｎ ｔＩ ｅ ｐ ｌ ｔｎｇ Ｐｏ ｙ ｏ
ＬＩ Ｓ ａ ・ ａ Ｗ Ｕ ｎ ・ ｈ ｎ Ｌ Ｕ ｈ ｏｈｕ ， Ｄｏ ｇ ｓ ｅ ｇ， ＵＯ ａ ・ｏ ｇ ＨＥ Ｚｈ ｎ ｍｉ ｇ Ｌ Ｕ ｅ ｆ ｎ Ｘｉ ｏ ｌｎ ， ｅ ・ ｎ ， Ｉ Ｘｕ ・ｅ ｇ
先将 多边形 的边作为约束数据入 网， 然后对多边形 内部 三角形进行清 空处理。在影响 区域及 多边形 内部三角
形确定上 ， 出了一种快速解决方法， 提 大大提高 了算法的执行 效率。 关 键 词 ： ｅ ｕａ ； Ｄ ｌ ｎｙ 三角 网； ａ 多边形 ； 内插 ； 算法

机载LiDAR点云的Delaunay三角网快速生成算法

机载LiDAR点云的Delaunay三角网快速生成算法
率 与稳 定性 ห้องสมุดไป่ตู้
２ ． １ 点 云 数 据 分 块
式 在特 定应 用 中具 有 各 自的优 势 … 。其 中 ， Ｔ Ｉ Ｎ具 有存 储 高效 、 数 据结 构简 单 、 适 合表 现不规 则地 面特 征、 能够 表示 线性 特 征 和迭 加 任 意形 状 的 区域边 界 等优点 ， 能更 好地 表达 目标 的几何 空 间特 征 ， 更 大程 度 保 留 地 物 的 形 态 便 于 后 续 处 理 和 分 析 Ｊ 。在 Ｔ Ｉ Ｎ生成 方 法 中 ， Ｄ ｅ ｌ ａ ｕ ｎ ａ ｙ三 角 剖 分 具 有 最 小 角 最 大 的 良好性 质 ， 是 被公认 的最 优三 角剖分 ， 因此 本文
机载激光雷达 （ Ｌ ｉ Ｄ Ａ Ｒ ） 能够快速精确地获取地
物 目标 表面 的位 置 和高 度信 息 ， 为 目标 信 息 提取 和 三维重 建 提 供 了新 的数 据 源 。Ｌ ｉ Ｄ Ａ Ｒ 点 云 中各 激 光 点是 离散 的 ， 现 有 的代 表 性 的 离散 点 云 数据 表 达
方 法
一
对 点 云数据 中的所 有激 光点 进行 三角形 区域 分
块， 并 确保 每个子 块 内激 光点 个 数 不 超 过个 数 阈值
，
具体 步骤如 下 ： （ １ ） 生成 点 云凸包 。将所 有激 光点 中 ， Ｙ ， ｘ ＋ ｙ ，
—
Ｙ最大 值 和最 小 值 点 作 为 初 始 凸 包 点 Ｊ ， 按 照 顺
时针方 向生 成初 始 凸包 ， 再 利 用 比较 斜率 的方 法 逐 步生成 点 云的 凸包 （ 如 图 １中 凸包 点 Ｃ ， ｉ ＝１ ， ２ ，
…
，
８ ） 。
（ ２ ） 搜索 点云 重心 点 。计 算 所有 激 光 点 坐标 的

Delaunay三角网剖分中的约束边嵌入算法

Delaunay三角网剖分中的约束边嵌入算法

ｉｓ ｎｅ， ｄＣ ｅｉ ｌｍｅｔｄｂ ｒｇａ ａｉ ，ｎ ａ ｃｏｄｗｉ ｑ ｉ ｍｅｔ ｏ ｅｐｏｅｔ ｎｔ ｃｓａ ａ ｂ ｅ ｎｅ ｙｐｏ ｒｍｓ ｓｙ ａｄｃｎａｃ ｒ ｔ ｒ ｕｒ ｎｓ ｆｈ ｒｊｃ． ａ ｎ ｎ ｍｐ ｅ ｌ ｈｅ ｅ ｔ ［ ｙｗｏｄ ｉｃｎｔ ｉｅ ｄ ｅＤｅａｎ ｙｔａｇ ｌｔ ｎ ｄａｏ ａ Ｋｅ ｒ ｓ ｏ ｓａｎｄｅ ｇ ； ｌ ａ ｉ ｕａｉ ；ｉｇ ｎ ｌ ｒ ｕ ｒｎ ｏ
维普资讯
第 ３ 卷 第 １ 期 ３ ６
、ｌ ， ３３ ｏ
・
计
算
机
工
程
２０ ０７年 ８月
Ａｕ ｓ ０ ７ ｇｕ ｔ２ ０
Ｎｏ Ｊ ．６
Ｃｏ ｐｕ ｅ ｇｉ ｅ ｉ ｍ ｔ ｒＥｎ ｎｅ ｒｎｇ
软件 技术 与数据 库 ・
文章编号：ｌｏ ４８ ０７６ ０６＿３ 文献标识码；Ａ ００ ２（Ｈ）—０５＿ Ｈ—３ ２ｏ ｌ ＿ｏ
Ｄ・ｒａ ｇ ｌ ｔ ｎ ｉ ｔ ｔｉｎ ｕ ａ ｉ ｎ ｏ ＣＤ—ｒａ ｇ ｌ ｔ ｎ ｔ ａ ｏ ｓｒ ｉ ｅ ｄ ｅ ｉ ｎｓ ｒｅ ｎ ｏ Ｄ・ ａ ｇ ｌｔｏ ， ｎ ｌ ｏ ｔ ｎ ｕ ａｉ ｈ ｔ ｎ ｔａｎ ｄ ｅ ｇ ｓｉ ｅ ｔ ｄ ｉ ｔ ｔ ｎ ｕ ａ ｉ ｎ ａ ｄ ｏｎｙ ＣＤ・ｒａ ｇ ｌ ｔ ｎ ｃ ｎ ｐ ｅ ｅ ｔｒ ａ ｅ ｒ ｉ ｎ ｉ ｏ ｃ ｉ ｒ ｔ ｎ ｕ ａｉ ａ ｒ ｓ ｎ ｅ ｌｔｒ ａｎ ａ ｄ ｉ ｏ ｅ ｉ ｆ ｔ ｉ ｔ ｕ ｅ ｏ ａ ｉ ｃ ｎ ｅ ｔ ｓ ａ ｏ ｔ ｔ ｅ ａ ｇ ｒ ｈ ｏ ｎ ｅ ｎ ｏ ｓ ｒ ｉ ｅ ｄ ｅ ｎ ｌ ｓ ｓ ｐｒ ｅ ｔ ａ ｇ ｉ ｒ ｌｅ ．Ｉ ｎ ｒ ｄ ｃ ｓ ｓ ｍｅ ｂ ｓｃ ｏ ｃ ｐ ｉ ｎ ｂ ｕ ｈ ｌ ｏ ｔ ｍ ｆ ｉ ｓ ｒｉ ｇ ｃ ｎ ｔａ ｎ ｄ ｅ ｇ ，ａ ａｙ ｅ ｅ ｓ ｎ ｌｏｒ ｈｍｓ ｈ ｒ ｃ ｅ ｉ ｔ ｓ ａ ｄ ｏ ｏ ｉ ｔ ｔ ’ｃ ａ ａ ｔ ｒｓｉ ｎ ｃ ｐ ｅ ｅ ｔ ａ ｂ ｔｅ ｌ ｏ ｔ ｍ ｆｉ ｓ ｒｉ ｇ ｃ ｎｓｒ ｉ ｅ ｄ ｅ — “ ｎ ｅ ｉ ｇ ｓ ｐ ｉ ｇ ａｇ ｒｔ ｍ ． ｅ ａ ｇ ｒｔ ｍ ａ ｆｅ ｔｖ ｌ ｅ ｌ ｔ ｌ ｋ ｎ ｓｏｆ ｒ ｓ ｎ ｓ ｅ ｔｒ ａｇ ｒ ｈ ｏ ｎ ｅ ｎ ｏ ｔａ ｎ ｄ ｅ ｇ — ｉ ｔ ｉ ｓ ｒ ｎ ・ ｗａ ｐ ｎ ” ｌ ｏ ｈ ｔ ｉ Ｔｈ ｌ ｏ ｉｈ ｃ ｎ ｅ ｆ ｃ ｉ ｅ ｙ ｄ ａ ｗｉｈ ａ ｌ ｉ ｄ

基于三角网生成法的Delaunay三角网生成算法的研究与实现

基于三角网生长法的Delaunay三角网生成算法***************【摘要】论文简要介绍了Delaunay三角网的性质以及基本生成算法，并重点介绍了三角网生长法的基本原理和算法步骤，并通过设计合理的数据结构，对算法进行实现。

对算法进行分析并提出通过构建格网索引，进一步提高三角网生成效率。

【关键词】三角网生长法扩展TIN 格网索引1.引言数字地形模型DTM（Digital Terrain Model）是指对地形表面形态属性信息的数字表达，是带有空间位置特征和地形属性特征的数字描述[1]。

DTM是GIS的基础数据来源，可用于土地利用现状的分析、合理规划及洪水险情预报等。

DTM地形属性为高程时称为数字高程模型(DEM)。

DEM主要的三种表示模型为规则格网模型、等高线模型、不规则三角网模型（Triangular Irregular Network 简称TIN）。

数字化等高线模型不适合计算坡度或制作地貌渲染图等地形分析，规则格网数据结构简单，计算方便；但存在数据冗余，数据采集较麻烦，难以表达复杂地形等缺陷。

TIN即能够避免平坦地形时数据冗余，也能表达复杂地形，可以根据任意地形特征点表示DEM，因此被广泛应用。

Delaunay三角剖分能最大程度的接近等边三角形，避免狭长三角形，并且能保持三角网的唯一性，使其成为生成TIN的最佳选择。

本论文将简要介绍和比较几种常用的Delaunay三角网生成算法（逐点插入法，三角网生长法，分割合并算法等），并且对三角网生长法算法原理进行研究分析和程序实现。

2.Delaunay三角网的性质Delaunay三角网中的三角形必须满足以下几个性质：（1）空圆特性每一个Delaunay三角形的外接圆不包括Delaunay三角网中的任何其他点。

（2）最大最小角特性在三角剖分中，Delaunay三角网的所有三角形的最小角之和最大。

即使得Delaunay三角形最大程度接近等边三角形。

基于Qi算法的Delaunay三角网逐点插入法

插 入 法 Ｄ ｌｕ ａ 角 网构建 及插 入 约 束边 的 效 率 。 ｅ ｎ ｙ三 ａ
关键 词 ： ｅ ｕ ａ Ｄ ｌ ｎ ｙ三角 网； ａ 拓扑关 系； ｉ Ｑ 算法； 效率
ｄ ｉ１ ． ９ ９ ｊｉｓ ． Ｏ Ｏ ３ ７ ． ０ １ ０ ． １ ｏ ： ０ ３ ６ ／．ｓｎ １ Ｏ 一 １ ７ ２ １ ． １ ０ ９
ｉ ｅ ｔｓ ｏ ｈ ｔｔ ｔｏ ｕ ｔ ｎ ｏ ｈ ｌ ｏ ｉ ｍ ａ ｍ ｎ ｈ ｗｓｔ ａ ｈｅｉ ｒ ｄ ｃ ｉ ｆｔ ｅＱｉ ｇ ｒｔ ｎ ｏ ａ ｈ ｃ ｎ ｉ ｒ ｖ ｈ ｆｉｉｎ ｙｏ ｕ ｌ ｉ ｇ Ｄｅ ａ ｎ ｙ Ｔｒａ ｇ ｌ ｔ ｎ ｕ ｉ ｇ ｐ ｉ ｔ ｍｐ ｏ ｅｔ ｅ ｅ ｆ ｅ ｃ ｆｂ ｉ ｎ ｌ ｕ ａ ｉｎ ｕ ａ ｉ ｓｎ ｏｎ － ｃ ｄ ｏ
Ｄｅ ａ ｎ ｙ Ｔｒａ ｇ ｌ ｔ ｎ ｅｆｃｅ ｔｙ Ａｆｅ ｎ ｌ ｚｎ ｈ ｒ ｃ ｄ ｒ ｆ ｃ ｎ ｔｕ ｔ ｎ ｏ ｌ ｕ ａ ｉ ｎ ｕ ａ ｉ ｎ ｗｉｈ ｕ ｏ ｔ ｏ ｌ ｕ ａ ｉｎ ｕ ａ ｉ ｆｉ ｉｎ ｌ ． ｔ ｒ ａ ａ ｙ ｉ ｇ ｔ ｅ ｐ ｏ ｅ ｕ ｅ ｏ ｏ ｓ ｒ ｃ ｉ ｆ Ｄｅ ａ ｎ ｙ Ｔｒａ ｇ ｌ ｔ ｔ ｏ ｔ ｃ ｎ ｒ ｌ ｏ ｏ ｏ
过 程 中， 次 引入 Ｑ 算 法 ， 而提 高 了构 网 的 效 率 。 为 了验 证 上述 模 型 ， 们 在 Ｍｉ ｏｏｔ ｉ ａ Ｓｕ ｉ ２０ 再 ｉ 从 我 ｃ ｓｆ Ｖ ｓ ｌ ｔｄ ０ ５开 ｒ ｕ ｏ
发环境 下 ， Ｃ 以 ＃为开发 工具 ， 采用底层开发模 式实现 了改进 的逐 点插 入 法， 实验 证 明引入 Ｑ 算法能够提高逐 点 ｉ
ｂ ｕ ｄ ｒ ｓｎ ｏｎ －ｎ ｅｔｏ ｔｏ ｔ ｅａ ｔ ｏ ｓｉｔｏ ｕ ｅ ｈ ｌｏ ｉｈ ｔ ｈ ｅ ｔｐ ｏ ｕｌｉｇ ｎ ｄ －ｏ ｏｏ ｙ Ｔｈ ｏ ｎ ａ ｙｕ ｉｇ ｐ ｉｔｉｓ ｒｉｎ ｍｅｈ ｄ，ｈ ｕｈ ｒ ｎ ｒ ｄ ｃ ｄｔ ｅＱｉ ｇ ｒｔｍ ｏ ｔ ｅｋ ｙｓｅ ｆｂ ｉ ｎ ｏ ｅｔｐ ｌｇ ． ｅ ａ ｄ Ｑｉ ｌｏ ｉｈ ｗａ ｄ ｐ ｅ ｇ ｉ ｅ ｎ ｅ ｔ ｇｃ ｎ ｔａｎ ｄ ｂ ｕ ｄ ｒ ｓｉｔ ｈ ｌｕ ａ ｉｎ ｕａ ｉｎ ｔ ｒ ｖ ｈ ｆｉｉｎ ｇ ｒｔｍ ｓａ ｏ ｔｄａ ａｎ ｗｈ ｎｉ ｓｒｉ ｏ ｓｒｉｅ ｏ ｎ ａ ｉ ｎ ｏｔ ｅＤｅａ ｎ ｙＴｒａ ｇ ｌｔｏ ｏｉ ａ ｎ ｅ ｍｐ ｏ ｅｔ ｅｅｆ ｅ — ｃ

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

图5.2.1逐点插入法构建Delaunay三角网
可见，由于步骤（3）的处理，保证相邻的数据点渐次插入，并通过搜寻加入点的影响三角网（Influence Triangulation），现存的三角网在局部范围内得到了动态更新。从而大大提高了寻找包含数据点的三角形的效率。
5.3
当不相交的地形特征线、特殊的范围边界线等被作为预先定义的限制条件作用于TIN的生成当中时，必须考虑带约束条件的Delaunay三角网。最简单的处理方法是所谓的“加密法”，即通过加密约束线段上的数据点，将约束数据转换为普通数据，从而按标准Delaunay三角形剖分即可。尽管该方法加大了数据量并改变了原始数据集，但由于简单易行、稳定可靠，在许多情况下可以很好地满足需要。该方法唯一的问题在于如何恰当地确定特征线上加密数据点之间的距离，一般取平均数据点间距的一半或更小即可。以下内容主要介绍直接处理约束线段的算法。
定义2：令单点集M和线段端点集E之并为V（V=M∪E），如果在V的每个Delaunay三角形的外接圆范围内不包含任何与三角形的顶点均通视的其它点，而点Pi与Pj（Pi，Pj∈V）当且仅当连线PiPj不与L中的任何约束线段相交叉（除在端点处外）时才互相通视，那么称这个Delaunay三角网为V由L约束的Delaunay三角网（朱庆，陈楚江，1998）。
（a）三角形与等高线相交；（b）三角形的三个顶点都位于同一条等高线上
图5.3.3对等高线进行不合理三角化的例子
将等高线作为特征线生成三角网一般有两种算法：将等高线作为特征线的方法、自动增加特征点及优化TIN的方法。
将每一条等高线当作断裂线或结构线时，对三角形而言，至多只能从同一等高线取两个点。图5.3.4显示了一个考虑等高线特性的Delaunay三角网。
（1）搜寻分别对应x-y，x+y最大值及x-y，x+y最小值的各二个点。这些点为凸闭包的顶点，且总是位于数据集的四个角上，如图5.1.2（a）中的点7，9，12，6所示；

TIN_边生长法

不规则三角网（TIN）的生成算法 ——递归生长法
算法简介
Delaunay三角网 (Delaunay Triangulation Irregular Network ,D-TIN) 是一系列相互连接但不重合的三角形的集合，每个三角形的外接圆内， 不包含其他的点，是空外接圆。 其次，点集构成的三角网中，delaunay三角网的三角形的最小内角最大。
P4 P3
P5 P2
P1
常用构建D-TIN算法：递归生长算法 逐点插入法 凸闭包收缩法
基础算法
ห้องสมุดไป่ตู้ 基础算法
如何判断点在直线的左侧还是右侧：平面上三点的面积量
y p1
p2
p3 x
S (P1, P2 , P3 )
x1 x3 x2 x3 y1 y3 y2 y3
S 0, 在矢量 P1P2 左侧
S 0, 在矢量 P1P2 右侧
p3
x
递归生长法
递归生长法
P3 P2
P1
递归生长法
P3’ P3
P2 P1
递归生长法
P3 P3’’
P2 P1
递归生长法
出现重复情况，就把新生成的边删除，最后就保留了不重复的边
P5 P3
P2
P1
P6 P4
P8
P7
递归生长法
THANKS
S =0, 在矢量 P1P2 上
基础算法
判断距离直线最近的点：夹角最大原则
y p1
a b a b cos
a b xa xb ya yb
p2
cos
(x1 x3 ) (x2 x3 ) (y1 y3 ) (y2 y3 )
(x1 x3 )2 (y1 y3 )2 (x2 x3 )2 (y2 y3 )2
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
3、优点：结构良好，数据 结构简单，数据冗余度 小，存储效率高，可适 应各种分布密度的数据。
p1
p4
p2 p3
p6
p5
三、Voronoi图 （泰森多边形或Dirichlet图）
由一组由连接两邻点直线的垂直平分线组成的连续多 边形组成。 N个在平面上有区别的点，按照最邻近原则划分平面； 每个点与它的最近邻区域相关联。 Delaunay三角形是由与相邻Voronoi多边形共享一条 边的相关点连接而成的三角形。 Delaunay三角形的外接圆圆心是与三角形相关的 Voronoi多边形的一个顶点。
Voronoi三角形是Delaunay图的偶图 。
4、依次将新形成的三角形的边作为基边，形成新 的控制边链表，按照上述第2步，对控制边链表所 有的线段进行循环，再次向外扩展，直到所有三 角形不能再向外扩展为止。
NT
2019/6/3
2019SUCCESS
THANK YOU
2019/6/3