学步园

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

  

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

简单多边形与复杂多边形

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

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

自相交多边形

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

凸多边形与凹多边形

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

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

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

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

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

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

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

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

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

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

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

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

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

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