耳切法处理多边形三角划分

发表于2017-10-10

这也是我Get到的新概念，一种网格多边形三角化算法之一。

我之前也写过文章关于在Unity下使用Mesh 绘制多边形，正方体、三棱锥等。

我在搜索这个概念的时候看到一篇非常好的翻译文章：

http://www.cnblogs.com/xignzou/p/3721494.html

抱歉，我下面也只是做一个粘贴而已。和一些自己当时的理解

使用EarClipping三角化多边形（翻译）

---Triangulation by Ear Clipping(http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf)

内容提要

1、简介

2、Ear Clipping方法

3、含有岛洞的多边形

4、查找相互可见点

5、含有多个岛洞的多边形

6、嵌套多边形

1、简介

将简单多边形转换成一组由同样顶点组成的三角形集合是计算机图形学中的一个经典问题。问题中，简单多边形是指由一组有序顶点组成的，点V0~点Vn-1。相邻的顶点之间通过边(Vi,Vi-1)连接，并且边（Vn-1,V0）连接起始点。每个顶点被两条边所共享，而边的所有交点都是顶点。图1.1的示例则是说明

图中，左边的多边形是个简单多边形，中间的多边形点1被四条边共享，不符合定义的条件，不算是简单多边形，右侧的多边形中边14，边02的交点不是我们定义的顶点之一，因此该图形也不符合简单多边形的定义。

耳切法处理多边形三角划分

图1.1 简单多边形示例

如果一个多边形是简单多边形，当你延长一条边的时候，内部有界区域中总是在边的一侧。假设多边形顶点逆时针排序，那么当你延长边的时候，内部指的便是你的左边。 我们图1.1中的简单多边形顶点顺序使用的便是逆时针的方法。

将一个简单多边分解成三角形集合的方法称之为多边形的三角形化（triangulation of thePolygon）。几何学的知识告诉我们，由n个顶点组成的简单多边形总是可以分解成n-2个三角形。解决该问题的方法比较多，他们共同的特点就是算法的复杂度渐近阶随着n的增长没有约束(Various algorithms have beendeveloped for triangulation, each characterized by its asymptotic order as ngrows without bound.)。最简单的分割算法是耳剪裁（EarClipping），正是本文档中所要描述的算法。EarClipping的算法复杂度O(n2_n平方)，虽然也存在效率更高的算法，但是被其他组织严格使用并没有公开。水平分解成梯形随后被自己单调三角多边形的鉴定阳离子是一种复杂度为O（nlog n）的算法[ 1 ， 3 ] 。使用增量的改进随机算法产生一个O （ n日志？ n），其中记录？ n为重对数函数[ 5 ]。此功能是电子？作为各自一个常数非常大的n ，你会在实践中看到的，所以对于所有的实际目的的随机方法是线性时间。理论存在的复杂度为O(n)的算法，比较复杂，到目前依旧没有看到具体的公开实现。

2、Ear Clipping方法

简单多边形的耳朵，是指由连续顶点V0,V1和V2（就是这样的顺序相邻）组成的内部不包含其他任意顶点的三角形。在计算机几何术语中，v0与V2之间的连线称之为多边形的对角线（这个找完之后要在编辑器中显示出来会更好看出三角形分割），点V1称之为耳尖（找耳尖也是这么找的）。虽然你可以将耳尖放到三角形的任意一个顶点上，但是我们认为三角形包含一个耳尖。一个由四个顶点（或者更多）组成的多变形至少有两个不重叠的耳尖。这个特性提供了一个通过递归来解决三角化分割的方法。针对由N个定点组成的多边形，找到其耳尖，移除唯一耳尖上的顶点，此时剩余顶点组成了一个n-1个顶点的简单多边形。我们重复这个操作知道剩余三个顶点。这样的话会产生一个复杂度为O(N3)的算法。

我发现一个现象，如果一个顶点是耳尖，一定是凸顶点。反之不成立。

随着一些细节改进，耳朵消除可以在O （N2）的时间来完成。第一步是将多边形使用双向链表存储，这样可以快速的移除耳朵。列表的构建复杂度是O（n），第二部是遍历顶点寻找耳朵。对于每一个顶点Vi和围绕该顶点的三角形<Vi-1,Vi，Vi 1>，(总长度为N，所以Vn=V0，兵器V-1=Vn-1),测试其他顶点是否在当前三角形中，如果有一个顶点在三角形里面，则不是耳朵，只有都不在的情况，才算是找到一个耳朵。具体实现的时候我们可以考虑以下因素让这个算法更为高效。当发现有一个点在三角形里面的时候便可以开始放弃当前测试。一个凹拐角其两边的夹角大于180，而一个凸拐角两边夹角小于180。存储多边形的数据结构使用四个链表，具体使用数组而不是标准的动态需要分配合释放存储器的链表。多边形的顶点存储在在一个循环链表中，凹顶点和凸顶点存储在线型表中，耳尖存储在一个循环列表中。

这里要说明一下，怎么判断一个拐角是凸凹，通过两个临边求叉积（法线方向），如果>0 说明是角度<180 是凸角度，反之。。。。

怎么判断一个点在没在三角形内呢？ 顺时针／逆时针判定法。 该方法要求点的顺序是顺时针或逆时针的，如果是顺时针的点，沿着3条边走，如果目标点P在三角形内，那么P始终在边的右侧。同理，如果是逆时针的话，目标点p应该始终在边的左侧。 例：逆时针的三个点abc，判断abXap , bcXbp , caXcp,如果这三个向量叉积的Z值都同向，并且都为负的话（左手系），说明p点在三角形内部。（Unity使用的是右手坐标系，也是右手法则，逆时针旋转，大拇指向旋转的正方向）

http://blog.csdn.net/evilbox/article/details/42681381  
//原理：通过向量之间的对比，利用点乘和差乘实现判断一个点是否在三角形里面。  叉乘结果用右手判断法则。   
publicstatic  bool InTrigon(Vector3_target,Vector3 _center,Vector3 _left,Vector3 _right)｛  
Vector3Ctl=_left-_center;  
Vector3Ctr=_right -_center;  
Vector3Ctt=_target-_center;  
Vector3Ltr=_right-_left;  
Vector3Ltc=_right-_center;  
Vector3Ltt=_left-_target;  
Vector3Rtl=_left-_right;  
Vector3Rtc=_center-_right;  
Vector3Rtt=_target-_right;  
if(          
  Vector3.Dot(Vector3.Cross(Ctl,Ctr).normalized,Vector3.Cross(Ctl,Ctt).normalized)==1&&  
  Vector3.Dot(Vector3.Cross(Ltr,Ltc).normalized,Vector3.Cross(Ltr,Ltt).normalized)==1&&  
  Vector3.Dot(Vector3.Cross(Rtc,Rtl).normalized,Vector3.Cross(Rtc,Rtt).normalized)==1  
   )  
returntrue;  
else  
returnfalse;  
｝

一旦凸顶点和耳朵的链表构建成功，每次遍历都会移除一个耳朵。假设当前Vi是个耳朵并且被移除掉，那么边结构的相邻点Vi-1,Vi 1则会发生变化，如果相邻点是凸顶点，那么依旧保持凸点，如果相邻点是个耳朵，那么当Vi被移除后则不一定能保持耳朵的状态，如果相邻点是个凹点，那么他则有可能变为一个凸点甚至是耳朵。因此当移除顶点Vi后，如果相邻点是凸点，则必须遍历相关顶点，通过遍历查看是否包含其他点，来测试它是否是一个耳朵。我们有n个耳朵，每一次更新都会触发一个耳朵检测，每次过程中更新O（n），所以移除进程的复杂度是O(n2)。

耳切法处理多边形三角划分

图2.1 右侧多边形展示了左侧耳朵2,3,4被移除后的的效果

下面的示例使用图1.1中的简单多边形，具体展示算法的实现和构建。初始够将的时候凸顶点集合C=｛0,1,3,4,6,9｝，初始凹顶点集合R=｛2,5,7,8｝,初始的耳朵集合E=｛3,4,6,9｝（按照定义，顺序跑一遍就找到了）,遍历，当顶点3被移除的时候，其对应的耳朵是三角形T0=<2,3,4>。图2.1展示了改进后的多边形效果。相邻点2是个凹节点，变化后依旧是凹的，顶点4之前是个耳朵，现在依旧耳朵，所以凹节点结合R保持不变，耳朵集合现在变成了E=｛4,6,9｝(3已经被移除)。

继续移除点点4，此时的三角形对应是T1=<2,4,5>。图2.2展示了变化后的效果。

耳切法处理多边形三角划分

图 2.2 移除三角形<2,4,5>后的效果

相邻顶点2依旧保持凹节点，相邻点5之前是凹顶点，现在变为了凸顶点，经过测试最终发现它是个耳朵。因此定点列表最终的变化结果是，凹节点几何R=｛2,7,8｝,耳朵集合E=｛5,6,9｝(移除4，添加了新的5)。

如果一处顶点5，此时对应的三角形是T2=<2,5,6>,图2.3展示了变化后的效果。

耳切法处理多边形三角划分

图2.3 移除耳朵<2,5,6>后的效果

相邻顶点2起初是个凹节点，现在变为另一个图节点，从图上有点不大容易看出顶点7其实是位于三角形<1,2,6>中间的，所以2不是个耳朵。顶点6起初是个耳朵，现在依旧。操作完成之后各顶点列表中，凹节点集合R=｛7,8｝(移除了2)，耳朵集合E=｛6,9｝(移除了5)。

继续，移除顶点6，此时对应的三角形是T3=<2,6,7>。图2.4是变化后的前后对比效果。

耳切法处理多边形三角划分

图2.4移除耳朵<2,6,7>

相邻点2是图节点，保持依旧，但是它由一个非耳朵变成了耳朵节点。相邻顶点7依旧是个凹节点，因此凹节点集合保持不变。各队列结果，耳朵集合E=｛9,2｝(添加2移除6)，耳朵列表这样写是因为新耳朵的加入是在移除了旧的耳朵操作之后（先来后到），在移除旧耳朵之前，它忍让可以被当做是列表的第一个元素（循环列表）。删除操作设置第一项是下一个指向的老耳朵，而不是以前的值。

移除顶点9，对应的三角形T4=<8,9,0>。图2.5展示了操作前后的多边形对比

耳切法处理多边形三角划分

相邻顶点8是个凹节点，操作后编程了一个凸点，并且是一个耳朵。相邻点0是个凸点，保持依旧，并且由非耳朵变成了耳朵。操作结束后的各队列集合如下：凹点集合R=｛7｝，耳朵集合E=｛0,2,8｝(添加8，添加0，移除9，顺序按照了程序的产生方式)

移除顶点0，对应的三角形是T5=<8,0,1>,图2.6是操作前后的多边形对比

耳切法处理多边形三角划分

相邻顶点8和1都是凸节点并且保持依旧，顶点8依旧是个耳朵，顶点1依旧不是耳朵。因此凹节点集合不变，耳朵列表变为E=｛2,8｝(移除了0)

最后，移除耳朵2顶点，对应的三角形是T6=<1,2,7>。图2.7展示了操作前后的多边形对比。

耳切法处理多边形三角划分

到现在，已经没有在需要更新的凹点和耳朵列表，到此为止我们只剩下了三个顶点，这三个顶点组成最后的三角形T7=<7,8,1>。所有的三角形分割线是如图2.8

耳切法处理多边形三角划分

3、含有岛洞的多边形

耳朵裁剪法也可以应用到包含岛洞的多边形中。考虑如图3.1所示的一个包含岛洞的多边形，他有一个外多边形和一个内洞组成。外侧多边形的定点方形和内测岛洞的顶点方向必须是相反的（顶点顺序要反向）。如果外侧的顶点是逆时针顺序，那么内测的顶点则必须是顺时针顺序。

耳切法处理多边形三角划分

图中蓝色的顶点是互相可见的，通过绘制两条双向的边连接两个蓝色的顶点，可以把图3.1转变成一个简单多边形。图3.2中显示这两天便，一条蓝色，一条红色，两条边是重叠的，这里为了看得清晰特殊标绘出来。

耳切法处理多边形三角划分

图中通过小箭头标识出了边的方向。

依照这种情景，互相可见的顶点必须复制到不同的数据结构中以供使用。每个数据结构存储当前点可能是凹点也可能是凸点。即使使用同一个坐标的两个点，也可能一个是凹点，一个是凸点，比如位于最下面的蓝色顶点11(18)。原始的顶点在最初的外多边形中是凹点，分割后在新的多边形中，V11与红色边相连，构成了一个凹点，与蓝色边相连构成另一个凸点。

原始的外多边形顶点数据：

｛0,1,2,3,4,5,6,7,8,9,10,11,12,13,14｝

原始的内多边形数据

｛15,16,17｝

分割后顶点V11被复制出V18，顶点V16复制出V19，这时候的简单多边形数据如下：

｛0,1,2,3,4,5,6,7,8,9,10,11,16,17,15,19,18,12,13,14｝

新的多边形即可以使用耳朵裁剪法切割。

4、查找相互可见点

视觉上，图3.1我们可以直接看出顶点V11和顶点V16是两个相互可见的点。而实际上，这个多边形中存在不止一对这样的相互可见点（一个来自内多边形，一个来自外多边形）。我们需要个算法来查找一对这样的可见点。

下面的算法便是如此。查找内多边形中x轴方向最大值的顶点，在图3.1中，这个点是V16，假设以此为原点构造左边系，沿着x轴正方向观察，该轴线可能与外对变形的边教育一点，或者直接连接到外多边形的顶点上，很大程度上，我们会获得一个边的交点。此时，这条边的两个端点则很有可能使我们所要寻找的。如果是一个独立的点点，那么便和最初的V16组成了一对相互可见点。

下面，我们考虑在x轴正方向的最近可视点是相交边的端点。如图4.1所示：

耳切法处理多边形三角划分