algorithm - 障害物の部屋を三角測量する方法は?

Question

多角形の障害物でいっぱいの部屋を三角測量したいと思います。

現時点で他の機能をテストしているので、実装するのが簡単なアルゴリズムを特に探しています。効率 (1 分以内に数十の頂点を処理できる場合) と三角形の「品質」は考慮されません。今、私の考えは、各頂点をループして、以前に作成された接続を交差せずに接続できる他の頂点をチェックすることです。このアプローチには、より簡単な解決策や欠陥がありますか?

ありがとう

Answer 1

すべての頂点を三角形分割してから、アルファ シェイプに似た最長のエッジを削除できます。私のホームページhttp://www.phpdevpad.de/geofenceで例を探すことができます。

Answer 2

簡単な解決策の 1 つは、制約付き三角形分割を使用して、すべてのポリゴン エッジを制約として追加することです。次に、部屋の外から始まるドメインをマークするだけです。

C++ の実装を探している場合は、CGAL ライブラリを参照してください。特に、必要な処理を行っているこの例を参照してください。