Как лучше всего подойти к этой проблеме, зависит от нескольких факторов, которые вы не описали:
- Будет ли такое же расположение гиперсфер использоваться для многих расчетов столкновений частиц?
- Гиперсферы одинакового размера?
- Что такое движение частицы (например, прямая линия / кривая) и влияют ли на это движение сферы?
- Считаете ли вы, что частица имеет нулевой объем?
Я предполагаю, что частица не имеет простого движения по прямой линии, поскольку это было бы относительно быстрым расчетом нахождения ближайшей точки между линией и точкой, которая, вероятно, будет примерно такой же скорости, что и нахождение того, какая из прямоугольники, с которыми пересекается линия (чтобы определить, где в n-дереве исследовать).
Если ваши положения в гиперсфере фиксированы для большого количества столкновений частиц, тогда вычисление разложения вороной / тесселяции Дирихле даст вам быстрый способ позже найти точно, какая сфера ближе всего к вашей частице для любой данной точки в космосе.
Однако, чтобы ответить на ваш первоначальный вопрос о octrees / quadtrees / 2 ^ n-деревьях, в n измерениях вы начинаете с (гипер) -куба, который содержит интересующую вас область пространства. Он будет разделен на 2 ^ n гиперкубов, если вы считаете содержимое слишком сложным. Это продолжается рекурсивно до тех пор, пока в узлах листа не останутся только простые элементы (например, один гиперсферный центроид).
Теперь, когда n-дерево построено, вы используете его для обнаружения столкновений, беря путь вашей частицы и пересекая его с внешним гиперкубом. Положение пересечения скажет вам, какой гиперкуб на следующем уровне вниз по дереву следует посетить следующим, и вы определите позицию пересечения со всеми 2 ^ n гиперкубами на этом уровне, следуя вниз, пока не достигнете листового узла. Как только вы достигнете листа, вы можете исследовать взаимодействие между вашим путем частиц и гиперсферой, хранящейся на этом листе. Если у вас есть столкновение, которое вы закончили, в противном случае вы должны найти точку выхода пути частицы из текущего листа гиперкуба и определить, к какому гиперкубу он перемещается в следующий. Продолжайте, пока не найдете столкновение или не покинете весь ограничивающий гиперкуб.
Эффективное нахождение соседнего гиперкуба при выходе из гиперкуба является одной из самых сложных частей этого подхода. Для 2 ^ n деревьев подходы Самета {1, 2} могут быть адаптированы. Для kd-деревьев (бинарных деревьев) подход предлагается в разделе {3} 4.3.3.
Эффективная реализация может быть такой же простой, как сохранение списка из 8 указателей от каждого гиперкуба на его дочерние гиперкубы и специальная маркировка гиперкуба, если это лист (например, сделать все указатели NULL).
Описание разделения пространства для создания дерева квадрантов (которое можно обобщить для n-дерева) можно найти в Klinger & Dyer {4}
Поскольку другие упоминали, что kd-деревья могут быть более подходящими, чем 2 ^ n-деревья, поскольку расширение произвольного числа измерений является более простым, однако они приведут к более глубокому дереву. Также легче адаптировать позиции разделения в соответствии с геометрией вашего
гиперсферы с кд-деревом. Приведенное выше описание обнаружения столкновений в дереве 2 ^ n в равной степени применимо к дереву kd.
{1} Маркировка подключенных компонентов, Ханан Самет, Использование журнала Quadtrees в журнале ACM, том 28, выпуск 3 (июль 1981 года)
{2} Обнаружение соседей в изображениях, представленных октреями, Ханан Самет, том компьютерного зрения, графики и обработки изображений, том 46, выпуск 3 (июнь 1989 года)
{3} Выпуклая генерация корпуса, маркировка подключенных компонентов и минимальное расстояние
расчет для теоретически заданных моделей, Дэн Пидкок, 2000
{4} Эксперименты по представлению изображений с использованием регулярного разложения, Klinger, A. и Dyer, C.R. E, Comptr. Графика и обработка изображений 5 (1976), 68-105.