ポイントのセットが与えられた場合、内のすべてのポイントから可能な限り離れた の領域を境界付けるp空間内のポイントを見つけたいと思います。bpp
これは、 Craig Reynolds の Boidsによる群れシミュレーションでの近隣回避の実装に関するものです。これが近隣を回避する最善の方法でない場合は、提案をお待ちしています。
編集: 言い換えれば、p周囲の境界ボックス内に留まりながら、他のポイントからできるだけ離れた任意のポイントを見つけたいと思いますp。
バウンディング ボックスとは、解が上端と下端の間にある y 座標と、左端と右端の間にある x 座標を持つ点であることを意味します。
質問をより抽象的に言えば、私はこのアルゴリズムをM、最も近い隣のユニットの範囲内にとどまり、それらのユニットよりも近づかないようにしたいエージェントのターゲットを見つける方法として見ていmます。このアルゴリズムによって返される解は、その点とその最も近い隣接点との間の距離が最大になる点を返す必要があります。
これは 2D 平面にあります。
解決策は、(他の) エージェントのボロノイ図の交点の 1 つにある必要があるようです。したがって、アルゴリズムによる解決策は、ボロノイ図を作成し、交点を反復して、隣接点までの最短距離が最大のものを選択することです。
最も遠い点は、ボックスの境界上にあるか、最も近い 2 つの点の間で等距離にある必要があると思います。そうでない場合は、少しずらして、2 つのポイントの近くから遠ざけることができるはずです。これにより、図の線上に配置されます。その線に沿った方向の 1 つは、両方のポイントからさらに移動するため、その線が別のポイントで結合するまで移動できます。したがって、私はそれが境界上にあるか、http://en.wikipedia.org/wiki/Voronoi_diagramの交差点の 1 つにあると予想します. ボロノイ図の線が境界と交差する境界の角と、ボロノイ図の交点をチェックして、最も遠い点を見つけることができます。このようにしない場合でも、ボロノイ図が別のアプローチの最近傍を見つける方法として役立つ場合があります。さまざまな分枝と境界が機能する可能性があります。