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

Question

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

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

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

РЕДАКТИРОВАТЬ: причина, по которой я хочу вставить так быстро, заключается в том, что если вы думаете о прямоугольнике, перемещаемом по экрану, его придется удалить, а затем снова вставить.

Спасибо!

Answer 1

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

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

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

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

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

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

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

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

Answer 2

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

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

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

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

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

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

Answer 3

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

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

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

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

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