Бин (вычислительная геометрия)

В вычислительной геометрии интервал — это структура данных , которая позволяет выполнять эффективные запросы к регионам. Каждый раз, когда точка данных попадает в интервал, частота этого интервала увеличивается на единицу. ^[1]

Например, если есть несколько прямоугольников, выровненных по осям на двумерной плоскости , структура может ответить на вопрос: «Данный прямоугольник запроса, какие прямоугольники его пересекают?» В примере на верхнем рисунке A, B, C, D, E и F являются существующими прямоугольниками, поэтому запрос с прямоугольником Q должен возвращать C, D, E и F , если мы определяем все прямоугольники как закрытые интервалы .

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

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

Операции

Запрос

Из прямоугольника запроса Q мы можем узнать, с каким интервалом эффективно пересекается его нижний левый угол, просто вычитая нижний левый угол ограничивающей рамки интервала из нижнего левого угла Q и разделив результат на ширину и высоту интервала. соответственно. Затем мы можем перебрать интервалы Q, которые пересекаются, и проверить всех кандидатов в связанных списках этих интервалов. действительно ли он пересекает Q. Для каждого кандидата мы проверим , Если да, и если об этом не сообщалось ранее, то мы сообщаем об этом. Мы можем использовать соглашение, согласно которому мы сообщаем о кандидате только в первый раз, когда находим его. Это можно легко сделать, вырезав кандидата по прямоугольнику запроса и сравнив его левый нижний угол с текущим местоположением. Если совпадение, мы сообщаем, иначе пропускаем.

Вставка и удаление

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

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

Эффективность и настройка

Анализ аналогичен хеш-таблице . В худшем случае все кандидаты концентрируются в одном контейнере. Тогда запрос равен O( n ), удаление — O( n ), а вставка — O(1), где n — количество кандидатов. Если кандидаты расположены на равном расстоянии друг от друга, так что в каждом интервале имеется постоянное количество кандидатов, запрос равен O( k ), где k — количество интервалов, которые пересекает прямоугольник запроса. Вставка и удаление — это O( m ), где m — количество ячеек, которые пересекает вставляющий кандидат. На практике удаление происходит намного медленнее, чем вставка.

Как и хеш-таблица, эффективность bin во многом зависит от распределения местоположения и размера кандидатов и запросов. В общем, чем меньше прямоугольник запроса, тем эффективнее запрос. Размер подборки должен быть таким, чтобы в ней содержалось как можно меньше кандидатов, но при этом достаточно большим, чтобы кандидаты не охватывали слишком много подборок. Если кандидат охватывает множество интервалов, запрос должен пропускать этого кандидата снова и снова после того, как о нем сообщается в первом интервале пересечения. Например, на рисунке E посещается 4 раза в запросе Q , поэтому его нужно пропустить 3 раза.

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

По сравнению с другими структурами данных запроса диапазона

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

Ссылки

^ Оптимизация поиска гармонии для HDR-брахитерапии простаты . 2008. ISBN 9780549534365 . Архивировано из оригинала 06 марта 2016 г. Проверено 12 января 2016 г.

См. также

k Дерево -d — еще одна эффективная структура данных запроса диапазона.
Разделение пространства
Квантование (обработка сигналов)

[1] Оптимизация поиска гармонии для HDR-брахитерапии простаты . 2008. ISBN 9780549534365 . Архивировано из оригинала 06 марта 2016 г. Проверено 12 января 2016 г.

[1]