Эффективный алгоритм поиска 3D-координат в массиве

Question

У меня есть большой массив (> 10 ^ 5 записей) трехмерных координат r = (x, y, z), где x, y и z являются числами с плавающей точкой.Какой самый эффективный способ поиска заданной координаты r 'в массиве и дать индекс массива.Обратите внимание, что r 'может быть задано не с той же точностью, что и r;скажем, если массив сохранил координаты (1.5, 0.5, 0.0) и r 'задано как (1.49999, 0.49999, 0.0), алгоритм должен правильно выбрать координату.Я разрабатываю код на языке C.

Как можно использовать O (1) возможность поиска для хеш-таблицы для этой цели?Преобразование координаты в строку исключено из-за проблем, связанных с точностью.Есть ли какая-то конкретная структура данных, которая бы помогла в алгоритме O (1)?

Спасибо

OnRoadCoder

Answer 1

Чтобы «нечеткий» поиск соответствовал описанию (чтобы вы могли поддерживать небольшие неточности), вам придется пожертвовать алгоритмами O (1).

При этом есть несколько очень хороших алгоритмов для этого. Разделение пространства (например, использование Octree или KD-Tree ) является распространенным и популярным вариантом.

Answer 2

check R-деревья , уже реализованные в некоторых СУБД, таких как SQLite, и (я думаю) Postgres

Answer 3

То, что вы спрашиваете, звучит как Поиск ближайшего соседа .Один из подходов может состоять в том, чтобы кодировать kd-дерево (или любой метод, основанный на разделении пространства) и использовать его для нахождения ближайшей точки к вашему запросу.Но вы также можете использовать подход, основанный на hash , который в основном делает то, что описывает ответ Ipthnc, но старается избежать плохой производительности для вырожденных случаев.

Answer 4

Если диапазон значений ограничен, выберите желаемую точность. Теперь ключ (1,2,3) будет указывать на связанный список (или более интересную структуру данных) всех точек, которые находятся в пределах Манхэттена. Расстояние 3 * d (d = 0,5? - зависит от деталей) из (1, 2,3). Вы лучше знаете свое приложение, поэтому можете лучше выбирать d. Подход к оптимизации будет зависеть от того, как распределяются данные.

EDIT:

Слабость здесь в том, что если у вас есть много точек, сосредоточенных в одном кубе, то мало что можно сделать, используя хеш-таблицу для гарантии O (1) ... больше как O (n):)

Какая-то древовидная структура данных может гарантировать O (log n).