algorithm - 三角測量を効果的にカットします（サブ三角測量を見つけます）

Question

現在、地形レンダリングツールに取り組んでいます。与えられたドロネー三角形分割からピースを切り取らなければなりません。次の三角形分割が与えられていると仮定します。

赤い四角は、元の三角測量から切り取る領域を示しています。つまり、元の三角測量と同じ点に加えて、正方形の境界上の点を持つサブ三角測量を見つけます。

そのようなカットを実行するための効率的なアルゴリズムはありますか？

Answer 1

制約付き Delaunay triangulationを使用する必要があります。

たとえば、CGAL ライブラリは C++ での実装を提供します。地形について話すときは、この例も見てください。

Java または Python の実装に興味がある場合は、SWIG で記述されたバインディングがここから入手できます。