連続マップ（ポリゴンなど）のパスファインディングアルゴリズム
多角形の障害物がある平面内の2点間の短いパスのさまざまなアルゴリズムを調査しようとしています。私が見つけたアルゴリズムの大部分は、離散マップ（グリッドマップ、可視グラフ、ボロノイロードマップなど）を使用しています。一部の本（Ben-Ariによる「Elementsof Robotics」、NikolausCorrellによる「IntroductiontoAutonomous Robots」など）では、連続マップ（生のポリゴンデータなど）について言及していますが、対応するアルゴリズムについては説明していません。彼らは、いくつかの単純な障害物に対してメモリまたは効率の利点を主張します。これは私にとって非常に興味深いものです。
幾何学的計算（交差点検出など）といくつかのアルゴリズムパラダイム（最小コストの分枝限定法など）を使用した巧妙なアプローチが必要だと思いますが、車輪の再発明を不十分にしたくはありません。
連続マップまたは検索に役立つキーワードを使用するいくつかの短い（最短）パスアルゴリズムのリソースはありますか？
提案されたように、私は使用した用語のいくつかを指定しようとします：
連続マップ（図を参照）は、幾何学的形状の（連続）実数値の保存を指します。障害物/三角形Iは、A =（3,2）、B =（7,5）、C =（7,2）として格納されます。
離散マップ（図を参照）は、チャンクへの細分割（離散化、たとえばグリッドマップのように）を指します。障害物/三角形I.はセルインデックスとして保存されます：（3,2）、（4,2）、（5,2）、（6,2）、（5,3）、（6,3）、（ 6,4）離散マップでのパスファインディングは、多くの場合、ダイクストラやA *などのグラフベースのアルゴリズムによって実行されます。
幾何学計算は、連続マップのパスファインディングアルゴリズムで期待する計算幾何学の操作に使用する漠然とした用語です。（例：平行移動、垂直距離、交差検出）
回答
あなたがそれを呼んだ「連続マップ」のために、あなたのすべての頂点でダイクストラを使うだけです。唯一の違いは、ノード間の距離を計算するときにクリッピングをチェックする必要があることです。
私の問題を表すもう1つの、より頻繁に使用される用語は、ユークリッド最短経路のようです。連続マップと離散マップのアルゴリズムの違いは、私には少しあいまいなようです。
ただし、連続マップのアルゴリズムに最も近いものは、連続ダイクストラ問題のミッチェルのアルゴリズム（または連続ダイクストラ法）です。このアルゴリズムは、開始点から均等に広がるウェーブレットを使用します。ウェーブレットの「回折」によって、直接到達できない領域に到達します。これにより、連続配置空間内の任意のポイントへのユークリッド最短経路を特定するために使用できる最短経路マップが作成されます。
詳細については、以下を参照してください。
- F.LiとR.Kletteによる「ユークリッド最短経路の正確または近似アルゴリズム」
- IvanChenによる素晴らしいが少しバグのあるアニメーション
- アントンコブシャロフによるアプリケーション
作成された最短経路マップは、連続構成空間の単なる別の離散化であると主張する人もいるかもしれません。ただし、最短経路マップは、アルゴリズムを構成空間全体に適用した場合に得られる結果にすぎないと思います。2つのポイント間の最短パスだけが必要な場合は、ターゲットポイントに到達した後にアルゴリズムを停止できます。これらのアルゴリズムの分類についてはまだわかりませんが、これで私の質問に答えられるはずです。