Как мне определить, в каких кубоидах находится точка, не перебирая их все?
-
18-09-2019 - |
Вопрос
У меня есть несколько кубоидов, позиции и размеры которых указаны с минимальными и максимальными значениями 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).;т. е.Возможно, я ищу "гиперкубоиды", а не кубоиды.)
Решение
Одним из простых способов ускорить выполнение этого запроса является построение следующего равномерная сетка структура данных (часто называемая ячейками) как этап предварительной обработки:Положить n x n x n
(в 3d) наложите сетку на вашу сцену и для каждой ячейки сетки сохраните указатель на все кубоиды, пересекающие эту ячейку.Теперь для точки запроса вы можете напрямую вычислить, в какой ячейке единой сетки она находится, а затем вам нужно проверить только кубоиды, связанные с этой ячейкой, а не все кубоиды.
В зависимости от того, насколько велико пространство и насколько различны размеры кубоида, этот метод может оказаться не очень эффективным, потому что вам может быть трудно выбрать хороший n
разрешения для ускорения достаточно и не требуется огромное количество ячеек.Чтобы преодолеть это, вы можете попробовать изучить более адаптивные способы разделения пространства, такие как kd-деревья (kd-деревья в Википедии), которые в основном представляют собой бинарные деревья , разделяющие пространство плоскостями , выровненными по оси:Смотрите пример здесь, где красная плоскость делит прямоугольник на две части, а затем зеленая на более мелкие части, затем синяя...
Запрос, использующий kd-tree, сначала перемещается вниз к листу kd-tree, где расположена точка запроса, а затем сверяется с локальными кубоидами в этой ячейке. Другая структура данных с разделением пространства варианты могут быть найдены здесь.
Другим вариантом было бы использовать ограничивающие иерархии томов, которые группируют объекты вместе в ограничивающие объемы, а затем группируют ограничивающие объемы в более крупные ограничивающие объемы и так далее...чтобы получить иерархию ограничивающих объемов.Они лучше адаптируются к сцене и могут легче обрабатывать сцены, в которых объекты перемещаются, но я бы подумал, что для ваших настроек разделение пространства могло бы сработать хорошо...В любом случае, для получения более подробной информации смотрите эта глава книги.
Другие советы
вы приближаетесь к области "Разбиения бинарного пространства" и "Обнаружения столкновений".;по сути, идея заключается в том, чтобы поместить кубоиды в структуру древовидного типа, которая делит пространство, которое они занимают, на аккуратные маленькие коробочки.Решение о том, какую "часть пространства" занимает каждый кубоид, принимается во время вставки в древовидную структуру.
Выполните поиск в Google по Octrees.
Эффективное разделение трехмерного пространства и объектов, содержащихся в этом пространстве, является довольно большой частью информатики;в основном используется при разработке компьютерных игр.Некоторые алгоритмы учитывают фактор времени, т.е.чтобы объекты перемещались между пространствами разделов.