将三角形多边形划分为更小的多边形

Question

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

Answer 1

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