Још неки геометријски алгоритми¶

Друга решења проблема конвексног омотача¶

Поред раније изложеног алгоритма Грејамовог скенирања, постоји још неколико алгоритама вредних пажње, који налазе конвексан омотач датог коначног скупа тачака. Један од једноставнијих и старијих је алгоритам увијања поклона, познат и као Џарвисов марш. Идеја овог алгоритма је следећа:

Псеудокод алгоритма увијања поклона:

- нађи једну тачку \(P_0\), која сигурно припада конвексном омотачу (нпр. тачка са највећом \(x\)

координатом, а ако има више таквих, онда она међу њима која има и највећу \(y\) координату)

- понављај

- нађи следећу тачку \(P_{i+1}\) конвексног омотача, као ону од тачака полазног скупа

за коју је оријентисани угао између вектора \(P_iP_{i+1}\) и позитивног смера \(x\) осе

најмањи

док не добијеш да је следећа тачка конвексног омотача једнака тачки \(P_0\)

Лако се уочава да је сложеност алгоритма увијања поклона \(O(nk)\), где је \(n\) број тачака полазног скупа, а \(k\) број темена конвексног омотача. Због тога у неповољним случајевима овај алгоритам може да захтева и број операција (а тиме и време) реда \(n^2\).

Задатак: Опишите скуп тачака за који је алгоритму увијања поклона потребно квадратно време да израчуна конвексан омотач тог скупа.

С обзиром на ову ману, значај алгоритма увијања поклона није толико у директној примени, већ више у упознавању идеје, ради лакшег разумевања других, новијих алгоритама, као што је нпр. алгоритам монотоног ланца, или Чанов алгоритам.

Постојање пресека међу више дужи¶

Дато је \(n\) дужи у равни. Одредити да ли се неке две од тих дужи секу, или су сваке две дисјунктне.

Овај проблем може да се реши алгоритмом бришуће (чистеће) линије (sweep line algorithm) у времену \(O(n \log n)\). Идеја алгоритма је да се замисли линија, која се помера преко равни, заустављајући се у крајњим тачкама датих дужи. Обично се узима да је линија вертикална и да се помера слева надесно. Осим ове бришуће линије, потребно је да се води евиденција о тзв активним дужима, тј. дужима на чији почетак смо бришућом линијом већ наишли, а на крај још нисмо. Другим речима, активне дужи су оне које секу бришућу линију. За вођење евиденције користи се нека колекција активних дужи, која се ажурира сваким наиласком бришуће линије на неку од крајњих тачака датих дужи. Колекцију замишљамо као да су активне дужи стално уређене по тачки пресека са бришућом линијом, тј. да датој активној дужи у колекцији претходи активна дуж која је непосредно изнад дате, а следи активна дуж која је непосредно испод дате.

Бришућа линија у проблему постојања пресека неких од датих дужи¶

Псеудокод алгоритма бришуће линије:

Сортирај низ \(P\) свих крајњих тачака датих дужи, растуће по \(X\) координати

креирај празну колекцију сегмената \(T\)

за сваку од \(2n\) тачака низа \(P\) (слева надесно):

ако је текућа тачка \(P_i\) лева тачка своје дужи \(L\):

убаци дуж \(L\) у колекцију \(T\)

ако се дуж \(L\) сече са претходном или следећом дужи у колекцији \(T\)

врати true

иначе (ако је текућа тачка \(P_i\) десна тачка своје дужи \(L\)):

ако се међусобно секу дуж која претходи и дуж која следи дужи \(L\) у колекцији \(T\):

врати true

уклони дуж \(L\) из колекције \(T\)

врати false

Приметимо да нема потребе да се проверава постојање пресека дужи \(L\) са осталим (активним) дужима. Заиста, ако се дуж \(L\) сече са било којом дужи која јој је на почетку претходила, то значи да у тренутку када бришућа линија дође до краја дужи \(L\), \(y\), координата дужи \(L\) постаје већа од \(y\) координате те дужи, па је зато већа и од \(y\) координате најближе претходне дужи, тј. има пресек и са непосредно претходном дужи. Исто важи и за пресеке са дужима које су на почетку биле испод (тј. следиле) дужи \(L\). Такође, нема потребе да се проверава постојање пресека осталих дужи међусобно, јер ће пресеци сваке дужи (са двема њој суседним, што је довољно) бити проверени када та дуж престане да буде активна.

Из описа идеје алгоритма и псеудокода је јасно да је за ефикасност целог алгоритма веома битно да колекција сегмената \(T\) буде имплементирана тако да има следеће две особине:

• омогућава да се за дату активну дуж ефикасно одреди активна дуж непосредно изнад или непосредно испод дате активне дужи (претходна, односно следећа дуж)

• убацивање дужи у колекцију и избацивање из ње треба да буду ефикасне операције

Структура која има обе поменуте особине је самобалансирано бинарно стабло претраге. Неке познате имплементације самобалансираног бинарног стабла претраге су АВЛ-стабло, црвено-црно стабло и Б-стабло.

Налажење свих пресека међу више дужи¶

Дато је \(n\) дужи у равни. Одредити све пресеке дужи по паровима.

Овај проблем је сличан претходном и може да се реши модификацијом претходно описаног алгоритма чистеће линије. Једна таква модификација је алгоритaм Бентли-Отмана, који налази све пресечне тачке у времену \(O((n + k) \log n)\), где је \(k\) број пресечних тачака. У односу на класичан приступ тражења пресека за сваки пар дужи, овај алгоритам је побољшање у случају да је \(k\) довољно мало. Прецизније, да би алгоритaм Бентли-Отмана био асимптотски бржи класичног алгоритма квадратне сложености, потребно је да важи \(k=o\left({\frac {n^2}{\log n}}\right)\).

Заинтересовани читаоци могу да нађу опис алгоритма, псеудокод, анализу сложености и друге детаље нпр. на википедији (Bentley–Ottmann algorithm).

Пресек два конвексна многоугла¶

Дата су два конвексна многоугла својим теменима, наведеним у редоследу обиласка у позитивном смеру. Наћи многоугао који представља њихов пресек.

Можда помало неочекивано, овај проблем може да се реши у линеарном времену. Једна од идеја, до које су 1981. године дошли Џозеф О’Рурк и сарадници (Joseph O’Rourke, Chi-Bin Chien, Thomas Olson, David Naddor: A New Linear Algorithm for Intersecting Convex Polygons), у суштини је сложени пример технике два показивача. Наиме, за сваки од два многоугла се уведе по једна бројачка променљива, која представља индекс текућег темена многоугла. Нека је то променљива \(p\) за многоугао \(P=A_1A_2...A_m\), а променљива \(q\) за многоугао \(Q=B_1B_2...B_n\). Подразумеваћемо да су темена дата у смеру супротном од смера казаљке на сату (позитиван смер) и да се индекси темена у многоугловима узимају по одговарајућем модулу (тј. да је \(A_m=A_0, A_{m+1}=A_1, \ldots, B_n = B_0, B_{n+1} = B_1, \ldots\)).

Са \(\alpha(p)\) ћемо означавати затворену полураван која садржи многоугао \(P\) и ограничена је правом \(A_{p-1}A_p\). Формалније, \(\alpha(p)\) је скуп свих тачака \(T\) дате равни, таквих да тројка \(A_{p-1}A_pT\) чини заокрет налево, или је колинеарна. Слично, са \(\alpha(q)\) означавамо затворену полураван која садржи многоугао \(Q\) и ограничена je правом \(B_{q-1}B_q\). На следећој слици је полураван \(\alpha(p)\) означена црвеном бојом, а полураван \(\alpha(q)\) зеленом.

Алгоритам за одређивање пресека два конвексна многоугла¶

Дужи \(A_{p-1}A_p\) и \(B_{q-1}B_q\) називаћемо текућим дужима многоуглова \(P\) и \(Q\) редом. У свакој итерацији се проверава да ли се текуће дужи два многоугла секу, а пронађене пресечне тачке се додају у резултат. Алгоритам напредује преласком на следеће теме у једном од многоуглова, тј. повећавањем једне од променљивих \(p, q\) за 1. Најосетљивији део алгоритма је управо критеријум одлучивања у којем многоуглу треба напредовати.

Циљ алгоритма је да нађе пар текућих дужи које имају пресек. Неформално говорећи, алгоритам настоји да изабере такво \(q\) да вектор \(\overrightarrow{\rm B_{q-1}B_q}\) сече граничну праву полуравни \(\alpha(p)\), а да истовремено вектор \(\overrightarrow{\rm A_{p-1}A_p}\) сече граничну праву полуравни \(\alpha(q)\). Да би се дошло до таквог пара индекса \(p, q\), користи се следећа идеја:

• ако је зелени вектор \(\overrightarrow{\rm A_{p-1}A_p}\) усмерен ка црвеној правој, а црвени вектор \(\overrightarrow{\rm A_{p-1}A_p}\) од зелене праве (као на слици), напредује се у зеленом многоуглу

• ако је зелени вектор \(\overrightarrow{\rm A_{p-1}A_p}\) усмерен од црвене праве, а црвени вектор \(\overrightarrow{\rm A_{p-1}A_p}\) ка зеленој правој, напредује се у црвеном многоуглу

• иначе (ако су оба вектора усмерена ка правама супротне боје, или оба од тих правих), напредује се у многоуглу који је споља. Када су вектори у оваквом положају, са слике може да се интуитивно разуме који многоугао је споља.

Када се на овај начин бира многоугао у коме се напредује, заиста се долази до пара дужи које се секу, ако такав пар постоји. Након проналажења једне пресечне тачке двеју многоугаоних линија, у темена пресечног многоугла се додају и темена једне многоугаоне линије, и то она која се налазе унутар друге многоугаоне линије.

Итерације (напредовање у једном од два многоугла) се понављају све док се не понови прва пресечна тачка, или док се не изврши \(2(m+n)\) итерација. У случају да се понови прва пресечна тачка, пресек је већ у целости одређен. У супротном саме многоугаоне линије немају пресечних тачака, али пресек многоугаоних површи може да постоји ако је једна од њих подскуп друге. Лако може да се провери који од случајева је наспупио, тако што се испита да ли се једно теме једног многоугла налази у унутрашњости другог и обрнуто (види алгоритам провере припадности тачке многоуглу).

Овај неформалан опис је дат пре свега ради интуитивног разумевања идеје алгоритма. Прецизнији опис алгоритма је дат ниже у псеудокоду. Напомињемо да се припадност тачке полуравни и знак оријентисаног угла утврђују користећи појам оријентације тројке тачака. Овако изложен алгоритам претпоставља да међу тачкама \(A_1, A_2, \ldots, A_m, B_1, B_2, \ldots, B_n\) нема колинеарних тројки. Специјално, пресек страница које припадају различитим многоугловима никад није један од крајева неке од тих страница. У оригналном раду аутора алгоритма описана је и модификација, која исправно обрађује и специјалне случајеве за колинеарним тројкама тачака.

Псеудокод алгоритма за одређивање пресечног многоугла:

Изабери произвољно теме \(A_p\) многоугла \(P\) и теме \(B_q\) многоугла \(Q\)

унутрашњи многоугао на почетку није ниједан

резултат је на почетку празна листа

понављај

ако се \(A_{p-1}A_p\) и \(B_{q-1}B_q\) секу:

ако је пресечна тачка једнака првој пресечној тачки:

врати резултат и заустави се

иначе:

додај пресечну тачку у резултат

// дефиниши унутрашњи многоугао

ако је \(P \in \alpha(q)\): унутрашњи многоугао је \(P\)

иначе: унутрашњи многоугао је \(Q\)

// напредуј у једном од многоуглова

ако је оријентисани угао између праваца \(B_{q-1}B_q\) и \(A_{p-1}A_p\) позитиван:

ако је \(A_p \in \alpha(q)\): Напредуј у \(Q\)

иначе: Напредуј у \(P\):

иначе:

ако је \(B_q \in \alpha(p)\): Напредуј у \(P\):

иначе Напредуј у \(Q\)

док се не изврши \(2(m+n)\) итерација

// саме многоугаоне линије немају пресек, проверити да ли је један многоугао подскуп другог

Изабери произвољно теме \(A_p\) многоугла \(P\) и теме \(B_q\) многоугла \(Q\)

ако је \(A_p \in Q\): врати \(P\) као резултат

иначе, ако је \(B_q \in P\): врати \(Q\) као резултат

иначе: врати празну листу као резултат

функција Напредуј у \(P\):

ако је \(P\) унутрашњи многоугао, додај \(A_p\) у резултат

увећај \(p\)

функција Напредуј у \(Q\):

ако је \(Q\) унутрашњи многоугао, додај \(B_q\) у резултат

увећај \(q\)