將三角形多邊形劃分爲更小的多邊形

Question

我有一個具有X個頂點的多邊形。多邊形已經被三角化爲X-2三角形。假設多邊形有100000個頂點。我如何將它分成2個多邊形，所以其中一個頂點的數量是65535或更少（不能更大）？

Answer 1

對偶圖（每個三角形的節點，相鄰三角形的弧）是一棵樹。您可以遍歷此樹並跟蹤每個節點確定的子樹中有多少個節點。因爲節點最多有三個學位，所以你應該能夠達到你的三分之二的目標。