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

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

вы находитесь на территории "Binary Space Partitioning" и "Collision Detection"; по сути, идеи в основном заключаются в хранении кубоидов в структуре типа дерева, которая делит пространство, которое они занимают, на аккуратные маленькие коробочки. Решение о том, какую «часть пространства» занимает каждый кубоид, принимается во время вставки в древовидную структуру.

Сделайте поиск в Google на Octrees.

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

Answer 2

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

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

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

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