Пространственный индекс для прямоугольников с быстрой вставкой
Я ищу структуру данных, которая обеспечивает индексирование для прямоугольников. Мне нужно, чтобы алгоритм вставки был максимально быстрым, поскольку прямоугольники будут перемещаться по экрану (подумайте о перетаскивании прямоугольника с помощью мыши в новое положение).
Я изучал R-Trees, R+Trees, kD-Trees, Quad-Trees и B-Trees, но, насколько я понимаю, вставки обычно медленные. Я предпочел бы иметь вставки с сублинейной сложностью, поэтому, возможно, кто-то может доказать, что я ошибаюсь в любой из перечисленных структур данных.
Я должен быть в состоянии запросить структуру данных для того, какие прямоугольники находятся в точке (x, y) или какие прямоугольники пересекают прямоугольник (x, y, ширина, высота).
РЕДАКТИРОВАТЬ: причина, почему я хочу вставить так быстро, потому что, если вы думаете о прямоугольнике, перемещаемом по экрану, их придется удалить, а затем снова вставить.
Спасибо!
3 ответа
Упомянутые вами структуры данных довольно смешаны: в частности, B-деревья должны быть быстрыми (стоимость вставки увеличивается с логарифмом числа присутствующих элементов), но не ускоряют запросы на пересечение.
Игнорируя это - и надеясь на лучшее - структуры пространственных данных делятся на две части. Первая часть рассказывает, как построить древовидную структуру из данных. Во второй части рассказывается, как отслеживать информацию на каждом узле, которая описывает элементы, хранящиеся под этим узлом, и как использовать ее для ускорения запросов.
Обычно вы можете ущипнуть идеи по отслеживанию информации на каждом узле, не используя (дорогие) идеи о том, как именно должно быть построено дерево. Например, вы можете создать ключ для каждого прямоугольника путем чередования битов координат его точек, а затем использовать совершенно обычную древовидную структуру (такую как B-дерево или дерево AVL или красно-черное дерево) для хранения это, сохраняя при этом информацию на каждом узле. На практике это может достаточно ускорить ваши запросы - хотя вы не сможете сказать это, пока не внедрили и не протестировали его на реальных данных. Целью инструкций построения дерева в большинстве схем является предоставление гарантий производительности.
Два приписки:
1) Мне для этого нравятся деревья Патриции - их достаточно легко реализовать, и добавление или удаление записей не сильно нарушает древовидную структуру, поэтому у вас не будет слишком много работы для обновления информации, хранящейся на узлах.
2) В прошлый раз, когда я смотрел на оконную систему, она не беспокоилась ни об одном из этих умных вещей - он просто держал линейный список элементов и просматривал его, когда это было необходимо: это было достаточно быстро.
Я бы использовал многоуровневый сеточный подход (эквивалентный квад-деревьям в некоторой форме).
Я предполагаю, что вы используете целочисленные координаты (то есть пиксели) и имеете достаточно места для хранения всех пикселей.
Иметь массив списков прямоугольников, по одному на каждый пиксель. Затем, бин два на два и сделайте это снова. И снова, и снова, и снова, пока у вас не будет одного пикселя, который охватывает все.
Теперь ключ заключается в том, что вы вставляете свои прямоугольники на уровне, который соответствует размеру прямоугольника. Это будет что-то вроде (размер пикселя) ~= min(высота, ширина)/2. Теперь для каждого прямоугольника у вас есть только несколько вставок, которые нужно сделать в списках (вы можете связать его сверху константой, например, выбрать что-то от 4 до 16 пикселей).
Если вы хотите найти все прямоугольники в точке x, y, вы посмотрите в список наименьшего пикселя, а затем в список двоичного пикселя 2x2, который его содержит, а затем в 4x4 и т. Д.; у вас должно быть log2(количество пикселей) шагов для просмотра. (Для больших пикселей вы должны проверить, действительно ли (x,y) было в прямоугольнике; вы ожидаете, что около половины из них будут успешными на границах, и все они будут успешными внутри прямоугольника, так что вы ожидаете не хуже, чем в 2 раза больше работы, чем если бы вы смотрели прямо на пиксель.)
А как насчет вставки? Это очень недорого -O(1), чтобы поставить себя в начале списка.
Как насчет удаления? Это дороже; вам нужно просмотреть и вылечить каждый список для каждого пикселя, в который вы ввели. Это примерно O(n) в количестве прямоугольников, перекрывающих эту позицию в пространстве, и примерно одинакового размера. Если у вас действительно большое количество прямоугольников, вам следует использовать некоторую другую структуру данных для их хранения (хэш-набор, дерево RB и т. Д.).
(Обратите внимание, что если ваш наименьший прямоугольник должен быть больше пикселя, вам не нужно фактически формировать многомасштабную структуру вплоть до уровня пикселей; просто опускайтесь до тех пор, пока самый маленький прямоугольник не будет безнадежно потерян внутри вашего сгруппированного пикселя.)
Это, возможно, расширенный комментарий, а не ответ.
Я немного озадачен тем, что вы действительно хотите. Я мог бы догадаться, что вы хотите, чтобы структура данных поддерживала быстрые ответы на такие вопросы, как "Учитывая идентификатор прямоугольника, вернуть его текущие координаты". Это правильно?
Или вы хотите ответить "какой прямоугольник находится в позиции (x,y)"? В этом случае может быть достаточно массива с размерами, соответствующими высоте и ширине вашего дисплея, причем каждый элемент массива представляет собой (предположительно короткий) список прямоугольников на этом пикселе.
Но затем вы заявляете, что вам нужен алгоритм вставки, чтобы как можно быстрее справиться с постоянно движущимися прямоугольниками. Если бы у вас было только, скажем, 10 прямоугольников на экране, вы могли бы просто иметь массив из 10 элементов, содержащий координаты каждого из прямоугольников. Обновление их позиций не потребовало бы никаких вставок в структуру данных.
Сколько прямоугольников? Как быстро они создаются? и уничтожен? Как вы хотите справиться с перекрытиями? Является ли прямоугольник просто границей, или он включает в себя интерьер?