多边形-三角形 ⇐ 文章草稿

[Anonymous]

多边形三角剖分是将多边形|多边形划分为三角形，即h。确定一组不重叠的三角形|三角形，并且其集合(数学)#union(并集)|union是多边形。

== 没有附加角的多边形三角剖分 ==

=== 凸多边形 ===

===剪耳===
Image:Polygon-ear.png|thumb|带有“耳朵”阴影的三角多边形
对简单多边形进行三角测量的一种方法是基于“双耳定理”。这表明每个至少有四个角且没有孔的简单多边形至少有两个“耳朵”。这些三角形的两条边是多边形的边，第三条边完全位于多边形内部。然后，该算法包括找到这样的“耳朵”，将其从多边形中删除，创建一个继续满足条件的新多边形，并重复该过程，直到只剩下一个三角形。

该算法易于实现，但比其他算法慢，并且仅适用于没有孔的多边形。维护单独的凸顶点和凹顶点列表的实现具有二次运行时间（计算机科学）。这种方法称为“剪耳”或有时称为“剪耳”。
=== 单调多边形 ===
Image:Polygon-to-monotone.png|thumb|多边形分解|多边形分解为单调多边形 如果一条正交线与多边形最多相交两次，则简单多边形相对于直线是单调的。一个单调多边形可以分解为两个单调链。相对于 y 轴单调的多边形称为 y 单调。具有 n 个顶点的单调多边形可以在线性运行时间（计算机科学）|运行时间内进行三角测量。假设给定的多边形是 y 单调的，贪婪算法首先从上到下遍历多边形链，尽可能添加对角线（几何）|对角线。容易看出该算法可以应用于任何单调多边形。

=== 非单调多边形 ===
如果多边形不是单调的，则可以在运行时使用扫描方法将其划分为单调子多边形O(n \cdot \log(n))。该算法不需要简单的多边形，因此可以应用于有孔的多边形。一般来说，该算法可以在 O(n \cdot \log(n)) 运行时间和 O(n) 存储空间中对具有 n 个顶点的平面分解进行三角剖分。
==另见==
* Delaunay 三角测量
* 平面图



类别：算法几何
类别：几何图形