Как мне определить, в каких кубоидах находится точка, не перебирая их все?

Question

У меня есть несколько кубоидов, позиции и размеры которых указаны с минимальными и максимальными значениями x, y и z координаты (таким образом, они параллельны главным осям).

например ,У меня могли бы быть следующие 3 кубоида:

10.5 <= x <= 39.4,  90.73 <= y <= 110.2, 90.23 <= z <= 95.87
20.1 <= x <= 30.05,  9.4  <= y <=  37.6,  0.1  <= z <= 91.2
10.2 <= x <= 10.3,   0.1  <= y <=  99.8, 23.7  <= z <= 24.9

Если я затем укажу точку (например (25.3,10.2,90.65)), есть ли способ быстро определить, в каких кубоидах я нахожусь?

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

• Для меня это звучит как проблема типа "нечеткого соответствия", и я замечаю, что В Apache Lucene, В поддерживает запросы диапазона, но это, кажется, работает наоборот (нахождение точки в кубоиде, а не кубоида, содержащего точку).

• Чтобы еще немного усложнить ситуацию, количество измерений может быть больше 3 (оно может быть до 20).;т. е.Возможно, я ищу "гиперкубоиды", а не кубоиды.)

Answer 1

Одним из простых способов ускорить выполнение этого запроса является построение следующего равномерная сетка структура данных (часто называемая ячейками) как этап предварительной обработки:Положить n x n x n (в 3d) наложите сетку на вашу сцену и для каждой ячейки сетки сохраните указатель на все кубоиды, пересекающие эту ячейку.Теперь для точки запроса вы можете напрямую вычислить, в какой ячейке единой сетки она находится, а затем вам нужно проверить только кубоиды, связанные с этой ячейкой, а не все кубоиды.

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

Запрос, использующий kd-tree, сначала перемещается вниз к листу kd-tree, где расположена точка запроса, а затем сверяется с локальными кубоидами в этой ячейке. Другая структура данных с разделением пространства варианты могут быть найдены здесь.

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

Answer 2

вы приближаетесь к области "Разбиения бинарного пространства" и "Обнаружения столкновений".;по сути, идея заключается в том, чтобы поместить кубоиды в структуру древовидного типа, которая делит пространство, которое они занимают, на аккуратные маленькие коробочки.Решение о том, какую "часть пространства" занимает каждый кубоид, принимается во время вставки в древовидную структуру.

Выполните поиск в Google по Octrees.

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