Конвексан омотач¶
Претпоставимо да су темена простог многоугла \(Q\) сортирана тако да је обилазак у позитивном смеру. Да би тај многоугао био конвексан, потребно је да ниједна тројка узастопних тачака не чини заокрет надесно. Прецизније, дозвољене су колинеарне тројке код којих је средња од три тачке између остале две, као и заокрети налево. Оваквим колинеарним тројкама одговарају опружени углови, а заокретима налево углови мањи од опруженог (тј. оштри, прави или тупи).
У случају да многоугао \(Q\) није конвексан, од интереса је да се одреди најмањи конвексан многоугао који садржи сва темена многоугла \(Q\). Такав многоугао се назива конвексан омотач многоугла \(Q\). Општије, конвексан омотач можемо да дефинишемо на исти начин и за било какав скуп тачака.
Скуп тачака и конвексан омотач тог скупа¶
Интуитивно, конвексан омотач скупа тачака је облик гумице која је прво растегнута тако да обухвати све те тачке, а затим пуштена да се затегне око њих.
Покушајте да набројите неке примене конвексног омотача. Потражите на интернету информације о таквим применама.
Алгоритам¶
Овде ћемо објаснити један од неколико познатих ефикасних алгоритама за налажење конвексног омотача. Алгоритам се зове Грејамово скенирање (енгл. Graham scan) и ради тако што одржава листу темена, која су кандидати за конвексан омотач. Идеја се састоји у томе да обилазимо темена одређеним редом (о редоследу у коме тачке треба да буду ће још бити речи), посматрајући у сваком тренутку последње три виђене тачке. Ако те три тачке чине заокрет надесно, средња од њих припада унутрашњости конвексног омотача и није једно од његових темена, па је треба избацити из листе. Уколико су последње три тачке колинеарне, средњу по распореду такође можемо да избацимо из листе, да бисмо доблили једноставнији резултат. Овај поступак треба понављати док год има узастопних тројки које не чине заокрет налево.
На следећој галерији можете да видите кораке скицираног алгоритма (на претходни или следећи корак прелазите помоћу стрелица испод слике). Црвеном бојом су означене дужи које са претходном дужи не чине заокрет налево, када избацујемо претходну тачку из листе кандидата за конвексан омотач.
Да бисмо добили одговарајући редослед тачака, потребно је да прво нађемо једну тачку која сигурно припада конвексном омотачу. То, на пример, може да буде најнижа тачка (тачка са најмањом \(y\) координатом). Ако има више тачака са најмањом \(y\) координатом, можемо да међу њима изаберемо ону са најмањом \(x\) координатом. Ову тачку ћемо означити са \(P_0\) (и у претходној илустрацији та тачка је означена нулом).
Када одредимо тачку \(P_0\), остале тачке \(P_i\) треба сортирати тако да (оријентисани) углови које полуправе \(P_0P_i\) заклапају са позитивним смером \(x\) осе буду у неопадајућем редоследу. Ако постоје тачке код којих је овај угао исти, можемо да задржимо само ону од њих која је најдаља од тачке \(P_0\) (остале сигурно нису темена конвексног омотача), или да их задржимо све, али да буду уређене по растојању од тачке \(P_0\) (на тај начин ће све осим последње бити елиминисане током обиласка).
Сада комплетан поступак можемо да опишемо следећим псеудокодом:
нека је \(P_0\) најнижа тачка многоугла \(Q\), односно, крајња лева таква тачка, ако има више најнижих
нека су \(P_1, P_2, ..., P_m\) остале тачке многоугла \(Q\), уређене у позитивном смеру при обиласку око \(P_0\) (секундарни критеријум уређивања је растуће по растојању од тачке \(P_0\))
нека је \(S\) празан стек
стави тачку \(P_0\) на стек
стави тачку \(P_1\) на стек
стави тачку \(P_2\) на стек
за свако \(i\) од 3 до \(m\)
док претпоследња тачка стека, последња тачка стека и тачка \(P_i\) не чине заокрет налево
избаци тачку са врха стека
стави тачку \(P_i\) на стек
на стеку су тачке које чине конвексан омотач
Овде се налази и комплетан програм који израчунава конвексан омотач датог скупа тачака (тачке могу да буду дате у било ком редоследу).
Временска сложеност алгоритма¶
Анализирајмо и временску сложеност датог алгоритма.
Време потребно за налажење тачке \(P_0\) је \(O(n)\)
Време потребно за сортирање осталих тачака је \(O(n \log n)\)
Време потребно за обилазак тачака је \(O(n)\)
Сложеност прва два корака би требало да је јасна (подразумева се употреба неког ефикасног алгоритма сортирања), али за сложеност последњег корака вероватно је потребно појашњење. Наиме, због двоструке петље у том делу алгоритма (спољна по новим тачкама, унутрашња која избацује виђене тачке са стека), на први поглед делује да је сложеност овог дела алгоритма \(O(n^2)\). Да бисмо се уверили да је сложеност линеарна, користимо такозвану амортизовану анализу. То значи да не процењујемо горње ограничење трајања унутрашње петље у сваком проласку кроз тело спољне петље засебно, него укупан број извршавања најдубље угнежђеног дела алгоритма, а то је у овом алгоритму избацивање тачака са стека. Са стека не можемо да избацимо више тачака него што смо их на стек ставили, па ова наредба не може да се изврши више од \(n\) пута укупно. Због тога је и сложеност овог дела алгоритма ипак линеарна.
Сабирајући сложености појединих корака, долазимо до закључка да је сложеност комплетног алгоритма Грејамовог скенирања \(O(n \log n)\).
Задаци¶
?