Запрос коллекции прямоугольников для перекрытия входного прямоугольника

Question

В многомерном пространстве у меня есть коллекция прямоугольников, все из которых выровнены по сетке. (Я использую слово «прямоугольники» свободно - в трехмерном пространстве они будут прямоугольными призмами.)

Я хочу запросить в этой коллекции все прямоугольники, которые перекрывают входной прямоугольник.

Какова лучшая структура данных для хранения коллекции прямоугольников? Я буду время от времени добавлять прямоугольники и удалять прямоугольники из коллекции, но эти операции будут нечастыми. Операция, которую я хочу выполнить, - это запрос.

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

Однако я хочу, чтобы операция запроса была быстрее линейной.

Я смотрел на структуру данных R-дерева , но она содержит набор точек, а не набор прямоугольников, и я не вижу очевидного способа обобщить ее.

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

Меня интересует общее решение, но я также расскажу вам о свойствах моей конкретной проблемы: у моего пространства задач есть три измерения, и их кратность сильно варьируется. Первое измерение имеет два возможных значения, второе измерение имеет 87 значений, а третье измерение имеет 1,8 миллиона значений.

Answer 1

Возможно, вы можете использовать KD-Trees , которые можно использовать для прямоугольников в соответствии со страницей вики:

Изменения

Вместо очков

Вместо точек, kd-дерево также может содержат прямоугольники или hyperrectangles [5]. 2D-прямоугольник считается четырехмерным объектом (xlow, xhigh, ylow, yhigh). Таким образом, поиск диапазона становится проблемой возвращения всех прямоугольники, пересекающие поиск прямоугольник. Дерево построено обычным способом со всеми прямоугольниками в листья. В ортогональном диапазоне поиск, противоположная координата используется при сравнении с медиана. Например, если текущий уровень делится по высоте, мы проверяем координата xlow поиска прямоугольник. Если медиана меньше координата xlow поиска прямоугольник, то нет прямоугольника в левая ветвь может пересекаться с прямоугольник поиска и так может быть обрезка. В противном случае обе ветви должны быть пройденным. Смотрите также интервальное дерево, который является одномерным частным случаем.

Answer 2

Давайте назовем исходную задачу PN - где N - число измерений.

Предположим, мы знаем решение для P1 - 1-мерной задачи: найдите, перекрывает ли новый интервал заданный набор интервалов.

Как только мы узнаем, как ее решить, мы можем проверить, перекрывается ли новый прямоугольник с набором прямоугольников в каждой из проекций x / y / z.

Таким образом, решение P3 эквивалентно P1_x И P1_y И P1_z.

Для эффективного решения проблемы P1 мы можем использовать отсортированный список. Каждый узел списка будет включать координату и число открытых открытых intetrvals-to-this-координаты.

Предположим, у нас есть следующие интервалы: [1,5] [2,9] [3,7] [0,2]

тогда список будет выглядеть следующим образом:

{0,1}, {1,2}, {2,2}, {3,3}, {5,2}, {7,1}, {9,0}

если мы получим новый интервал, скажем, [6,7], мы найдем самый большой элемент в списке, который меньше 6: {5,2}, и самый простой элемент, который больше 7: {9,0} .

Так что легко сказать, что новый интервал перекрывается с существующими.

И поиск в отсортированном списке быстрее линейного:)

Answer 3

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

Используя ограничение дискретных значений - вы можете создать вторичную табличную структуру данных, в которой вы будете хранить дискретные значения второго измерения(87 возможных значений).Предположим, что эти значения представляют плоскости, перпендикулярные этому измерению.Для каждой из этих плоскостей вы можете хранить в этой вторичной таблице прямоугольники, которые пересекают эти плоскости.

Точно так же для третьего измерения вы можете использовать другую таблицу с таким количеством равных интервалов значений, сколько вам нужно (1,8 миллиона - это слишком много, поэтому вы, вероятно, захотите сделать это по крайней мере на пару величин меньше), исоздайте карту прямоугольников, которые находятся между двумя выбранными значениями.

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