使用hashmaps將點劃分爲子區域

我有一個200像素x 200像素的2D光柵我想將它細分爲每個10x10像素的400個「存儲桶」。使用hashmaps將點劃分爲子區域

然後我有一個要在上述結構中映射的點（約200k）的列表。所以如果這個點落入10x10區域，將它添加到桶中。

現在看來我認爲哈希表可以做得很好。我想知道這是否可以使用STL？

我試過使用stl :: unordered_map並指定了桶的數量，但這不起作用，它'忽略'該請求。（因爲太多的項目被映射到同一區域，我認爲，但在我的情況下，這不是一個問題，相反，這是整個問題）。

是否有任何方式與STL做到這一點？

2011-08-27 KWyckmans

所以你想劃分成400塊的畫布，並希望跟蹤他們單獨。每個塊可以包含該塊範圍內的點。對不對？ –

我認爲你混淆了兩個術語。哈希表中有「桶」，它們是用於均勻分配元素的內部實現細節，以便查找不會掃描太多無用的元素。在空間意義上也有「桶」，它們將空間劃分爲區域，從而使元素恰好屬於一個桶。通常情況下，你可以自己控制空間分區系統（你可以選擇所有分區），但是哈希表不會讓你非常精確地控制分區。您可能會選擇初始大小，但如果哈希表認爲增加該大小以提高性能是個不錯的主意，那麼它幾乎肯定會這樣做。如果沒有，查找時間會大大變差。

如果要將空間分割成網格，然後將點分散到該網格中，最好的方法是創建std::unordered_map的二維數組（使用原始數組或線性化）它們中的每一個都只在一個特定的空間區域中存在點。那樣的話，如果你想查找一個元素，你可以到地圖上爲這個地方存儲點，然後讓地圖查找這個值，然後查看它自己的內部分區系統，找到你的點想。這意味着如果你想分割點，這樣你就可以對空間區域進行有趣的查詢，點被存儲在特定專用於這些區域的桶中，但是在這些桶中它們被存儲在哈希表中以使查找這些點需要更少的時間。

或者，您可能需要考慮使用空間數據結構，如四叉樹或kd-tree，它們可以高效地存儲元素，並讓您高效地查詢空間存儲桶中的每個點。

希望這會有所幫助！

來源

2011-08-27 01:29:18 templatetypedef

有時，最大的挑戰是理解他們「需要」什麼，而不是混淆他們「想要」。很好的理解和小暗示。 :) –

與所有空間數據結構一樣，使用正確結構的真正問題歸結爲結構的預期用法。在日誌（n）點搜索或最近鄰居的自適應存儲中，kd-tree的性能令人驚歎。在渲染領域，它們很受RayTracers的歡迎。在物理領域，它們有時用於修剪基元以進行碰撞檢測。正如我在下面回答的，對於基於整數的點，您可以爲點創建哈希方案並使用哈希表進行存儲，但正如在此答案中所述，可能不是最好的方法。 – Mranz

你是對的。我輸入這個有點太累了，有點太晚了。當我今天早上想到它時，我意識到我的錯誤:)。 – KWyckmans

您可以創建像水桶的哈希碼：

[前4個字節是X] [下4個字節是Y]

size_t hash = (p.X/10) << 16 | (p.Y/10); 

map[hash].push_back(hash);

來源

2011-08-27 01:30:00 Mranz

你真正想要的是不是「鬥」，但地圖。你想要類似地圖的地圖

typedef pair<int,int> P 
typedef set<P> PS 
typedef map<P,PS> PSM // say the point at right edgexbottomedge defines the BLOCK you want. 
PSM psm(400)

田田。這就是你正在尋找...

來源

2011-08-27 01:32:30

使用hashmaps將點劃分爲子區域

回答

相關問題