私はブロックと呼ばれる小領域の束に分割されます領域を有するポイント

Question

を含むマップの地域を検索します。各ブロックは、ノードが与えられ、そして（i、j）はブロックIFFエッジi及びjタッチである：私は次のようにエンコードされていますグラフを持っています。私は（長い、長い）ポイントのリストを持ち、各ポイントについて、そのポイントを含むブロックを探したい。グラフ上にランダムな頂点を選び、ユークリッド距離を探索するよりも速いアルゴリズムがありますか？ランダムブロックと

Answer 1

1. スタート。
2. ブロックはポイントが含まれているかどうかを確認します。
3. 隣接するブロック（エッジを介して隣接しているもの）がターゲットまでの最短距離を決定します。
4. そのブロックに移動します。
5. ステップ2が真になるまで、ステップ2〜4を繰り返します。

あなたが来たブロックを追跡する場合、ステップ3でこのブロックをテストする必要はありません。