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

Структура данных бункера.

Гистограмма упорядочена по 100 000 ячеек.

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

Например, если есть ось -выровненные прямоугольники на 2D самолет, структура может ответить на вопрос, «Какие прямоугольники пересекают прямоугольник запроса?» В примере на верхнем рисунке 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 (п), удаление равно O (п), а insert - это O (1), где п количество кандидатов. Если кандидаты равномерно распределены так, чтобы в каждом бункере было постоянное количество кандидатов, запрос будет O (k) куда k - количество интервалов, которые пересекает прямоугольник запроса. Вставка и удаление - это O (м) куда м - количество интервалов, которые пересекает кандидат на вставку. На практике удаление выполняется намного медленнее, чем вставка.

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

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

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

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

Смотрите также

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

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

[1]