平鋪地圖

數據結構，我想打一個無限拼接地圖，從(-max_int,-max_int)直到(max_int,max_int)，所以我會做一個基本結構：chunk，每個chunk包含char tiles[w][h]並且還int x, y座標，因此，例如h=w=10所以tile(15,5)在chunk(1,0)上(5,5) coordinate，並tile(-25,-17)是chunk(-3,-2)上(5,3)等。現在可以有任何數量的塊，我需要將它們存儲起來，並且在O(logn)或更好的情況下（O(1)如果可能的話，但它不是..）很容易訪問它們。應該很容易：添加，刪除（不必）和查找。那麼我應該使用什麼數據結構？平鋪地圖

來源

2011-08-27 Vladp

這很難遵循。也許你可以提供一個結構/類和一個公式來轉換塊，以瓷磚協調。 – 2011-08-27 18:41:49

它只是一堆用X對象，y座標（塊），現在我需要存儲它們方便地訪問他們 – Vladp

讀入KD樹或四叉樹（八叉樹的2D變體）。這兩方面都可能是一個很大的幫助。

來源

2011-08-27 18:34:38 Mranz

四叉樹 - 應該是一個常量的大小廣場......不適合。 kd-tree - 如果我只有10個塊，並且全都具有相同的x ??，該怎麼辦？ – Vladp

取決於你構建算法kd樹，但常見的是分裂的最大尺寸，所以在所有箱子是在同一x平面的情況下，你總是劈在Y，這應該仍然保持你的訪問時間低。換句話說，如果你不強迫kd-tree旋轉分裂平面並保持適應性，這就是它試圖解決的確切問題。 – Mranz

如果全部彼此靠近，那麼有沒有更好的解決方案？ – Vladp

所以所有的空間splited成塊（矩形集羣）。通常問題是將數據存儲爲稀疏（由於已經實現了集羣）矩陣。爲什麼不使用兩級字典式的容器？ rb-tree by row index其中value是按列索引的rb-tree。或者如果你很幸運，你可以使用散列來獲得你的O（1）。在這兩種情況下，如果找不到行，則將其分配到容器中，然後創建新容器作爲值，但最初僅使用單個塊。當然，在現有的行上分配新的塊會比新的更快，我想這是這種方法唯一的問題。

來源

2011-08-27 19:13:29 ony

這會工作，但內存成本可能很大。對於這些類型的問題，它們是更好的空間數據結構。 – Mranz

回答

相關問題