Пространственный индекс для прямоугольников с быстрой вставкой

Question

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

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

Я должен быть в состоянии запросить структуру данных для того, какие прямоугольники находятся в точке (x, y) или какие прямоугольники пересекают прямоугольник (x, y, ширина, высота).

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

Спасибо!

Answer 1

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

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

Обычно вы можете ущипнуть идеи отслеживания информации на каждом узле, не используя (дорогие) идеи о том, как именно следует строить дерево. Например, вы можете создать ключ для каждого прямоугольника путем бит-чередования координат его точек, а затем использовать совершенно обычную древовидную структуру (например, B-дерево или дерево AVL или дерево Red-Black) для хранения он, сохраняя при этом информацию на каждом узле. Это может на практике ускорить ваши запросы достаточно, хотя вы не сможете сказать это, пока вы не внедрили и не протестировали его на реальных данных. Цель инструкций по деревообразованию в большинстве схем - обеспечить гарантии эффективности.

Два постскриптумов:

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

2) В прошлый раз, когда я смотрел на оконную систему, он не беспокоился ни о каком этом умном материале - он просто держал линейный список предметов и искал всю дорогу, когда ему было нужно: был достаточно быстрым.

Answer 2

Возможно, это расширенный комментарий, а не ответ.

Я немного озадачен тем, что вы действительно хотите. Я мог предположить, что вы хотите, чтобы структура данных поддерживала быстрые ответы на такие вопросы, как «Учитывая идентификатор прямоугольника, верните его текущие координаты». Это правильно ?

Или вы хотите ответить «какой прямоугольник находится в положении (x, y)»? В этом случае может потребоваться массив с размерами, соответствующими высоте и ширине вашего дисплея, причем каждый элемент в массиве будет (предположительно коротким) списком прямоугольников на этом пикселе.

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

Сколько прямоугольников? Как быстро они создаются? и уничтожены? Как вы хотите справиться с перекрытиями? Является ли прямоугольник только границей, или включает в себя интерьер?

Answer 3

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

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

Имейте массив списков прямоугольников, по одному для каждого пикселя. Затем, два раза в два, и сделайте это снова. И снова, и снова, и снова, пока у вас нет одного пикселя, который покрывает все.

Теперь ключ заключается в том, что вы вставляете прямоугольники на уровне, соответствующем размеру прямоугольника. Это будет что-то вроде (размер пикселя) ~ = min (высота, ширина)/2. Теперь для каждого прямоугольника у вас есть только несколько вложений, которые нужно сделать в списках (вы могли бы связать их выше константой, например, выбрать что-то, что имеет от 4 до 16 пикселей).

Если вы хотите искать все прямоугольники в x, y, вы смотрите в списке наименьшего пикселя, а затем в списке двухъядерного пикселя 2x2, который содержит его, а затем в формате 4x4 и т. Д .; вы должны иметь шаги log2 (количество пикселей) для просмотра.(Для больших пикселей вам нужно проверить, действительно ли (x, y) находится в прямоугольнике, вы ожидаете, что примерно половина из них будет успешной на границах, и все они будут успешными внутри прямоугольника, поэтому вы ожидаете не хуже, чем в 2 раза больше работы, чем если бы вы напрямую посмотрели на пиксель.)

Теперь, как насчет вставки? Это очень недорого - O (1), чтобы встать на передний план списка.

Как насчет удаления? Это дороже; вам нужно просмотреть и исцелить каждый список для каждого введенного вами пикселя. Это примерно O (n) в количестве прямоугольников, перекрывающихся в этой позиции в пространстве и примерно такого же размера. Если у вас действительно большое количество прямоугольников, вы должны использовать другую структуру данных для их хранения (хеш-набор, дерево RB и т. Д.).

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