个人笔记|GIS的ear clipping算法

作者: 图骨南 | 来源:发表于2022-05-13 16:23 被阅读0次

个人笔记|GIS的ear clipping算法
词汇学第一单元简答题(1)
GIS常用算法
CentOS7下用户登录相关
电脑小工具、窍门
WebGIS开发-openlayers5入门(1)
How to apply gradient clipping i
芒种：谷物开始成熟盛夏
C# GIS算法之球面任意多边形面积算法
input追加内容

对论文Triangulation by Ear Clipping 的理解
不涉及带孔洞的多边形及多边形迭代
问就是功能不需要

声明：在本学习笔记的写作过程中，没有一只猫猫受到实际伤害。
（包括赛博猫猫在内）

引入

计算机图形学的多边形分解问题

简单多边形定义

定义一个简单多边形为由从 $V_0$ 到 $V_{n-1}$ 的 $n$ 个点组成的有序序列。两相邻顶点之间以边 $<V_i,V_{i+1}>,0\leq i\leq n-2$ 相连，且起点和终点之间以边 $<V_{n-1},V_0>$ 相连。简单多边形的每个顶点有且仅有两条边，简单多边形的任意两条边仅在顶点处相交。简单多边形和复杂多边形的对比如图所示

简单与复杂多边形对比

左侧多边形为简单多边形。中间的多边形的顶点1有两条以上边，不为简单多边形。右侧多边形中连接顶点1和顶点4的边与其他边在非顶点处相交，该多边形不为简单多边形。

在一个简单多边形中，当遍历边缘时，多边形内部的有限区域总处于遍历方向同一侧。假设以逆时针方向遍历例图中的简单多边形边缘，则多边形内部区域始终处于遍历方向左侧。

多边形三角化算法

将简单多边形分解为多个三角形的过程叫做多边形三角化。对具有 $n$ 个顶点的任意多边形进行三角化分解都会得到 $n-2$ 个三角形。在诸多算法中复杂度为 $O(n^2)$ 的ear clipping算法算是最简单又好用的一个，其他复杂度更低的算法也存在，不过会比ear clipping更难实现。

Ear Clipping算法

下文用猫耳朵指代ear 用咔耳朵算法指代ear clipping）

我觉得论文作者也会赞同的除了猫奴还有谁会看到三角形就想到尖尖耳朵呢）

定义

猫猫耳朵

多边形的一只猫猫耳朵是由三个相邻顶点 $V_{i_0},V_{i_1},V_{i_2}$ 构成的三角形，其中 $V_{i_1}$ 是三角形凸出的顶点，在该顶点处三角形的内角角度小于 $\pi$ 。作一条连接点 $V_{i_0},V_{i_2}$ 的辅助线，该线段完全位于多边形内部。这只猫猫耳朵只含有构成耳朵的三个顶点，不包含多边形的其他顶点。在计算机几何学术语里把连接点 $V_{i_0},V_{i_2}$ 的辅助线叫做多边形的一条对角线，把顶点 $V_{i_1}$ 叫做耳朵尖（猫猫的耳朵根根和耳朵尖尖，懂得都懂）。一个三角形就是一只猫猫耳朵，三角形的任意一个顶点都可以是耳朵尖尖。

有四条边及以上的多边形拥有至少两只不重叠的耳朵，这就提供给我们一个递归实现多边形三角化的思路。若在含有 $n\geq 4$ 个顶点的多边形内确定并移除一个三角形，移除后的多边形具有 $n-1$ 个顶点。重复该过程，即是复杂度为 $O(n^3)$ 的三角化算法。

咔耳朵算法

好消息：咔耳朵算法的复杂度可以降到 $O(n^2)$

坏消息：难的步骤要来了

step1

首先，将多边形以双链表形式存储，以便快速咔掉耳朵尖尖。这个步骤的复杂度是 $O(n)$ 。

step2

其次，对顶点进行迭代，分出各个不重叠的猫猫耳朵。对于每个顶点 $V_i$ 和该顶点对应的三角形 $<V_{i-1}, V_i, V_{i+1}>$ ，测试多边形的其他顶点是否位于该三角形中。该索引对 $n$ 取模，所以 $V_n = V_0$ 且 $V_{-1} = V_{n-1}$ 。如果三角形内不包含多边形的其他顶点，我们就喜提了一只猫猫耳朵！如果三角形内至少含有多边形的一个顶点，它就不是猫猫耳朵。在三角形包容测试中效率更高的三角化方法是只考虑反射点。反射点指由两条边构成的角度大于 $\pi$ 的内部角的顶点。多边形的数据结构包含四个同时共用一个存储数组的双链表，而非动态分配和释放内存的标准列表数据结构。使用循环链表存储多边形的所有顶点，线性表存储凸顶点，另一个线性表存储反射点，另一个循环链表存储耳朵尖尖。

step3

当完成对存储反射点和耳朵尖尖的数据列表初始化后，就可以一只接一只地咔掉猫猫耳朵了！若 $V_i$ 是已经被咔掉的猫猫耳朵，那么与其相邻的顶点 $V_{i-1}$ 和顶点 $V_{i+1}$ 的边的参数随之变化。若一相邻顶点是凸出点，则其仍是凸出点。若一相邻顶点是耳朵，在移除 $V_i$ 后它可能就不再是耳朵了。若为反射点，则可能变为凸出点或耳朵。在移除 $V_i$ 后，若存在一凸出的相邻顶点，则必须通过遍历反射点和测试三角形内是否包含点来验证该相邻顶点是否为耳朵。整个过程的复杂度是 $O(n^2)$

算法示例

以第一张图的简单多边形为例

初始的简单多边形

凸出顶点的初始列表为 $C = \{0,1,3,4,6,9\}$

反射顶点的初始列表为 $R = \{2,5,7,8\}$

耳朵尖尖的初始列表为 $E = \{3,4,6,9\}$ （再复习一遍，耳朵尖尖=这个点是凸出点+和这个点相邻的两个点的连线完全在多边形内部）

凸出点	$C = \{0,1,3,4,6,9\}$
反射点	$R = \{2,5,7,8\}$
耳朵尖尖	$E = \{3,4,6,9\}$
三角形	暂无

① 把耳朵尖尖 $3$ 对应的猫猫耳朵咔掉，那么三角化咔出来的第一个三角形就是 $T_0 = <2,3,4>$ 。

咔掉第一个三角形

与 $V_3$ 相邻的顶点 $V_2$ 初始时是反射点，咔掉 $T_0$ 后仍是反射点。与 $V_3$ 相邻的顶点 $V_4$ 初始时是耳朵尖尖，咔掉 $T_0$ 后仍是耳朵尖尖。可知反射点列表 $R$ 维持原状，但耳朵尖尖列表变为 $E = \{4,6,9\}$ 。

凸出点	$C = \{0,1,4,6,9\}$
反射点	$R = \{2,5,7,8\}$
耳朵尖尖	$E = \{4,6,9\}$
三角形	$T_0=<2,3,4>$

② 然后把顶点 $4$ 对应的耳朵咔掉，可得三角化后的又一个三角形 $T_1 = <2, 4, 5>$ 。

咔掉第二个三角形

与 $V_4$ 相邻的顶点 $V_2$ 初始时是反射点，咔掉 $T_0$ 后仍是反射点。与 $V_4$ 相邻的顶点 $V_5$ 初始时是反射点，咔掉 $T_1$ 后变成了凸出点，经过测试后确定为耳朵尖尖，故从反射点列表中移除 $V_5$ ，反射点列表变为 $R = \{2,7,8\}$ 。但耳朵尖尖列表变为 $E = \{4,6,9\}$ 。

凸出点	$C = \{0,1,5,6,9\}$
反射点	$R = \{2,7,8\}$
耳朵尖尖	$E = \{4,6,9\}$
三角形	$T_0=<2,3,4>,T_1=<2,4,5>$

如此重复直到将多边形全部三角化，得到三角形
$T_0=<2,3,4>,T_1=<2,4,5>,T_2=<2,5,6>,T_3=<2,6,7>,T_4=<8,9,0>,T_5=<8,0,1>,T_6=<1,2,7>,T_7=<7,8,1>$

分解后的多边形

个人笔记|GIS的ear clipping算法
对论文Triangulation by Ear Clipping[https://www.geometrictoo...
词汇学第一单元简答题(1)
clipping* Clipping is a way of making new words which inv...
GIS常用算法
作为一个GISer，在日常WebGIS开发中，会常用到的turf.js，这是一个地理空间分析的JavaScript...
CentOS7下用户登录相关
本文章仅作为个人笔记一：登陆相关： win下登陆linux工具putty下载链接：https://the.ear...
电脑小工具、窍门
喜欢的留言啦会继续更新都是MAC电脑的小工具如何把Kindle笔记优雅地导出？ clipping.com 思...
WebGIS开发-openlayers5入门(1)
前言：初学GIS开发是痛苦的，复杂的API加上复杂的样式算法和交互功能，总让人感觉到无从下手。从事GIS开发有一段...
How to apply gradient clipping i
Gradient clipping needs to happen after computing the gra...
芒种：谷物开始成熟盛夏
芒种 Grain in Ear Ear: the top part of a grain plant, such ...
C# GIS算法之球面任意多边形面积算法
上一章中，我们有提到GIS算法中面积计算，但是实际中的GIS面积计算并不能按平面来计算，在实际进行运用会有很大的缺...
input追加内容
var text=$('#ear .txt').val()+'、'; //原有的内容 $('#ear .txt'...

个人笔记|GIS的ear clipping算法

引入

计算机图形学的多边形分解问题

简单多边形定义

多边形三角化算法

Ear Clipping算法

定义

猫猫耳朵

咔耳朵算法

step1

step2

step3

算法示例

相关文章

个人笔记|GIS的ear clipping算法

词汇学第一单元简答题(1)

GIS常用算法

CentOS7下用户登录相关

电脑小工具、窍门

WebGIS开发-openlayers5入门(1)

How to apply gradient clipping i

芒种：谷物开始成熟盛夏

C# GIS算法之球面任意多边形面积算法

input追加内容

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读