最も近いポイント アルゴリズムのペアなどのアルゴリズムを探しています
すべてのポイント間の任意の距離の代わりに、4 つのポイントがそれぞれ右上、右下、左上、左下になるようにグリッド システムを設定しました。これにより、すべてのポイント間の距離が一定に保たれます。
たとえば、このグリッドに外側のポイントを配置する場合、最も近い 4 つのポイント (グリッド スクエアの終点が得られる) を見つけることによって、それがどのグリッド スクエアにあるかを見つける必要があります。
最も近いポイントのアルゴリズムを実装するつもりでしたが、ポイントは常に互いに同じ距離にあるため、これが別のより効率的なアルゴリズムに値するかどうかはわかりませんでした.
答えの詳細な説明は本当に必要ありません。正しい方向へのポイントだけです。
これは2次元だと思いますか？非常に簡単に言えば、これを行うことができます。同様の手法を使用して、大規模なデータ マイニング プロジェクトで空間クラスタリングをすばやく最適化しました。
座標空間を X 方向と Y 方向の固定数のグリッド線に分割します (これらの 4 点を等間隔にすることで、既に行っているようです)。
ポイントを挿入するときは、原点から X および Y 方向の距離 (整数除算) をグリッド ステップ間隔で割ります。次に、最も近い X/Y グリッド交点を識別する 2 つの座標が残ります。残りを使用して、ポイントが属するグリッド交差点の側を確立します。
本当に複雑にしたい場合は、kD-Trees などを使い始めることができます...しかし、この例は、これ以上複雑な空間分割を保証するほど単純ではないと思います。