复杂多边形与简单多边形

参考
复杂多边形与简单多边形

一、多边形的定义

多边形是平面的封闭、由有限线段（大于2）组成，且首尾连接起来划出的形状。

1.简单多边形

简单多边形的定义：简单多边形是边不相交的多边形，又称佐敦多边形，因为佐敦曲线定理可以用来证明这样的多边形能将平面分成两个区域，即区内和区外。

在拓扑学上，简单多边形和球同胚。

在计算几何学有几个重要问题，其输入都是简单多边形：

• 点在多边形内：决定一点是否在多边形内
• 求多边形面积
• 将多边型切割成三角形

这个图片的分类是错误的，中间有孔的应该算复杂多变形了

2.复杂多边形

这几乎是我们平时研究内容的全部，那么什么是复杂多变形呢？

复杂多变形（我个人认为的），多条边共用一个节点（超过两个），中间有空，或者中间有孤岛（这个就不能称之为多边形了吧？），但是有论文把它拿出来作为复杂多边形分析，可能二维的集合体没有办法说清楚，只能这样归类了，除了简单的多边形就属于复杂的多边形了。 对于计算机编程人员来说，他们的分类就清晰多了，有一定的实用性

image.png

3.简单多边形与复杂多边形

简单多边形不包含"洞"，复杂多边形可能包含"洞"（图12.26）。简单多边形可以通过沿多边形列出的所有顶点来描述（左手坐标系中，通常以从多边形正面看时的顺时针方向列出所有点）。简单多边形的使用频率比复杂多边形高得多。

image.png

通过添加一对"接缝"边，能将任意复杂多边形转化成简单多边形，如图12.27所示。见右边的放大图，我们在每个"缝"添加了两个边，这两个边实际上是重合的，放大图中将其分开是为了让你看得更清楚。当我们考虑到绕多边形的边的顺序时，这两个接缝边的方向是相反的。

image.png

4.自相交多边形

大多数简单多边形的边不相交，如果有的边相交了，那么这个多边形叫做自相交多边形。一个简单的自相交多边形如图12.28所示。

image.png

5.凸多边形与凹多边形

非自相交多边形能进一步细分为凸多边形和凹多边形。给凸多边形下一个精确定义是一件非常困难的事，因为存在很多令人棘手的退化形式。对大多数多边形，下列常用的定义是等价的。不过对于一些退化多边形来说，根据一种定义它是凸的，而根据另一种定义它又可能是凹的。

• （1）直观上，凸多边形是没有任何"凹陷处"的，而凹多边形至少有一个顶点处于"凹陷处"----凹点。

• （2）凸多边形，任意两顶点的连线都包含在多边形中。但在凹多边形中，总能找到一对顶点，它们的连线有一部分在多边形外。

• （3）沿凸多边形周边移动时，在每个顶点的转向都是相同的。对凹多边形，一些是向右转，一些是向左转，在凹点的转向是相反的（注意这仅是对非自相交多边形来说的）。

前面曾提到过，退化多边形会使这些相对清晰的定义变得模糊不清。例如一些多边形有两个连续的顶点重合，或这一条边以相反的方向重复了两次。能认为这些多边形是凸的吗？实践中，经常用到下列凸性的定义:

• （1）如果只能对凸多边形起作用的代码对这个多边形也能起作用，那么它就是凸的（也就是说如果一个定义没有被打破就不用修正它）。

• （2）如果凸性测试算法判断它是凸的，那么它就是凸的（这是由"算法定义"解释的）。

现在，让我们忽略一些病态情况，给出一些大家意见都一致的凸、凹多边形。如图12.29所示，右上角的凹多边形有1个凹点，而下面的凹多边形有5个凹点。

image.png

任意凹多边形都能分解为凸多边形片，它的基本思路是定位凹点并通过添加对角线来有系统地移除它们。

6.怎样才能知道一个多边形是凸的还是凹的？

一种方法是检查各顶点的内角和，考虑n个顶点的凸多边形，它的内角和为(n-2)180。,有两种方法可以证明这个结论。

（1）设θi为顶点i的内角，很明显，θi≤ 180。(假设多边形是凸的)。在每个顶点上，补角为（180-θi）。，对于一个封闭的凸多边形，全部顶点的补角之和为360。，有：

image.png

（2）任意n个顶点的凸多边形都能分解为n-2个三角形，由经典几何知识可知，三角形内角和为180。。所有三角形的内角和为(n-2)180。，可以看到，这个和总是等于多边形的内角和。

不幸的是，凹多边形和凸多边形一样，内角和也是(n-2)180。。怎样才能进一步判断一个多边形是不是凸多边形呢？对一个凸多边形，内角不会大于外角。（外角不是补角，一对内角外角的和等于360。）

所以，将每个顶点处较小的角（内角或外角）相加，凸多边形得到(n-2)180。，凹多边形则小于它。怎样判断哪个角较小呢？幸运的是，有这样一个工具 ---- 点乘，这种方法返回的角总是以较短的弧度来度量的。

另一种检测凸性的方法是检测多边形上是否有凹点，如果一个都没有找到，就是凸多边形。它的基本想法是每个顶点的转向应该一致，任何转向不一致的点都是凹点。

怎样检测一个点的转向呢？技巧是利用边向量的叉乘，左手坐标系中，如果向量的转向是顺指针，它们的叉乘就会指向你。什么是指向你呢？我们从多边形的正面看，正面由法向量指明。如果没有提供法向量，就必须做一些计算来得到。一旦有了法向量，检查多边形的每个顶点。用相邻的两个边向量计算该顶点的法向量，接着用多边形的法向量和顶点的法向量点乘，检测它们的方向是否相反。如果是（点乘为负），那么这个顶点就是一个凹点。

7.三角分解和扇形分解

任意多边形都能分解为三角形。因此，所有对三角形的操作都能应用到多边形上。复杂、自相交、甚至简单的凹多边形的三角分解都不是一件简单的工作。幸运的是，简单多边形的三角分解是一件容易的事。

一种显而易见的三角分解技术是选取一个点（称作第一个点），沿着顶点按"扇形"分解多边形。给定一个有n个顶点的多边形，沿多边形列顶点v1...vn，能够很容易地构造形如{v1,vi-1, vi}的n-2个三角形，见图12.30。

image.png

扇形三角分割会分割出一些长的、较细的三角形，这在某些情况下会引起麻烦。如同计算表面的法向量一样，数值的不精确性在度量极小的角时会造成一些问题。

一种更加"聪明"的分解方法是：连接两顶点的对角线将一个多边形分解为两部分。这时，对角线端点处的两个内角都能分解为两个新的内角。因此，总共产生了4个新内角。为了分解多边形，选择能使这4个新内角中最小的角最大化的对角线，用这条对角线将多边形分为两个。对分割后的每一部分都递归应用这个过程直到剩下的都是三角形。

这个方法产生较少的细三角形，但在实践中，它过于复杂。根据几何学和应用目的，扇形分解已经足够了（并且简单得多）。

8.多边形三角化算法：

遍历多边形每个顶点，计算该点处内角大小；

• 当内角小于180度，当前点和该点前后两点构成一个三角形，该点从多边形顶点队列中删除。
• 当内角大于等于180时，跳过该点处理下一个点；
• 循环处理多边形的顶点队列，直到队列中顶点个数小于3；

算数复杂度：每构建一个三角形，多边形顶点就少一个；当多边形有N个顶点时，至少需要构建N-2个三角形，理想的凸多边形情况下，需计算N-2次内角；假设50%概率遇到大于180的内角，则需要计算2*（N-2）次内角角度。