查找包含點的地圖區域

Question

我有一個區域被分割成一堆稱爲塊的子區域。我有一個圖形編碼如下：每個塊都有一個節點，而（i，j）是一個邊緣，如果塊i和j接觸。我有一個（很長很長的）點列表，對於每個點我想查找包含該點的塊。有沒有更快的算法，而不是在圖上選擇一個隨機頂點和A *在歐幾里得距離上搜索？

Answer 1

1. 從隨機塊開始。
2. 確定塊是否包含點。
3. 確定鄰居塊的位置（通過邊緣有鄰居）具有到目標的最短距離。
4. 移至該塊。
5. 重複步驟2-4，直到步驟「2」爲真。

請注意，如果您跟蹤來自的塊，則無需在步驟「3」測試此塊。