Зачем кому-то использовать Octree поверх KD-дерева?

У меня есть некоторый опыт в научных вычислениях, и я широко использовал kd-деревья для приложений BSP (разбиение двоичного пространства). Недавно я стал более знаком с октреями, схожей структурой данных для разделения трехмерных евклидовых пространств, но той, которая работает с фиксированными регулярными интервалами.

Небольшое исследование независимости, кажется, показывает, что kd-деревья обычно превосходят по производительности для большинства наборов данных - быстрее создавать и запрашивать. Мой вопрос: каковы преимущества октод в пространственно-временном исполнении или нет, и в каких ситуациях они наиболее применимы (я слышал, программирование трехмерной графики)? Краткое изложение преимуществ и проблем обоих типов мне бы очень понравилось.

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

Клетки в дереве могут иметь высокое соотношение сторон, в то время как ячейки окт-дерева гарантированно будут кубическими. Поскольку это теоретическая доска, я дам вам теоретическую причину, по которой проблема заключается в высоком соотношении сторон: невозможно использовать границы объема для управления количеством ячеек, которые вы должны исследовать при решении приближенных запросов ближайших соседей.$kD$

Более подробно: если вы запрашиваете -approximate ближайшего соседа к точке запроса , а фактический ближайший сосед находится на расстоянии , вы обычно заканчиваете поиском, который проверяет каждую ячейку структуры данных, которая достигает изнутри в внешняя поверхность кольца или кольцевая оболочка с внутренним радиусом и внешним радиусом . Если ячейки имеют ограниченное соотношение сторон, как и в дереве квадрантов, то таких ячеек может быть не более , и вы можете доказать хорошие границы времени для запроса. Если соотношение сторон не ограничено, как в дереве, эти границы не применяются.q d d ( 1 + ϵ ) d 1 / ϵ d - 1 k $\epsilon$$q$$d$$d$$(1+\epsilon)d$$1/\epsilon^{d-1}$$kD$

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

Группа друзей и я работаем над космической RTS игрой как веселым сайд-проектом. Мы используем многое из того, чему научились в Computer Science, чтобы сделать его высокоэффективным, что позволит нам впоследствии создавать огромные армии.

Для этой цели мы рассмотрели использование kd-деревьев, но мы быстро отклонили их: вставки и удаления чрезвычайно распространены в нашей программе (рассмотрим корабль, летящий в космосе), и это нечестивый беспорядок с kd-деревьями. Поэтому мы выбрали октры для нашей игры.

Каковы преимущества октод в пространственно-временном исполнении или нет, и в каких ситуациях они наиболее применимы (я слышал, программирование трехмерной графики)?

кД деревья сбалансированные бинарные деревья и octrees являются попытки так преимущества и недостатки, вероятно , унаследованные от этих более общих структур данных. В частности:

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

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

РЕДАКТИРОВАТЬ

Очевидно, мои ссылки на попытки и однородность нуждаются в уточнении.

Попытки представляют собой семейство структур данных, представленных деревьями словарей, и используются в качестве словарей для ключей, которые являются последовательностями (в первую очередь, строками, но также последовательностями ДНК и битами в значении хэша для хэш-попыток). Если каждый словарь отображает один бит каждой из координат x, y и z (старший значащий бит на первом уровне дерева, следующий значащий бит на втором уровне и т. Д.), То дерево представляет собой дерево, которое равномерно разделяет трехмерное пространство. Следовательно, октреи наследуют характеристики попыток, которые, как правило:

• Высокий коэффициент ветвления может означать, что мелкие деревья имеют мало косвенных указаний, поэтому поиск происходит быстро, например, 20 уровней двоичного дерева могут быть сохранены на 4 уровнях дерева с коэффициентом ветвления 256.
• Попытки не перебалансированы во время вставок и удалений, что экономит дорогостоящую операцию, необходимую для сбалансированных двоичных деревьев.

Недостатком является то, что неоднородность может привести к несбалансированным попыткам / октодам, поэтому поиск может потребовать много косвенных указаний. Эквивалентная проблема в попытках решается с помощью сжатия краев для объединения нескольких уровней косвенности в один уровень. Октреи не делают этого, но ничто не мешает вам сжать октри (но я не думаю, что вы могли бы назвать результат октреем!).

Для сравнения рассмотрим специализированный словарь для строковых ключей, который представлен в виде дерева. Первый уровень дерева ветвится на первом символе в ключе. Второй уровень на втором персонаже и тд. Любую строку можно найти, выполнив поиск первого символа в ключе словаря, чтобы получить второй словарь, который используется для поиска второго символа в ключе и так далее. Набор строк случайных ключей будет однородным распределением. Набор ключевых строк, которые имеют общий префикс (например, все слова, начинающиеся с «анти»), являются неоднороднымираспределение. В последнем случае первый словарь содержит только одну привязку для «a», второй - только одну для «n» и так далее. Поиск любого отображения в дереве всегда осуществляется путем поиска в тех же четырех словарях с теми же четырьмя ключами. Это неэффективно, и это то, что делают октреи, если, например, они используются для хранения гетерогенных распределений частиц, где подавляющее большинство частиц находится в крошечном объеме в векторном пространстве.

Octrees полезны в качестве базового типа данных для моделей континуума, см., Например, решатель потока Gerris . Жизнь в гидродинамике достаточно сложна, поэтому знание того, что размеры всех ваших субкубов зависят только от их глубины, должно быть упрощающим фактором.

Предостережение: я не подвижный динамик!