大きな領域を凸多角形に分割するアルゴリズム

Question

グリッドベースのエンジンにA *経路探索アルゴリズムを実装していますが、グリッド点を使用するのではなく、多角形領域にノードを作成したいと考えています。

このエリアには障害物があり、移動しないでください。

可能な限り小さな数の接続された凸多角形を持つグラフに、障害物のある大きな領域を分割するアルゴリズムがあるのでしょうか？

Answer 1

多くのものがあります。通常は、三角形分割アルゴリズムを扱っています。あなたは障害物を通過する線を取り除き、その上で最短経路アルゴリズムを実行します。私は接続された凸多角形の最小の数をなぜ必要としているのかは分かりませんが、それは同じように行うことができます。答えは単に点の凸包です。 1つのポリゴンは、定義上、そこでの最小の数です。