Бин - 2Д Паковање (рачунарска геометрија)

У рачунарској геометрији, бин структура података омогућава ефикасно попуњавање простора правоугаоницима, нпр. ако имамо поређане правоугаонике у 2Д координатном систему равни и интересује нас да нађемо све правоугаонике који секу задати користили бисмо се овим. К-Д стабло је још једна структура података која може ефикасно одговорити на овај задатак. У примеру на слици A, B, C, D, E, и F су постојећи правоугаоници, ако нам је задати правоугаоник Q решење треба да буду C, D, E и F, ако све правоугаонике обележавамо затвореним интервалима.

Структура података дели део равни у бинове униформне величине. Гранични оквир бинова обухвата све потенцијалне кандидате правоугаонике. Сви бинови су поређани у 2Д низ. Сви кандидати су такође приказани 2Д низом. Величина низа кандидата је број бинова у којима је. На пример, на слици, кандидат B има 6 елемената поређаних у 3 реда са по 2 колоне зато што сече 6 бинова у таквом распореду. Сваки бин садржи главу једноструко повезане листе. Ако је кандидат део бина, онда је он повезан са листом тог бина. Сваки елемент у низу кандидата је један чвор у одговарајућој повезаној листи бинова.

Операције

Решавање проблема

Из задатог правоугаоника Q, можемо сазнати којем бину у његовом доњем-левом ћошку припада тако што једноставно одузимањем биновог доњег-левог граничног оквира од доњег-левог ћошка Q и дељењем резултата са ширином и висином бина тим редом. Онда посматрамо пресеке Q и све кандидате повезаних листа тих бинова. За сваког кандидата проверавамо да ли се уопште сече са Q. Ако се сече и ако то претходно није обележено, онда обележавамо. Можемо користити конвенцију да само обележавамо кандидате први пут када установимо да се секу. Ово се лако може обавити тако што спајамо кандидата са задатим правоугаоником и поредимо његов доњи-леви ћошак са тренутном локацијом. Ако су пар онда обележавамо, ако нису настављамо даље.

Уметање и брисање

Уметање је линеарно са бројем бинова које кандидат сече, зато што умећемо кандидата у један бин у константном броју корака. Брисање је скупље јер морамо да претражимо једноструко повезану листу сваког од бинова који садрже кандидата.

У вишенитном окружењу, уметање, брисање и упит се међусобно искључују. Било како било, уместо да закључамо целу структуру података можемо закључати под-домен бинова. Детаљна анализа учинка треба да се обави да би се све што радимо оправдало.

Ефикасност

Анализа је слична као код хеш табела. Најгори случај је да су сви кандидати у једном бину. Онда је проналажење решења O(n), брисање је O(n), а уметање је и даље O(1), где је n број кандидата. Ако су кандидати равномерно распоређени тако да сваки бин има константан број кандидата онда је проналажење решења O(k) где је k број бинова у којима се налази задати правоугаоник. Уметање и брисање су сложености O(m) где је m број бинова у којима се садржи кандидат. У пракси је брисање доста спорије него уметање.

Као и у хеш табелама ефикасност проблема паковања доста зависи од распореда кандидата по биновима и простора који задати правоугаоник заузима. Генерално, што је мањи задати правоугаоник то је тражење решења ефикасније. Величина бинова треба да буде таква да садржи што мање кандидата, али да буде довољно велика да кандидати не буду део превише бинова. Ако кандидат заузима доста бинова онда током решавања морамо да га превише пута проверавамо да ли се сече, чак и када закључимо да се секу и обележимо га. Нпр. правоугаоник E је посећен 4 пута при решавању, па је морао и да буде прескочен 3 пута.

Поређење са другим структурама података

У поређењу са К-Д стаблом, бин структура омогућава ефикасно уметање и брисање без компликација које изазива балансирање. Ово решење може бити врло корисно у алгоритмима који требају да често додају нове и нове правоугаонике у структуру података.