Разделение точек на субрегионы с использованием хэш-карт

Question

У меня есть 2D-растр, скажем, 200 пикселей x 200 пикселей. Я хочу разделить его на 400 «сегментов» каждых 10x10 пикселей.

Затем у меня есть список точек (около 200 КБ), которые я хочу отобразитьв вышеупомянутой структуре.Поэтому, если точка попадает в область 10х10, добавьте ее в корзину.

Теперь мне кажется, что хеш-таблица могла бы хорошо с этим справиться.Мне было интересно, возможно ли это с помощью STL?

Я пытался использовать stl :: unordered_map и указывать количество сегментов, но это не работает, он «игнорирует» этот запрос.(Из-за слишком большого количества элементов, которые отображаются в одной области, я полагаю, но в моем случае это не проблема, наоборот, в этом весь смысл).

Есть ли способ сделать это с помощьюSTL?

Answer 1

Я думаю, что вы путаете две части терминологии. В смысле хеш-таблиц есть «сегменты», которые представляют собой некоторые внутренние детали реализации, используемые для равномерного распределения элементов, чтобы при поиске не сканировалось слишком много бесполезных элементов. Существуют также «сегменты» в пространственном смысле, которые представляют собой разбиение пространства на области, так что элементы принадлежат ровно одному сегменту. Как правило, вы сами контролируете пространственную систему группирования (вы можете выбрать, где все разделено), но хеш-таблица не позволит вам точно контролировать сегменты. Вы можете выбрать начальный размер, но если хеш-таблица считает целесообразным увеличить этот размер с целью повышения производительности, она почти наверняка сделает это. Если этого не произойдет, время поиска будет значительно хуже.

Если вы хотите разбить пространство на сетку, а затем распределить точки в этой сетке, лучший способ сделать это - создать двумерный массив (с необработанными массивами или с использованием некоторой линеаризации сетки), равный std::unordered_map с. каждая из которых просто содержит точки в одной определенной области пространства. Таким образом, если вы хотите найти элемент, вы идете на карту, содержащую точки только для этого сегмента, а затем попросите карту найти значение, после чего она обращается к своей собственной внутренней системе группирования, чтобы найти точку, которую вы хотите найти. хочу. Это означает, что если вы хотите разделить точки так, чтобы вы могли выполнять интересные запросы по областям пространства, точки хранятся в сегментах, специально предназначенных для этих областей, но внутри этих сегментов они хранятся в хеш-таблице для создания поиск этих точек занимает меньше времени.

В качестве альтернативы вы можете рассмотреть возможность использования структуры пространственных данных, таких как дерево квадрантов или дерево kd, которые эффективно хранят элементы и позволяют эффективно запрашивать каждую точку в пространственном сегменте.

Надеюсь, это поможет!

Answer 2

То, что вы действительно хотите, это не «ведро», а карты. Вы хотите что-то вроде карт карт

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)

Тад. Это то, что вы ищете ...

Answer 3

Вы можете создать хеш-код для сегментов, например:

[старшие 4 байта - x] [младшие 4 байта - y]

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

map[hash].push_back(hash);