Хорошая структура данных для евклидовых 3-х запросов данных?
Что хороший путь состоит в том, чтобы хранить данные облака точек так, чтобы это было оптимально для приложения, которое сделает один из этих двух запросов?
- Ближайший (т.е. самое низкое евклидово расстояние) точка данных к (x, y, z)
- Поймите все мысли в сфере с радиусом R вокруг точки (x, y, z)
Структура только будет заполнена однажды, но много раз читать. lowish объем потребляемой памяти был бы хорош, поскольку я могу иметь дело с наборами данных> 7 миллионов точек, но скорость должна вызвать первоочередное беспокойство. Библиотека была бы хороша, но я не буду возражать реализовывать ее сам, если это будет что-то выполнимое с ограниченными экспертными знаниями в области.
Заранее спасибо!
2 ответа
A Kd-Tree вы получите O (log ( n )) ближайшего соседа, и обычно диапазон запросы будут быстрыми.
Там есть ссылки на множество библиотек. Я не использовал ни одного из них.
Вы также можете посмотреть CGAL . Я использовал CGAL для других целей, он довольно быстрый, чрезвычайно всеобъемлющий, но документация заставит вас выпить.
Огромная часть решений в структурах данных будет зависеть от пространственной организации данных. Например, сильно кластеризованные данные имеют тенденцию иметь другие характеристики производительности в kd-деревьях, чем равномерно распределенные данные.
KD-деревья очень хорошо подходят для обоих этих запросов.
Octree также может быть хорошим вариантом во многих случаях, и его потенциально проще реализовать.
Существует множество библиотек, которые делают это, используя различные алгоритмы. Поиск по k-nearest neighbor search покажет много полезных библиотек. Например, мне очень повезло с ANN.