graphics - 三角ポリゴンをより小さなものに分割する

Question

X個の頂点を持つポリゴンがあります。ポリゴンは既に X-2 三角形に三角形化されています。ポリゴンに 100000 個の頂点があるとします。それを 2 つのポリゴンに分割するにはどうすればよいですか?そのうちの 1 つの頂点の数は 65535 以下です (それ以上にすることはできません)。

Answer 1

デュアル グラフ (各三角形のノード、隣接する三角形のアーク) はツリーです。このツリーをたどって、各ノードによって決定されるサブツリーに含まれるノードの数を追跡できます。ノードの次数は最大で 3 であるため、3 分の 2 の目標を達成できるはずです。