Структуры пространственных данных в C

Квадратное дерево - это двумерное дерево, в котором на каждом уровне узел имеет 4 дочерних элемента, каждый из которых покрывает 1/4 площади родительского узла.

Дерево Oct - это трехмерное дерево, в котором на каждом уровне узел имеет 8 дочерних узлов, каждый из которых содержит 1/8 объема родительского узла. Вот картинка, которая поможет вам это визуализировать: http://en.wikipedia.org/wiki/Octree

Если вы выполняете N-мерные тесты на пересечение, вы можете обобщить это на N-дерево.

Алгоритмы пересечения работают, начиная с вершины дерева и рекурсивно переходя к любым дочерним узлам, которые пересекают тестируемый объект, в какой-то момент вы попадаете на листовые узлы, которые содержат фактические объекты.

Похоже, вы хотите реализовать kd-дерево, который позволит вам более быстро искать в N-мерном пространстве. Дополнительная информация и ссылки на реализации на Репозиторий алгоритмов Стоуни-Брук.

Поскольку ваше поле статично (я предполагаю, что вы имеете в виду, что гиперсферы не двигаются), то самым быстрым решением, которое я знаю, является Kdtree.
Вы можете сделать свой собственный или использовать чужой, например: http://libkdtree.alioth.debian.org/

Как лучше всего подойти к этому для вашей проблемы, зависит от нескольких факторов, которые вы не описали: - Будет ли такое же расположение гиперсферы использоваться для многих расчетов столкновений частиц? - Гиперсферы одинакового размера? - Что такое движение частицы (например, прямая линия / кривая) и влияют ли на это движение сферы? - Считаете ли вы, что частица имеет нулевой объем?

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

Если положение вашей гиперсферы зафиксировано для множества столкновений частиц, то вычисление разложение Вороного / мозаика Дирихле даст вам быстрый способ позже точно определить, какая сфера ближе всего к вашей частице для любой заданной точки пространства.

Однако, чтобы ответить на ваш исходный вопрос об октодеревьях / квадродеревьях / 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-деревья, поскольку расширение до произвольного количества измерений более прямолинейно, однако они приведут к более глубокому дереву. Также легче адаптировать положения разделения, чтобы они соответствовали геометрии вашего гиперсферы с kd-деревом. Приведенное выше описание обнаружения столкновений в дереве 2 ^ n в равной степени применимо к kd-дереву.

{1} Маркировка подключенных компонентов, Ханан Самет, Использование Quadtrees Journal of the ACM Volume 28, Issue 3 (июль 1981 г.)

{2} Обнаружение соседей в изображениях, представленных октодеревьями, Ханан Самет, Компьютерное зрение, графика и обработка изображений, том 46, выпуск 3 (июнь 1989 г.)

{3} Создание выпуклой оболочки, маркировка связанных компонентов и минимальное расстояние расчет для теоретически определенных моделей, Дэн Пидкок, 2000

{4} Эксперименты в представлении изображений с использованием регулярной декомпозиции, Клингер, А., и Дайер, C.R.E, Comptr. Графика и обработка изображений 5 (1976), 68-105.

Октодерево будет работать до тех пор, пока вы можете указать сферы по их центрам - оно иерархически объединяет точки в кубические области с восемью дочерними элементами. Определение соседей в структуре данных октодерева потребует от вас вычислений пересекающихся сфер-кубов (в некоторой степени проще, чем кажется), чтобы определить, какие кубические области в октодереве находятся внутри сферы.

Поиск ближайших соседей означает возвращение вверх по дереву до тех пор, пока вы не получите узел с более чем одним заполненным дочерним элементом и включенными всеми окружающими узлами (это обеспечивает получение запроса со всех сторон).

По памяти это (несколько наивный) базовый алгоритм пересечения сферы и куба:

я. Находится ли центр внутри куба (получается одноименная ситуация)

II. Находятся ли какие-либо углы куба в радиусе r от центра (углы внутри сферы)

iii. Для каждой поверхности куба (вы можете исключить некоторые из поверхностей, определив, на какой стороне поверхности находится центр) вычислите (это вся векторная арифметика первого года):

а. Нормаль к поверхности, идущая к центру сферы

б. Расстояние от центра сферы до пересечения нормали с плоскостью поверхности (хорда пересекает плоскость поверхности куба)

c. Пересечение плоскости находится внутри стороны куба (одно условие пересечения хорды с кубом)

iv. Рассчитайте размер хорды (Sin of Cos ^ -1 отношения нормальной длины к радиусу сферы)

v. Если ближайшая точка на прямой меньше, чем расстояние хорды и точка лежит между концами линии, хорда пересекает одно из ребер куба (хорда пересекает поверхность куба где-то вдоль одного из ребер).

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