本节主要讲解了如何将二维多边形划分为多个不相交的三角形。
一、画廊问题 art gallery problem
考虑如下场景，在一个尺寸为多边形的画廊中放置摄像头（哨兵），需要放几个才能完全覆盖该场景？可以看到下图至少需要两个哨兵。
如下图，若多边形是凸多边形或星形多边形，那么只须在中间的核位置放一个即可，此情况为该问题的最小解（下界）：
若多边形不规则，那么最多n个点，即n多边形的每个顶点都设置一个哨兵，就可以将整个多边形覆盖，因此问题的最大解（上界）为n。
实际上，对于n个顶点的不规则多边形而言，最多只须n/3个点即可覆盖，如下图红点所示：
文章来源：https://www.toymoban.com/news/detail-406587.html
因为场景不同导致的情况不同，在数学上有证明指出画廊问题是NP-Hard问题，就是非确定性多项式困难问题文章来源地址https://www.toymoban.com/news/detail-406587.html
二、Fisk's Proof
一些概念：
- 扇形：一个有核点的星形多边形。每个扇形可以由一个点覆盖整个扇形。
到了这里，关于计算几何——三角剖分（Triangulation）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
