Поиск ограничивающих прямоугольников (выровненных по оси) для заданной точки запроса в 2 измерениях

У меня есть набор очень многих прямоугольников, выровненных по осям, которые могут быть вложенными и пересекающимися. Я хочу иметь возможность найти все прямоугольники, которые окружают/связывают точку запроса. Что было бы хорошим подходом для этого? РЕДАКТИРОВАТЬ: Дополнительная информация-
1. Под очень многими я имел в виду ~ 100 миллионов или более.
2. Прямоугольники распределены по огромному промежутку (пространству страны). Ограничений по размерам нет.
3. Да, прямоугольники могут быть предварительно обработаны и сохранены в древовидной структуре.
4. Вставки и удаления в реальном времени не требуются.
5. Я только нужно найти все прямоугольники, окружающие/ограничивающие заданную точку запроса. Мне не нужны Ближайшие Соседи.

Как вы могли догадаться, это приложение для геозонирования в реальном времени на мобильном устройстве и, следовательно, -
6. Нет необходимости повторять поиск для прямоугольников, достаточно удаленных от точки.

Я пробовал KD-деревья и Quad-деревья, приближая каждый прямоугольник к точке. Они дали мне различные характеристики в зависимости от размера прямоугольников. Есть ли более прямой способ сделать это? Как насчет r деревьев?


algorithm data-structures geospatial spatial-index
person chilljeet    schedule 15.12.2014    source источник
comment
Сколько очень много? Можете ли вы предварительно обработать прямоугольники, чтобы построить структуру данных для запросов? Будете ли вы проверять множество точек на одном и том же наборе прямоугольников? Вы можете начать с наивного метода в любом случае. Это вполне может быть достаточно быстро для ваших целей, а если нет, то, по крайней мере, у вас есть известный рабочий алгоритм, с которым вы можете протестировать свои оптимизации.   -  person Jim Mischel    schedule 15.12.2014
comment
Привет, Джим, что именно ты имеешь в виду наивные методы? Кроме того, я отредактировал вопрос, чтобы сделать его более понятным.   -  person chilljeet    schedule 16.12.2014
comment
Я предполагаю, что прямоугольники, которые у вас есть, известны заранее, и они вряд ли будут двигаться, сжиматься или растягиваться. Если я прав, то вам следует рассмотреть R-дерево с массовой загрузкой (или его варианты).   -  person Rerito    schedule 16.12.2014
comment
Наивный метод заключается в последовательном поиске по всему списку, что явно нецелесообразно для списка из 100 миллионов прямоугольников.   -  person Jim Mischel    schedule 16.12.2014

Ответы (2)


arrow_upward
0
arrow_downward

Вам нужно посмотреть на структуру данных R*-дерева.

В отличие от многих других структур, R*-дерево может хранить (перекрывающиеся) прямоугольники. Он не ограничен точечными данными. Вы также сможете найти много публикаций о том, как лучше всего аппроксимировать многоугольники, прежде чем помещать их в указатель. Кроме того, он масштабируется до довольно больших данных, так как может работать и на диске.

R*-деревья работают быстрее при массовой загрузке; так как это можно использовать для уменьшения перекрытия страниц индекса и обеспечения почти идеально сбалансированного дерева, тогда как динамические вставки гарантируют, что каждая страница будет заполнена как минимум наполовину или около того. т.е. дерево с массовой загрузкой часто использует вдвое меньше памяти/хранилища.

Однако для двумерных данных и запросов вашего типа дерево квадрантов или сетка могут работать достаточно хорошо. Это зависит от того, насколько сильно различается локальная плотность данных.

person Has QUIT--Anony-Mousse    schedule 17.12.2014
comment
Я собираюсь попробовать R* TREES, используя библиотеку BOOST. - person chilljeet; 22.12.2014
comment
Я понимаю, что поиск в дереве R должен быть полем запроса, однако я хочу искать все прямоугольники, которые обязательно содержат заданную точку запроса. Это возможно? Будет ли преобразование прямоугольника запроса в точку (сделав его достаточно маленьким) дать желаемые результаты? - person chilljeet; 22.12.2014
comment
Вы можете выполнять различные виды поиска, включая ближайших соседей, перекрытие, локализацию и т. д. — Думаю, в вашем случае вы хотите перекрыть точку запроса. - person Has QUIT--Anony-Mousse; 22.12.2014
comment
ну, если это возможно, то мне не нужно искать дальше. Я собираюсь углубиться в это. Спасибо, что указали мне правильное направление. - person chilljeet; 22.12.2014
comment
У меня возникли проблемы с получением хорошей документации по реализации BOOST Rtree. В официальной документации особенно не хватает пространственных индексов. Есть что-нибудь, что может быть полезно? - person chilljeet; 24.12.2014
comment
Я никогда не использовал его. Здесь было несколько вопросов по этому поводу, но я не помню, чтобы видел ответы - вероятно, слишком маленькая база пользователей, может быть, спросите в списке рассылки boost? - person Has QUIT--Anony-Mousse; 24.12.2014
comment
Я решил использовать sqlite-реализацию R*Tree. Это позволяет мне запрашивать в соответствии с моим требованием, просто используя неравенство. Однако дерево всегда анализируется сверху вниз, и я хотел бы изменить его на анализ снизу вверх от последнего результата. Любые указатели на это? - person chilljeet; 04.02.2015
comment
Что вы подразумеваете под разбором r-дерева? Деревья не анализируются. - person Has QUIT--Anony-Mousse; 04.02.2015
comment
Простите мою терминологию. Насколько я понимаю, R-дерево всегда начинает поиск с родительского узла. Я хочу оптимизировать это для своего приложения, выполняющего последующие поиски снизу вверх, поскольку последующие результаты почти всегда будут находиться рядом с «заборами». - person chilljeet; 05.02.2015
comment
Единственный способ добраться до листа — начать с корня и перемещаться по дереву. Ваша идея похожа на соединения knn, но даже они начинаются с листа и спускаются по уровню. - person Has QUIT--Anony-Mousse; 05.02.2015
comment
При первом выполнении поиска он идет вниз по дереву и находит правильный «забор», при последующих поисках он проходит вверх от последнего результата до тех пор, пока не найдет родительский узел, который может содержать правильный «забор». Затем поиск снова идет вниз. Это звучит абсурдно? - person chilljeet; 05.02.2015
comment
Вот как выглядит поиск по дереву, да. Найдите координаты, затем расширяйтесь до окрестностей, насколько хотите. Но вам придется перезапустить для следующего поиска (и это не сильно повредит, вы все равно обычно будете иметь индексные страницы в кеше) - person Has QUIT--Anony-Mousse; 05.02.2015
comment
Спасибо. Я довольно новичок во всем этом. Я планирую реализовать это на микроконтроллере для приложения реального времени, и поэтому меня беспокоит производительность. - person chilljeet; 05.02.2015
comment
Для оперативных и не слишком больших наборов данных (которые помещаются в основную память) не пренебрегайте примитивными подходами на основе сетки. Они тратят больше памяти, но их намного проще реализовать, и они могут содержать множество обновлений. - person Has QUIT--Anony-Mousse; 05.02.2015

arrow_upward
1
arrow_downward

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

Это хорошо работает для небольших прямоугольников, но если много прямоугольников покрывают почти всю область, вам все равно придется проверять их все.

person Erik P.    schedule 15.12.2014
comment
Как насчет kd-деревьев и r-деревьев? - person Gigamegs; 16.12.2014
comment
Оба они также могут работать. R-деревья могут потребовать немного больше усилий для повышения производительности, оба эффекта связаны с подкачкой страниц; это, вероятно, зависит от фактической рабочей нагрузки, поэтому вам нужно будет реализовать оба, чтобы быть уверенным. Kd-деревья (для K = 2) очень похожи на деревья квадрантов, которые я ожидал. - person Erik P.; 16.12.2014
comment
@ Эрик, я думал примерно так же. Как вы предлагаете мне выбрать плоскость разделения? Кроме того, как мне позаботиться о пересекающихся и вложенных прямоугольниках? - person chilljeet; 17.12.2014
comment
В качестве первой попытки вы можете взять набор всех верхних и нижних границ и разделить его по медиане. То же самое для горизонтального разделения. Это определяет дерево прямоугольников, по одному на каждый узел дерева. Эти прямоугольники не совпадают с прямоугольниками, которые вы храните! Вложение и перекрытие работают автоматически, если вы сохраняете каждый прямоугольник в самом нижнем узле, для которого он содержится в соответствующем прямоугольнике дерева. - person Erik P.; 17.12.2014
comment
@ Эрик, я решил пока попробовать дерево R*. Тем не менее, я буду экспериментировать с использованием дерева KD для эффективного хранения и поиска прямоугольников в ближайшем будущем. Я опубликую обновление, когда я это сделаю. - person chilljeet; 22.12.2014