Kd Tree против отсортированных кодов Мортона
В настоящее время я программирую систему частиц OpenGL 2d, но я столкнулся с более общей проблемой программирования, с которой мне нужна помощь.
По сути, мне нужен способ найти, могут ли частицы сталкиваться, т.е. обнаружение широкого фазового столкновения.
Я много читал об использовании кодов Мортона и деревьев kd для пространственного разбиения, чтобы отбирать множество точек, которые не нужно проверять на столкновение. Однако мне кажется, что kd-деревья полезны только при поиске ближайшего соседа. Вместо этого я хочу, чтобы все соседи были в радиусе. Основная проблема заключается в том, что я хотел бы сделать это для каждой точки.
Итак, мой вопрос: есть ли преимущество в создании дерева kd с использованием моих кодов Мортона, или будет достаточно отсортированного списка кодов Мортона? Теоретически, если у меня есть массив отсортированных кодов Мортона, которые соответствуют идентификаторам отсортированных частиц, могу ли я просто посмотреть в массиве Мортона элементы, окружающие мою текущую частицу, и проверить расстояние? Я полагаю, что буду продолжать делать это, пока расстояние не станет больше моего определенного радиуса.
Имеет ли это смысл? Или я должен выбрать какой-то тип древовидной структуры?