Непрерывная модификация набора точек - найти всех ближайших соседей

Question

У меня есть 3D набор очков. Эти точки будут подвергаться серии крошечных возмущений (все точки будут возмущены одновременно). Пример: если у меня есть 100 точек в блоке, каждая точка может быть перемещена вверх, но не более 0,2% ширины блока в каждой итерации моей программы.

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

Это должно использовать очень быструю структуру данных; Я оптимизирую это для скорости. Это несколько сложная проблема, потому что я изменяю все точки одновременно. Приближенные алгоритмы NN не подходят для этой задачи.

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

Спасибо

Answer 1

Вы можете попробовать кривую quadkey или monster. Это уменьшает размер и заполняет плоскость. Microsoft Bing Maps Quadkey - хорошее начало для изучения.