Самый быстрый способ получить похожие значения в словаре C#

Question

У меня есть пространственный хэш-класс в C# для обнаружения 3D-данных. Каждая позиция вершин имеет пространственный хеш и Vector3, хранящийся в Dictionary<float, Vector3>, где поплавок является фактическим пространственным хешем, который я вычислил. То, как я понимаю пространственные хэши, состоит в том, что вы сортируете хэши в ведрах, а затем получаете значения, находящиеся в пороге (скажем, 0,0001f) друг от друга. В большинстве исследований, которые я провел, была реализована сортировка ковша, и я не могу понять, как реализовать ее с помощью Dictionary.

Итак, мой вопрос: как мне подойти к получению подобных значений в словаре, как это? До сих пор мне кажется, что мне нужно сортировать значения хеша в ведрах с размером threshold и каким-то образом поддерживать ссылку на Vector3. Подхожу ли я совсем по-другому? Есть, скажем, другой родовой, который лучше подходит для этого конкретного случая использования?

Answer 1

реализовать интерфейс

IEqualityComparer<float> 

для обработки нечеткого соответствия и передать его в конструктор словаря

http://msdn.microsoft.com/en-us/library/ms132151.aspx http://msdn.microsoft.com/en-us/library/ms132072.aspx

Answer 2

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

Итак, выбор за вами:

Perfect Hashing

или

Smartly used 'Close-Enough' functions (взят из исходного кода OpenGL SuperBible, пожалуйста, смотрите на 'm3dCloseEnough')

Answer 3

Dictionary класс не разрешить коллизии ключей, поэтому, если вы хотите, чтобы несколько векторов были связаны с одним и тем же пространственным хешем (т. е. они хранятся в одном и том же ведре), вам необходимо сохранить списки векторов а не отдельных лиц. По существу, вы храните свои ведра в словаре:

Dictionary<float, List<Vector3>> Buckets; 

Далее, вам необходимо убедиться, что ваша пространственная хэш-функция возвращает то же значениедля каждого элемента, который должен быть в том же ведре. Имея это в виду, вам может быть лучше использовать целое число как ваш пространственный хеш.

Наконец, для того, чтобы получить аналогичные предметы из словаря, вы будете должны использовать следующие шаги:

1. Определить рамку для получения аналогичных элементов (например,< Х-дельта, Y-дельта, Z-дельта >, < Х + дельта, Y + дельта, Z + дельта >)
2. Итерация по всем ковшей, которые потенциально пересекаются с ограничивающей рамки
   1. Для каждого пересекающихся ковш, вычислить пространственный хэш для точки внутри ковша и использовать словарь, чтобы получить список элементов в ведре
   2. Добавление элементов из ведра в список результатов

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

Answer 4

Для того, чтобы работать с Dictionary, каждому элементу должен быть назначен ведро, так что каждый элемент может быть вслепую не эквивалентен любому элементу, находящемуся в другом ковше. Таким образом, невозможно использовать Dictionary непосредственно для поиска объектов, находящихся рядом с данной точкой, поскольку такие объекты могут попадать в более чем один ковш.

Если вы хотите, чтобы у всех объектов, которые строго меньше половины единицы от данной точки, я хотел бы предложить вам назначить комбинации кодов целочисленных координат, а затем поместить каждую точку в каждую из (обычно восемь) ведер, координаты которых представляют либо следующее большее, либо следующее меньшее целое число по сравнению с рассматриваемой точкой. Чтобы найти, содержит ли сборник точку, которая строго меньше половины единицы от данной точки, загляните в ведро для ближайшей точки.

В зависимости от плотности указанных точек может оказаться полезным использовать более грубую сетку, и в этом случае многие объекты должны храниться только в одном ведре. Ключевым требованием является то, что каждая точка должна храниться в каждом ведре, который может быть «ближайшим» к любой точке, в которой он должен совпадать.