Поиск диапазона в пределах указанного радиуса в октрее

Question

Меня интересуют алгоритмы частиц, такие как N-Body и SPH. Одним из важных шагов в этих приложениях, учитывая точку запроса, чтобы найти частицы лежащий в пределах указанной сферы радиуса 'h'.

Теперь я слышал, что Octrees - это хорошая структура пространственных данных для таких задач, как N-body или SPH.

Но после построения октодерева я не могу понять, как выполняется шаг «найти частицы в радиусе». Может кто-нибудь указать мне какие-либо ссылки, статьи или статьи для выполнения этого шага?

Answer 1

Предполагая, что Octree содержит объекты 3dPoint: «найти частицы в радиусе 3 от точки p» можно выразить как «Вернуть все точки, содержащиеся в Octreecells, соприкасающиеся или пересекающиеся со сферой (центр p, радиус r)» Чтобы проверить, является ли ячейкапересекает сферу:

dx,dy,dz = 0;
if (pX < minX of Cell)
    dx = |px - minX|
else if (px > maxX of Cell)
    dx = |px-maxX|
Same for other dimensions

return (|dx,dy,dz|<=r)

Answer 2

k-d деревья также являются хорошими структурами данных для использования и обычно используются для поиска ближайших соседей.