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