3

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

このエリアには、移動してはならない障害物があります。

接続された凸多角形の数が可能な限り少ないグラフに、障害物があるより大きな領域を分割できるアルゴリズムがあるのだろうか?

4

1 に答える 1

1

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

于 2016-08-17T07:24:51.207 に答える