graphics - 将三角多边形划分为较小的多边形

Question

我有一个多边形，它有 X 个顶点。多边形已经被三角化成 X-2 个三角形。假设多边形有 100000 个顶点。如何将其划分为 2 个多边形，因此其中一个的顶点数为 65535 或更少（不能更大）？

Answer 1

对偶图（每个三角形的节点，相邻三角形的弧）是一棵树。您可以遍历这棵树并跟踪每个节点确定的子树中有多少节点。因为节点的度数最多为三，所以您应该能够实现三分之二的目标。