複雑なポリゴン（おそらく凹面）があり、そのエッジのいくつかが入口/出口ポイントとしてマークされています。このポリゴンの内部に、任意の形状の1つまたは複数の封鎖が存在する可能性があります。入口/出口エッジのペアの間に特定の幅のパスが存在するかどうかを判断するために、どのようなアプローチを使用できますか？
質問を読んだら、宿題のタイプのように見えますが、そうではありません。これは私にとって新しいことなので、私が追求できる少なくともいくつかのリードが欲しいだけです。
2 に答える
1
Motion Planningをご覧ください。そこには豊富な情報があります。
于 2010-05-05T21:05:59.347 に答える
0
ルートに幅が必要かどうかによって異なります。移動する必要のあるオブジェクトのサイズが有限である場合は、ドメインポリゴンと移動するオブジェクトのポリゴンのミンコフスキー差をとる必要があります。次に、それを経由してルーティングを試みます。
パスを正確に計算する1つの方法は、ポリゴンの可視グラフを計算することです。可視性グラフには、ドメインポリゴンの頂点に対応する頂点があり（障害物がある場所に穴がある可能性があります）、2つの頂点は、互いに「見える」場合はエッジで接続されます。入口と出口を結合するエッジのセットが存在する場合、形状は合格です。最短経路などを計算することもできます。単純な方法で可視グラフを計算することは難しいことではありませんが、遅いです。それを行うための非常に高度なアルゴリズムがありますが、それら（AFAIK）は実装されていません。数年前に実装を試みましたが、結果は平凡でした。それらのほとんどは、正確な算術を使用して一般的な位置に頂点を想定していますが、実際のアプリケーションでは浮動小数点数を使用します。
于 2010-05-05T21:23:20.523 に答える