Объекты внутри тома

Question

У меня проблема в том, что мне нужен очень эффективный способ поиска объектов внутри заданного объема.Можно представить, что объекты представлены в виде блоков со значениями X-min, Y-min, Z-min и X-max, Y-max, Z-max.В космосе могут быть миллионы таких объектов, и проблема заключается в том, чтобы найти объекты внутри произвольно заданного пользователем объема.Пользователь вводит min, max значений X, Y и Z для поля.

В настоящее время в таблице базы данных Oracle у меня есть все объекты, диапазон которых проиндексирован для значений X, Y и Z.Любой запрос, чтобы найти объекты, включает в себя сравнение данных значений X, Y и Z со значениями объектов.Я считаю, что производительность неудовлетворительная, и я думаю об алгоритме в памяти для решения этой проблемы.Кроме того, требуется найти объекты, которые полностью включены, частично включены.

Спасибо Ey

Answer 1

Существует относительно быстрый способ определения того, попадают ли выровненные по оси ограничивающие рамки в, частично в или без указанного ограничивающего объема. По сути, вы можете назначить битовую маску для значений сравнения границ и определить пересечение ограничивающих рамок, используя AND битовых масок. Это именно то, что вы хотите, и это очень эффективный метод; Я помню, как видел это много лет назад (серьезно, как 15 лет назад); Я опубликую ссылку и дополнительные данные о методе, когда найду его.

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

Answer 2

Не очень элегантные решения, но я надеюсь, что это эффективно.
У него есть часть инициализации, которая займет некоторое время, но затем она окупится, надеюсь, запросы будут быстрыми.
Сначала создайте структуру данных с пространственным разделением, с помощью которой вы сможете искать точки в запрашиваемом контейнере, и вы сможете находить поля таким образом.
Это будет дерево с 8 дочерними узлами на узел. Есть и другие альтернативы, взгляните на k-d деревья

Найдите наименьший вмещающий контейнер, содержащий все коробки.
Разделите этот контейнер на 8 контейнеров одинакового размера.
Для каждой точки в вашем наборе найдите контейнер, которому она принадлежит.
Повторите этот процесс для каждого контейнера, который содержит более одной точки.
Вы получите контейнеры для листьев, имеющие одну точку.

Используя эту структуру, скажем, вы хотите найти все точки в запрашиваемом контейнере.
Начните с вершины дерева и пройдите все ветви / контейнеры, которые пересекаются с запрашиваемым контейнером.
Будет 3 случая:
1) контейнер полностью заключен в запрашиваемый контейнер => все точки в этом поддереве находятся в запрашиваемом контейнере.
2) контейнер находится вне запрашиваемого контейнера => вы не проходите его. (это где вы должны получить эффективность)
3) контейнер пересекает запрашиваемый контейнер => вам придется повторить процесс для всех его дочерних элементов.
Есть некоторые крайние случаи, которые вы должны выяснить.

Чтобы найти прямоугольники, вам нужно поместить каждый из их 8 углов в эту структуру данных.
Углы должны быть связаны с ящиками. Поэтому, когда вы найдете угол, вы узнаете, к какой коробке он принадлежит.

Чтобы определить, какие коробки полностью заключены в запрашиваемый контейнер, вы должны проверить каждую из найденных коробок