Найти прямоугольники, содержащие точку - эффективный алгоритм

Добрый день.

Моя ситуация:

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

Вопросы:

Какова эффективная структура для хранения прямоугольников?
Какой алгоритм эффективен в этом случае?
- И какой алгоритм эффективен только для добавления прямоугольников без удаления?

Спасибо :-).

Ответ 1

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

Wikipedia, short ppt и исследовательская статья поможет вам понять концепцию.

Ответ 2

В java вы можете использовать shape.contains

Но в целом, если предположить, что прямоугольник определяется (x, y, width, height), вы делаете

if (pt.x >= x && pt.x <= x + width & pt.y >= y & pt.y <= y + height)...

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

Ответ 3

Прямоугольник (left, top, right, bottom) содержит точку (x, y), если left < x < right и top < y < bottom (при условии, что координаты увеличиваются вниз, что имеет место с большинством аппаратных средств, которые я видел; если ваши координаты увеличиваются вверх, тем больше традиционно математический случай, swap top и bottom). Вы не будете намного эффективнее, чем тест.

Если вы рассматриваете прямоугольник как "содержащий" точку, если она также находится на границе, замените все < на <=.

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

Ответ 4

Кажется, что ваш набор прямоугольников может быть динамическим ( "... для добавления прямоугольников..." ). В этом случае - 2D Дерево интервала может быть решением.

Ответ 5

Вот простое решение.

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