Объекты внутри тома
У меня проблема в том, что мне нужен очень эффективный способ поиска объектов внутри заданного объема. Можно представить, что объекты представлены в виде блоков со значениями X-min, Y-min, Z-min и X-max, Y-max, Z-max. В космосе может быть миллионы таких объектов, и проблема заключается в том, чтобы найти объекты внутри произвольно заданного пользователем объема. Пользователь вводит min,max значений X,Y и Z окна.
В настоящее время у меня есть все те объекты в таблице базы данных Oracle, диапазон которых проиндексирован для значений X,Y и Z. Любой запрос, чтобы найти объекты, включает в себя сравнение данных значений X,Y и Z со значениями объектов. Я считаю, что производительность неудовлетворительная, и я думаю об алгоритме в памяти, чтобы решить эту проблему. Также требуется найти объекты, которые полностью включены, частично включены.
Спасибо эй
2 ответа
Существует относительно быстрый способ определения того, попадают ли выровненные по оси ограничивающие рамки в, частично в или без указанного ограничивающего объема. По сути, вы можете назначить битовую маску для значений сопоставления границ и определить пересечение ограничивающих рамок с помощью ANDing битовых масок. Это именно то, что вы хотите, и это очень эффективный метод; Я помню, как видел это много лет назад (серьезно, как 15 лет назад); Я опубликую ссылку и больше данных о методе, когда найду его.
Обновление: Хорошо, я думаю, что оригинальный метод, который я запомнил, был не для этой конкретной ситуации, но у него есть относительно быстрое решение. В одномерном случае (из которого вы можете обобщить другие измерения) вы хотите, чтобы объект был дисквалифицирован, если обе точки поля в этом измерении меньше, чем поле min, или если они оба больше, чем поле Максимум. Повторите для каждого измерения, и это даст вам то, что вы хотите.
Не очень элегантные решения, но я надеюсь, что это эффективно.
Он имеет часть инициализации, которая займет некоторое время, но затем она окупится, и, надеюсь, запросы будут быстрыми.
Сначала создайте структуру данных с пространственным разделением, с помощью которой вы можете искать точки в запрашиваемом контейнере, и вы сможете находить поля таким образом.
Это будет дерево с 8 дочерними элементами на узел. Есть и другие альтернативы, посмотрите на деревья кд
Найдите самый маленький вмещающий контейнер, который содержит все коробки.
Разделите этот контейнер на 8 контейнеров одинакового размера.
Для каждой точки в вашем наборе найдите контейнер, которому он принадлежит.
Повторите этот процесс для каждого контейнера, который имеет более одной точки.
Вы получите контейнеры для листьев, имеющие одну точку.
Используя эту структуру, скажем, что вы хотите найти все точки в запрашиваемом контейнере.
Начните с вершины дерева и пройдите все ветви / контейнеры, которые пересекаются с запрашиваемым контейнером.
Будет 3 случая:
1) контейнер полностью заключен в запрашиваемый контейнер => все точки в этом поддереве находятся в запрашиваемом контейнере.
2) контейнер находится вне запрашиваемого контейнера => вы не проходите его. (это где вы должны получить эффективность)
3) контейнер пересекает запрашиваемый контейнер => вам придется повторить процесс для всех его дочерних элементов.
Есть некоторые крайние случаи, которые вы должны выяснить.
Чтобы найти прямоугольники, вам нужно поместить каждый из 8 их углов в эту структуру данных.
Углы должны быть связаны с ящиками. Поэтому, когда вы найдете угол, вы узнаете, к какой коробке он принадлежит.
Чтобы найти, какие коробки полностью заключены в запрашиваемый контейнер, вы должны проверить каждый из найденных блоков.