平面点集合 P があります。P のどの点 p が境界 B(p) に属するかは既にわかっています。前記境界は、凸状または非凸状であり得る。ここで、境界 B(p) を持つ P の三角形分割を見つけたいと思います。私の質問:
これを直接達成するアルゴリズムはありますか? 近い候補は、制約付きドローネ三角形分割 (CDT) です。ただし、ここでは CDT は適用されないと思います。すべてのエッジが三角形分割に含まれるように、B(p) のすべてのエッジを制約として供給することができます。ただし、必ずしもこれが三角測量の境界になるとは限りません。ここで間違っている場合は修正してください。
そのようなアルゴリズムの場合は、実装を提供する (軽量) C ライブラリを教えてもらえますか?
あるいは、もちろん、GTS の標準的な Delaunay 三角形分割を使用して P を三角形分割することもできます。次に、頂点が B(p) の外側にあるすべての面を切り取る必要があります。これはGTSで可能ですか？