Ивановский С.А., Преображенский А.С. Алгоритмы вычислительной геометрии. Выпуклые оболочки: простые алгоритмы

Èâàíîâñêèé Ñ.À., Ïðåîáðàæåíñêèé À.Ñ., Ñèìîí÷èê Ñ.Ê.

Èâàíîâñêèé Ñåðãåé Àëåêñååâè÷,

Ïðåîáðàæåíñêèé Àëåêñåé Ñåìåíîâè÷,

Ñèìîí÷èê Ñåðãåé Êîíñòàíòèíîâè÷

ÀËÃÎÐÈÒÌÛ ÂÛ×ÈÑËÈÒÅËÜÍÎÉ ÃÅÎÌÅÒÐÈÈ.

ÂÛÏÓÊËÛÅ ÎÁÎËÎ×ÊÈ: ÏÐÎÑÒÛÅ ÀËÃÎÐÈÒÌÛ

1. ÂÂÅÄÅÍÈÅ

Âû÷èñëèòåëüíàÿ ãåîìåò-

ðèÿ  ýòî î÷åíü èíòåðåñíàÿ

è ñðàâíèòåëüíî ìîëîäàÿ îá-

ëàñòü êîìïüþòåðíîé íàóêè,

íàõîäÿùàÿñÿ íà ñòûêå èí-

ôîðìàòèêè è ãåîìåòðèè è ñî-

÷åòàþùàÿ ãåîìåòðè÷åñêèå ïîíÿòèÿ, èäåè è

ìîäåëè ñ ïîíÿòèÿìè, èäåÿìè è ìåòîäàìè ðàç-

ðàáîòêè àëãîðèòìîâ è ñòðóêòóð äàííûõ.

Ñî âðåìåí Åâêëèäà (III âåê äî íàøåé ýðû)

ãåîìåòðè÷åñêèå ïîñòðîåíèÿ áûëè ñóùå-

ñòâåííîé ÷àñòüþ è ýôôåêòèâíûì ñðåäñòâîì

êàê ãåîìåòðè÷åñêèõ èññëåäîâàíèé, òàê è ãåî-

ìåòðè÷åñêîé ïåäàãîãèêè. Êëàññè÷åñêèé ïðè-

ìåð ïðåäñòàâëÿþò ñîáîé çàäà÷è íà ïîñòðîå-

íèå: ïîñòðîèòü òðåóãîëüíèê ïî òðåì äàííûì

åãî ñòîðîíàì, ðàçäåëèòü äàííûé óãîë ïîïî-

ëàì, èç äàííîé òî÷êè îïóñòèòü ïåðïåíäèêó-

ëÿð íà äàííóþ ïðÿìóþ, ðàçäåëèòü ïîïîëàì

äàííûé îòðåçîê [4].

Ãåîìåòðè÷åñêèå ïîñòðîåíèÿ, ïî ñóòè

äåëà, ÿâëÿþòñÿ çà÷àòêàìè àëãîðèòìè÷åñêîé

íàóêè. Äåéñòâèòåëüíî, â çàäà÷àõ íà ïîñòðî-

åíèå ïî çàäàííûì ãåîìåòðè÷åñêèì îáúåê-

òàì (òî÷êàì, ïðÿìûì, îòðåçêàì è îêðóæíî-

ñòÿì), òî åñòü ïî èñõîäíûì äàííûì, òðåáó-

åòñÿ ïîñòðîèòü äðóãèå ãåîìåòðè÷åñêèå îáúåê-

òû, òî åñòü âûõîäíûå äàííûå, èñïîëüçóÿ äëÿ

ýòîãî ôèêñèðîâàííûé íàáîð èíñòðóìåíòîâ

(áàçîâûõ îïåðàöèé èëè ïðèìèòèâîâ), êîòî-

ðûìè ìîãóò áûòü, íàïðèìåð, öèðêóëü è ëè-

íåéêà, èëè òîëüêî öèðêóëü [3], èëè òîëüêî

ëèíåéêà. Ó ãåîìåòðè÷åñêèõ ïîñòðîåíèé ñó-

ùåñòâóåò òàêæå ïîíÿòèå ñëîæíîñòè, ââå-

äåííîå Ýìèëåì Ëåìóàíîì â 1902 ãîäó è îç-

íà÷àþùåå ìèíèìàëüíîå êîëè÷åñòâî ïðèìå-

íåíèé áàçîâûõ îïåðàöèé, íåîáõîäèìîå äëÿ

äàííîãî ïîñòðîåíèÿ.

Ïîÿâëåíèå êîìïüþòåðîâ è çàòåì áóð-

íîå ðàçâèòèå êîìïüþòåðíîé íàóêè (èíôîð-

ìàòèêè) îòêðûëî âîçìîæíîñòü ñèìáèîçà

÷èñòî ãåîìåòðè÷åñêîé ïðèðîäû çàäà÷ íà ïî-

ñòðîåíèå ñ àíàëèòè÷åñêèì (âû÷èñëèòåëü-

íûì) ïîäõîäîì ê èõ ðåøåíèþ, ÷òî, â ñâîþ

î÷åðåäü, ïðèâåëî ê âîçìîæíîñòè ðåøåíèÿ

íîâîãî êëàññà çàäà÷, êîòîðûìè è çàíèìàåò-

ñÿ âû÷èñëèòåëüíàÿ ãåîìåòðèÿ.

Â ýòèõ çàäà÷àõ èñõîäíûìè äàííûìè ÿâ-

ëÿþòñÿ ãåîìåòðè÷åñêèå îáúåêòû (íàïðèìåð,

ìíîæåñòâî òî÷åê, íàáîð îòðåçêîâ, ìíîãî-

óãîëüíèê), à ðåçóëüòàòîì ìîæåò ÿâëÿòüñÿ:

 îòâåò íà âîïðîñ î íåêîòîðûõ îòíîøå-

íèÿõ ìåæäó çàäàííûìè îáúåêòàìè (íàïðè-

ìåð, ïåðåñåêàþòñÿ ëè çàäàííûå îòðåçêè);

 ïåðå÷èñëåíèå ôàêòîâ îòíîñèòåëüíî

ýòèõ îòíîøåíèé (íàïðèìåð, ïåðå÷èñëåíèå

âñåõ ïàð ïåðåñåêàþùèõñÿ îòðåçêîâ);

 ïîñòðîåíèå íîâîãî ãåîìåòðè÷åñêîãî

îáúåêòà (íàïðèìåð, íàèìåíüøåãî âûïóêëî-

ãî ìíîãîóãîëüíèêà, ñîäåðæàùåãî çàäàííûå

òî÷êè).

Àëãîðèòìû âû÷èñëèòåëüíîé ãåîìåòðèè.

Âûïóêëûå îáîëî÷êè: ïðîñòûå àëãîðèòìû

ÈÍÔÎÐÌÀÒÈÊÀ

Ïðè÷åì âàæíî, ÷òî êàê ðàçìåð èñõîä-

íûõ äàííûõ (÷èñëî çàäàííûõ ãåîìåòðè÷åñ-

êèõ îáúåêòîâ), òàê è ðàçìåð ïîëó÷åííîãî

îòâåòà (ïåðå÷èñëåíèÿ èëè íîâîãî ãåîìåò-

ðè÷åñêîãî îáúåêòà) ìîãóò áûòü ïðîèçâîëü-

íûìè è, êàê ïðàâèëî, äîñòàòî÷íî áîëü-

øèìè.

Âû÷èñëèòåëüíàÿ ãåîìåòðèÿ íàõîäèò ïðè-

ìåíåíèå âî ìíîãèõ îáëàñòÿõ íàóêè è òåõ-

íèêè, òàêèõ êàê [5]:

 êîìïüþòåðíàÿ ãðàôèêà è âèçóàëèçàöèÿ;

 êîìïüþòåðíîå çðåíèå è ðîáîòîòåõíèêà;

 ãåîãðàôè÷åñêèå èíôîðìàöèîííûå ñè-

ñòåìû (ÃÈÑ);

 ñèñòåìû àâòîìàòèçèðîâàííîãî ïðîåê-

òèðîâàíèÿ (ÑÀÏÐ);

 êîìïüþòåðíûé àíàëèç è èíòåðïðåòà-

öèÿ äàííûõ (íàïðèìåð, êîìïüþòåðíàÿ òî-

ìîãðàôèÿ);

 ìîëåêóëÿðíàÿ áèîëîãèÿ;

 àñòðîôèçèêà.

2.1. ÂÛÏÓÊËÀß ÎÁÎËÎ×ÊÀ

È ÂÛÏÓÊËÎÅ ÌÍÎÆÅÑÒÂÎ

Çàäà÷à ïîñòðîå-

íèÿ âûïóêëîé îáîëî÷-

êè íå òîëüêî ÿâëÿåò-

ñÿ öåíòðàëüíîé â öå-

ëîì ðÿäå ïðèëîæå-

íèé, íî è ïîçâîëÿåò

ðàçðåøèòü ðÿä âîïðîñîâ âû-

÷èñëèòåëüíîé ãåîìåòðèè, íà

ïåðâûé âçãëÿä íå ñâÿçàííûõ ñ íåé. Ïîñòðî-

åíèå âûïóêëîé îáîëî÷êè êîíå÷íîãî ìíîæå-

ñòâà òî÷åê, îñîáåííî â ñëó÷àå òî÷åê íà ïëîñ-

êîñòè, óæå äîâîëüíî øèðîêî è ãëóáîêî èñ-

ñëåäîâàíî è èìååò ïðèëîæåíèÿ, íàïðèìåð

â ðàñïîçíàâàíèè îáðàçîâ, îáðàáîòêå èçîá-

ðàæåíèé, à òàêæå ïðè ðàñêðîå è êîìïîíîâ-

êå ìàòåðèàëà. Ìû áóäåì ðàññìàòðèâàòü ýòó

çàäà÷ó íà ïëîñêîñòè.

Åñëè íàì çàäàíî ìíîæåñòâî òî÷åê Q, òî

åãî âûïóêëàÿ îáîëî÷êà CH(Q)  ýòî íàè-

ìåíüøåå âûïóêëîå ìíîæåñòâî, âêëþ÷àþùåå

â ñåáÿ âñå ýòè òî÷êè. Âûïóêëûì íàçûâàåòñÿ

ìíîæåñòâî òî÷åê, â êîòîðîì âûïîëíÿåòñÿ

ñëåäóþùåå ïðàâèëî: åñëè êàêèå-òî äâå òî÷-

êè ïðèíàäëåæàò ìíîæåñòâó, òî è ñîåäèíÿþ-

ùèé èõ îòðåçîê ïðèíàäëåæèò ýòîìó æå

ìíîæåñòâó (ðèñ. 2.1).

Ðèñ. 2.1. Ïðèìåð âûïóêëîãî (à)

è íåâûïóêëîãî (á) ìíîæåñòâà

×òîáû íàãëÿäíî ïðåäñòàâèòü ýòî ïîíÿ-

òèå â ñëó÷àå, êîãäà Q  êîíå÷íîå ìíîæå-

ñòâî òî÷åê íà ïëîñêîñòè, ïðåäïîëîæèì, ÷òî

ýòî ìíîæåñòâî îõâà÷åíî áîëüøîé ðàñòÿíó-

òîé ðåçèíîâîé ëåíòîé. Êîãäà ëåíòà îñâî-

áîæäàåòñÿ, òî îíà ïðèíèìàåò ôîðìó ãðàíè-

öû âûïóêëîé îáîëî÷êè.

Åùå îäíèì ïîíÿòèåì, êîòîðîå íàì ïî-

íàäîáèòñÿ, ÿâëÿåòñÿ ïîíÿòèå êðàéíåé òî÷-

êè. Òî÷êà p âûïóêëîãî ìíîæåñòâà R íàçû-

âàåòñÿ êðàéíåé, åñëè íå ñóùåñòâóåò ïàðû

òî÷åê a, b

∈

R òàêèõ, ÷òî p ëåæèò íà îò-

êðûòîì îòðåçêå (a, b). Íåñëîæíî äîãàäàòü-

ñÿ, ÷òî âûïóêëàÿ îáîëî÷êà êîíå÷íîãî ìíî-

æåñòâà òî÷åê íà ïëîñêîñòè ÿâëÿåòñÿ âûïóê-

ëûì ìíîãîóãîëüíèêîì, âñå âåðøèíû êîòî-

ðîãî ïðèíàäëåæàò èñõîäíîìó ìíîæåñòâó òî-

÷åê (è ÿâëÿþòñÿ êðàéíèìè òî÷êàìè âûïóê-

ëîé îáîëî÷êè). Â ñâîþ î÷åðåäü, ñòîðîíû

ýòîãî ìíîãîóãîëüíèêà (íàçûâàåìûå òàêæå

ðåáðàìè ìíîãîóãîëüíèêà) îáðàçóþò ãðàíè-

öó âûïóêëîé îáîëî÷êè (ðèñ. 2.2).

Çàìåòèì, ÷òî äëÿ ëþáîãî ðåáðà âûïóê-

ëîé îáîëî÷êè (ìíîãîóãîëüíèêà) ÷àñòü òî-

÷åê èñõîäíîãî ìíîæåñòâà áóäåò ëåæàòü íà

äàííîì ðåáðå (íàïðèìåð, êîíöû ýòîãî ðåá-

ðà), à îñòàâøèåñÿ òî÷êè ïî îäíó ñòîðîíó

îò ñîäåðæàùåé ðåáðî ïðÿìîé (ïîïðîáóéòå

äîêàçàòü ýòî óòâåðæäåíèå ñàìîñòîÿòåëüíî).

Âåðíî è îáðàòíîå óòâåðæäåíèå åñëè äëÿ

îòðåçêà, ñîåäèíÿþùåãî äâå òî÷êè èñõîäíî-

ãî ìíîæåñòâà, ÷àñòü òî÷åê èñõîäíîãî ìíî-

æåñòâà ëåæèò íà íåì, à îñòàâøèåñÿ òî÷êè

ïî îäíó ñòîðîíó îò ñîäåðæàùåé îòðåçîê

ïðÿìîé, òî äàííûé îòðåçîê ÿâëÿåòñÿ ðåá-

ðîì âûïóêëîé îáîëî÷êè (ðèñ. 2.3).

Âûïóêëûå ìíîãîóãîëüíèêè ïðèíÿòî çà-

äàâàòü ïîñëåäîâàòåëüíîñòüþ âåðøèí â ïî-

ðÿäêå îáõîäà ïî ÷àñîâîé ñòðåëêå èëè ïðî-

á)

Èâàíîâñêèé Ñ.À., Ïðåîáðàæåíñêèé À.Ñ., Ñèìîí÷èê Ñ.Ê.

Ðèñ. 2.3. Ñâîéñòâî ðåáåð âûïóêëîé îáîëî÷êè

òèâ ÷àñîâîé ñòðåëêè. Íàïðèìåð, äëÿ âûïóê-

ëîãî ìíîãîóãîëüíèêà, ïðèâåäåííîãî íà ðè-

ñóíêå 2.4, ïîñëåäîâàòåëüíîñòü âåðøèí

FEDCBA ÿâëÿåòñÿ åãî îáõîäîì ïî ÷àñîâîé

ñòðåëêå, à ïîñëåäîâàòåëüíîñòü ABCDEF

îáõîäîì ïðîòèâ ÷àñîâîé ñòðåëêè.

Äàëåå áóäåò ðàññìîòðåíî íåñêîëüêî àë-

ãîðèòìîâ ïîñòðîåíèÿ âûïóêëîé îáîëî÷êè.

Äëÿ âñåõ ýòèõ àëãîðèòìîâ èñêîìîé âûïóê-

ëîé îáîëî÷êîé áóäåì ñ÷èòàòü âûïóêëûé

ìíîãîóãîëüíèê, çàäàííûé ïîñëåäîâàòåëüíî-

ñòüþ ñâîèõ âåðøèí â ïîðÿäêå îáõîäà ïðî-

òèâ ÷àñîâîé ñòðåëêè.

2.2. ÀËÃÎÐÈÒÌ

ÇÀÂÎÐÀ×ÈÂÀÍÈß ÏÎÄÀÐÊÀ

Â íåêîòîðîì öàðñòâå,

â íåêîòîðîì ãîñóäàðñòâå

êîðîëü ïðèêàçàë ñâîåìó

ñàäîâíèêó îãðàäèòü ñâîé

ñàä îò ïîñÿãàíèé ó÷åíè-

êîâ áëèçëåæàùåé øêî-

ëû. Ó ñàäîâíèêà åñòü äî-

ñòàòî÷íî äëèííàÿ âåðåâêà, è îí íàìåðåâà-

åòñÿ èñïîëüçîâàòü åå â êà÷åñòâå îãðàæäå-

íèÿ. Ñàäîâíèêó íóæíî ïîñòðîèòü èçãîðîäü

òàê, ÷òîáû êàê ìîæíî áîëüøóþ ïëîùàäü

îãîðîäèòü è êàê ìîæíî ìåíüøå âåðåâêè ïðè

ýòîì ïîòðàòèòü. Âåðåâêó ìîæíî ïðèâÿçû-

âàòü òîëüêî ê ñòâîëàì äåðåâüåâ ñàäà.

Íåñëîæíî äîãàäàòüñÿ, ÷òî ñàäîâíèê äîë-

æåí ïîñòðîèòü íå ÷òî èíîå êàê âûïóêëóþ

îáîëî÷êó ìíîæåñòâà òî÷åê. Òî÷êàìè â äàí-

íîì ñëó÷àå ÿâëÿþòñÿ äåðåâüÿ (åñëè ñìîò-

ðåòü íà íèõ ñ âûñîòû ïòè÷üåãî ïîëåòà).

×òîáû ðåøèòü ýòó çàäà÷ó, ñàäîâíèê áó-

äåò äåéñòâîâàòü â ñîîòâåòñòâèè ñî ñëåäóþ-

ùåé ñòðàòåãèåé: ñíà÷àëà îí íàéäåò òàêîå äå-

ðåâî, êîòîðîå òî÷íî áóäåò âêëþ÷åíî â èçãî-

ðîäü (îíî áóäåò ÿâëÿòüñÿ êðàéíåé òî÷êîé

âûïóêëîé îáîëî÷êè), è çàêðåïèò íà íåì âå-

ðåâêó, à çàòåì íà÷íåò îáõîäèòü ñàä êðóãîì

(íàïðèìåð, ïðîòèâ ÷àñîâîé ñòðåëêè), äåðæà

â ðóêàõ íàòÿíóòóþ âåðåâêó. Êîãäà îí ñäåëà-

åò ïîëíûé êðóã, ñàä óæå áóäåò îãîðîæåí. Ýòîò

ïðîöåññ ïðîèëëþñòðèðîâàí íà ðèñóíêå 2.5.

Îêàçûâàåòñÿ, èäåÿ, èñïîëüçîâàííàÿ ñà-

äîâíèêîì äëÿ ðåøåíèÿ äàííîé çà-

äà÷è, ëåæèò â îñíîâå àëãîðèòìà

çàâîðà÷èâàíèÿ ïîäàðêà, èëè îáõî-

äà Äæàðâèñà [2] (àëãîðèòì íàçû-

âàåòñÿ òàê â ÷åñòü ñâîåãî àâòîðà

Ðýÿ Äæàðâèñà, êîòîðûé ïðèäóìàë

åãî â 1973 ãîäó).

Íà ñàìîì äåëå, äëÿ òîãî ÷òîáû

îïèñàííûé ñïîñîá äåéñòâèÿ ñòàë

àëãîðèòìîì, åãî íàäî ôîðìàëèçî-

âàòü, òî åñòü çàïèñàòü òàê, ÷òîáû

åãî ìîã âûïîëíèòü ðîáîò, à íå òîëü-

êî ÷åëîâåê.

à)

á)

Ðèñ. 2.2. Èñõîäíîå ìíîæåñòâî òî÷åê (à) è åãî âûïóêëàÿ îáîëî÷êà (á)

êðàéíÿÿ òî÷êà

ãðàíèöà âûïóêëîé îáîëî÷êè

(âûïóêëûé ìíîãîóãîëüíèê)

á)

íå êðàéíÿÿ òî÷êà

CH(Q)

Àëãîðèòìû âû÷èñëèòåëüíîé ãåîìåòðèè.

Âûïóêëûå îáîëî÷êè: ïðîñòûå àëãîðèòìû

ÈÍÔÎÐÌÀÒÈÊÀ

Ðèñ. 2.4. Îáõîäû âûïóêëîãî ìíîãîóãîëüíèêà

Ðèñ. 2.5. Ïðîöåññ «çàâîðà÷èâàíèÿ»

Ïóñòü â ïàìÿòè ðîáîòà çàäàíà êàðòà

ñàäà, ãäå äåðåâüÿ îáîçíà÷åíû òî÷êàìè

íà ïëîñêîñòè è êàæäàÿ òî÷êà èìååò

ïàðó êîîðäèíàò. Îáîçíà÷èì îáùåå

êîëè÷åñòâî äåðåâüåâ çà n, òîãäà êîîð-

äèíàòàìè äåðåâà ñ íîìåðîì i áóäåò

ïàðà ÷èñåë p

=(x

, y

), ãäå x

 àáñöèñ-

ñà òî÷êè, ñîîòâåòñòâóþùåé äåðåâó, à

 îðäèíàòà ýòîé òî÷êè, ïðè ýòîì i

ìîæåò ïðèíèìàòü çíà÷åíèÿ îò 1 äî n.

Òîãäà íàø (ïîêà åùå íåôîðìàëü-

íûé) àëãîðèòì âûãëÿäèò òàê (ñì. ëèñ-

òèíã 1).

ABCDEF

FEDCBA

ïî ÷àñîâîé ñòðåëêå:

ïðîòèâ ÷àñîâîé ñòðåëêè:

Ëèñòèíã 1. algorithm JARVIS-MARCH(Q) → CH(Q)

Âõîä. Èñõîäíîå ìíîæåñòâî òî÷åê Q = {p

| p

= (x

, y

), i ∈ [1..n]}.

Âûõîä. Âûïóêëàÿ îáîëî÷êà ìíîæåñòâà òî÷åê CH(Q), çàäàííàÿ ïîñëåäîâàòåëüíîñòüþ

âåðøèí (ïåðå÷èñëåííûõ â ïîðÿäêå îáõîäà ïðîòèâ ÷àñîâîé ñòðåëêè).

1 Èíèöèàëèçèðèðîâàòü âûïóêëóþ îáîëî÷êó ïóñòîé ïîñëåäîâàòåëüíîñòüþ òî÷åê

2 Âûáðàòü ïåðâóþ òî÷êó, êîòîðàÿ áóäåò ÿâëÿòüñÿ êðàéíåé òî÷êîé âûïóêëîé îáîëî÷êè

3 Ñäåëàòü ïîëíûé êðóã âîêðóã ìíîæåñòâà òî÷åê, «çàâîðà÷èâàÿ» âîêðóã íåãî ðåáðà

âûïóêëîé îáîëî÷êè

Èâàíîâñêèé Ñ.À., Ïðåîáðàæåíñêèé À.Ñ., Ñèìîí÷èê Ñ.Ê.

Ðàñ-

ñìîòðèì âòîðóþ ñòðîêó àëãîðèòìà JARVIS-

MARCH. Â íåé ãîâîðèòñÿ, ÷òî ìû äîëæíû

âûáðàòü ïåðâóþ òî÷êó òàê, ÷òîáû îíà ÿâ-

ëÿëàñü âåðøèíîé âûïóêëîé îáîëî÷êè. Îêà-

çûâàåòñÿ, ÷òî òî÷êà, èìåþùàÿ íàèìåíüøóþ

àáñöèññó èç âñåõ òî÷åê, êîòîðûå èìåþò íàè-

ìåíüøóþ îðäèíàòó, ÿâëÿåòñÿ êðàéíåé òî÷-

êîé âûïóêëîé îáîëî÷êè (ïîïðîáóéòå äî-

êàçàòü ýòî óòâåðæäåíèå ñàìîñòîÿòåëüíî)

(ðèñ. 2.6).

Ó÷èòûâàÿ ýòîò ôàêò, ìîæíî äåòàëèçè-

ðîâàòü âòîðóþ ñòðîêó àëãîðèòìà JARVIS-

MARCH ñëåäóþùèì îáðàçîì (ëèñòèíã 2).

Òåïåðü äåòàëèçèðóåì ïðîöåññ «çàâîðà-

÷èâàíèÿ» ðåáåð âûïóêëîé îáîëî÷êè âîêðóã

ìíîæåñòâà òî÷åê. Áóäåì èñïîëüçîâàòü çà-

ïèñü [p

, p

] äëÿ îáîçíà÷åíèÿ îðèåíòèðî-

âàííîãî îòðåçêà, íàïðàâëåííîãî èç òî÷êè p

(íàçûâàåìîé íà÷àëîì îðèåíòèðîâàííîãî

îòðåçêà) â òî÷êó p

(íàçûâàåìóþ êîíöîì îðè-

åíòèðîâàííîãî îòðåçêà) (ëèñòèíã 3).

Çäåñü p

current

 òåêóùàÿ (ïîñëåäíÿÿ íàé-

äåííàÿ) âåðøèíà âûïóêëîé îáîëî÷êè, à p



ñëåäóþùàÿ çà íåé âåðøèíà âûïóêëîé îáî-

ëî÷êè (â íàïðàâëåíèè îáõîäà ïðîòèâ ÷àñî-

âîé ñòðåëêè). Çàïèñü A

DDVERTEX(p

current

)

äîáàâëÿåò òî÷êó p

current

= (x

current

, y

current

) â

êîíåö ïîñëåäîâàòåëüíîñòè òî÷åê, ïðåäñòàâ-

ëÿþùåé ñîáîé îáõîä âûïóêëîé îáîëî÷êè

ïðîòèâ ÷àñîâîé ñòðåëêè.

Ïóñòü p

current

ÿâëÿåòñÿ ïîñëåäíåé íàéäåí-

íîé âåðøèíîé âûïóêëîé îáîëî÷êè, à

 ïðåäïîñëåäíåé íàéäåííîé. Ðàñ-

ñìîòðèì ëó÷ l, èñõîäÿùèé èç âåðøèíû p

current

â òîì æå íàïðàâëåíèè, ÷òî è îðèåíòèðî-

âàííûé îòðåçîê [p

, p

current

] (â ñëó÷àå,

êîãäà ìû íàõîäèìñÿ íà ïåðâîì øàãå àëãî-

ðèòìà, ðàññìîòðèì â êà÷åñòâå l ãîðèçîíòàëü-

íûé ëó÷, èñõîäÿùèé èç âåðøèíû p

start

è íà-

ïðàâëåííûé â ñòîðîíó óâåëè÷åíèÿ àáñöèññ).

Çàìåòèì, ÷òî âñå îñòàëüíûå òî÷êè ëåæàò

ëèáî íà ïðÿìîé, ñîäåðæàùåé ëó÷, ëèáî ïî

ëåâóþ ñòîðîíó îò íåãî. Çàôèêñèðóåì ïðî-

èçâîëüíóþ òî÷êó t íà ýòîì ëó÷å, íå ñîâïà-

äàþùóþ ñ p

current

. Òîãäà ëþáîé òî÷êå p

ìíî-

æåñòâà Q \ {p

current

} áóäåò ñîîòâåòñòâîâàòü

óãîë ∠p

current

t, ëåæàùèé â äèàïàçîíå

(0;

]. Ýòîò óãîë íàçûâàåòñÿ ïîëÿðíûì óã-

ëîì òî÷êè p

îòíîñèòåëüíî ëó÷à l.

Òåïåðü ïîñòàâëåííóþ ïåðåä íàìè çàäà÷à

â ñòðîêå 3.4 àëãîðèòìà J

ARVIS-MARCH ìîæ-

íî ïåðåôîðìóëèðîâàòü ñëåäóþùèì îáðàçîì:

Íàéòè òàêóþ òî÷êó p

, ÷òîáû óãîë

∠p

current

t áûë ìèíèìàëüíûì.

start

Ðèñ. 2.6. Íà÷àëüíàÿ òî÷êà p

start

Ëèñòèíã 2.

2.1 p

start

←

2.2 for

∀

= (x

, y

)

∈

Q do

2.3 if (y

< y

start

) or ((y

= y

start

) and (x

< x

start

)) then

2.4 p

start

←

2.5 end-if

2.6 end-do

Ëèñòèíã 3.

3.1 p

current

←

start

3.2 do

3.3 ADDVERTEX(p

current

)

3.4 Íàéòè òàêóþ âåðøèíó p

, ÷òîáû îíà ÿâëÿëàñü ñëåäóþùåé ïîñëå p

current

âåðøè-

íîé âûïóêëîé îáîëî÷êè (â íàïðàâëåíèè îáõîäà ïðîòèâ ÷àñîâîé ñòðåëêè), òî

åñòü ëþáàÿ òî÷êà èñõîäíîãî ìíîæåñòâà ëåæàëà áû ïî ëåâóþ ñòîðîíó îò îðèåí-

òèðîâàííîãî îòðåçêà [p

current

, p

] èëè íà íåì

3.5 p

current

←

3.6 while p

current

≠

start

Àëãîðèòìû âû÷èñëèòåëüíîé ãåîìåòðèè.

Âûïóêëûå îáîëî÷êè: ïðîñòûå àëãîðèòìû

ÈÍÔÎÐÌÀÒÈÊÀ

Ðèñ. 2.8. Äëÿ òàêîãî ñëó÷àÿ S(p

, p

) áóäåò

èìåòü îòðèöàòåëüíûé çíàê

Íåñêîëüêî øàãîâ îïèñàííîãî àëãîðèò-

ìà ïðîèëëþñòðèðîâàíû íà ðèñóíêå 2.7.

Ìîæíî ðåàëèçîâûâàòü äàííûé àëãîðèòì,

èñïîëüçóÿ íåïîñðåäñòâåííîå âû÷èñëåíèå

óêàçàííûõ óãëîâ ñ öåëüþ èõ ïîñëåäóþùåãî

ñðàâíåíèÿ äëÿ íàõîæäåíèÿ íàèìåíüøåãî.

Îäíàêî íåïîñðåäñòâåííîå âû÷èñëåíèå óãëîâ

ñðàçó æå ïîäðàçóìåâàåò èñïîëüçîâàíèå âå-

ùåñòâåííûõ ÷èñåë è îáðàòíûõ òðèãîíîìåò-

ðè÷åñêèõ îïåðàöèé. Íà ñàìîì äåëå, ýòó

çàäà÷ó ìîæíî ðåøèòü, èñïîëüçóÿ òîëüêî

îïåðàöèè óìíîæåíèÿ, ñëîæåíèÿ è ñðàâíå-

íèÿ. Ïðè ýòîì, åñëè èñõîäíûå äàííûå çàäà-

÷è öåëî÷èñëåííûå, âñå ïðîèçâîäèìûå âû-

÷èñëåíèÿ íå âûâåäóò çà ðàìêè îïåðàöèé ñ

öåëûìè ÷èñëàìè. Äëÿ ýòîãî, íóæíî èñïîëü-

çîâàòü ïîíÿòèå îðèåíòèðîâàííîé ïëîùàäè

òðåóãîëüíèêà. Ðàññìîòðèì ñëåäóþùóþ ïîä-

çàäà÷ó:

Äëÿ îðèåíòèðîâàííîãî îòðåçêà [p

, p

]

è òî÷êè p

îïðåäåëèòü, ëåæèò ëè òî÷êà p

íà ïðÿìîé, ñîäåðæàùåé äàííûé îòðåçîê, è

åñëè íåò, òî ïî ëåâóþ èëè ïî ïðàâóþ ñòî-

ðîíó îò íåãî îíà ëåæèò.

×òîáû åå ðåøèòü, ðàññìîòðèì âûðà-

æåíèå:

))([(

)(

acabcba

yyxxp,p,pS

−−−=

)])((

acab

xxyy

−−

−

Â äàëüíåéøåì îò äàííîãî âûðàæåíèÿ

ïîòðåáóåòñÿ òîëüêî åãî çíàê, ïîýòîìó ìíî-

æèòåëü 1/2 ìîæíî îïóñòèòü (ðèñ. 2.8).

Îêàçûâàåòñÿ (ñì. ïðèëîæåíèå), âûðàæå-

íèå S (p

, p

) ïðåäñòàâëÿåò ñîáîé òàê

íàçûâàåìóþ îðèåíòèðîâàííóþ ïëîùàäü òðå-

óãîëüíèêà

∆

. Àáñîëþòíàÿ âåëè÷èíà

S (p

, p

) ðàâíà ïëîùàäè òðåóãîëüíèêà

∆

. Â ñëó÷àå, êîãäà òî÷êà p

ëåæèò ïî

ëåâóþ ñòîðîíó îò îðèåíòèðîâàííîãî îòðåç-

êà [p

, p

], ïëîùàäü èìååò ïîëîæèòåëüíûé

çíàê, â ñëó÷àå, êîãäà òî÷êà p

ëåæèò ïî ïðà-

âóþ ñòîðîíó îò îðèåíòèðîâàííîãî îòðåçêà

, p

],  çíàê ïëîùàäè îòðèöàòåëüíûé,

åñëè æå òî÷êè p

, p

è p

ëåæàò íà îäíîé

ïðÿìîé, ïëîùàäü ðàâíà íóëþ.

Äëÿ òîãî ÷òîáû â ñòðîêå 3.4 àëãîðèòìà

ARVIS-MARCH íàéòè òî÷êó p

, èìåþùóþ

ìèíèìàëüíûé óãîë, òî åñòü òî÷êó, êîòîðàÿ

áû ÿâëÿëàñü âåðøèíîé âûïóêëîé îáîëî÷êè,

è ëþáàÿ òî÷êà èñõîäíîãî ìíîæåñòâà ëåæà-

ëà ïî ëåâóþ ñòîðîíó îò îðèåíòèðîâàííîãî

îòðåçêà [p

current

, p

] èëè íà íåì, áóäåì äåé-

ñòâîâàòü â ñîîòâåòñòâèè ñî ñëåäóþùèì àë-

ãîðèòìîì.

Ðèñ. 2.7. Íåñêîëüêî øàãîâ àëãîðèòìà JARVIS-MARCH

start

current

start

current

p x

ccc

()

p x,

(

)

p x

()

Èâàíîâñêèé Ñ.À., Ïðåîáðàæåíñêèé À.Ñ., Ñèìîí÷èê Ñ.Ê.

Áóäåì ïîñòåïåííî ïîäáèðàòü èñêîìóþ

òî÷êó p

èç òî÷åê èñõîäíîãî ìíîæåñòâà

Q, îòáðàñûâàÿ íà êàæäîì øàãå îäèí çàâå-

äîìî íåïîäõîäÿùèé äëÿ íåå âàðèàíò. Ñíà-

÷àëà ïîëîæèì p

ðàâíîé ëþáîé òî÷êå èñ-

õîäíîãî ìíîæåñòâà. Áóäåì ïåðåáèðàòü âñå

òî÷êè èñõîäíîãî ìíîæåñòâà. Ïóñòü íà êà-

êîì-òî øàãå ïåðåáîðà ìû ðàññìàòðèâàåì

òî÷êó p

. Òîãäà äîëæíî âûïîëíèòüñÿ îäíî

èç òðåõ óñëîâèé:

1) p

ëåæèò ëåâåå ÷åì [p

current

, p

]. Ýòî

îçíà÷àåò, ÷òî òî÷êà p

çàâåäîìî íå ÿâëÿåòñÿ

òîé òî÷êîé, êîòîðóþ ìû èùåì.

2) p

ëåæèò ïðàâåå ÷åì [p

current

, p

Ýòî îçíà÷àåò, ÷òî òåêóùàÿ òî÷êà p

íà

ñàìîì äåëå íå ÿâëÿåòñÿ òîé òî÷êîé, êîòî-

ðóþ ìû èùåì. Îäíàêî ìû ïîêà íå ìîæåì

ñêàçàòü òàêîãî î p

, ïîñêîëüêó âñå ðàññìîò-

ðåííûå ðàíåå òî÷êè ëåæàò èëè ëåâåå îðèåí-

òèðîâàííîãî îòðåçêà [p

current

, p

], èëè íà íåì.

Ïîýòîìó íà ýòîì øàãå ïîëîæèì p

←

3) Òðè òî÷êè p

current

, p

è p

ëåæàò íà

îäíîé ïðÿìîé. Ïðè÷åì òî÷êè p

è p

ãà-

ðàíòèðîâàííî ëåæàò ïî îäíó ñòîðîíó îò

òî÷êè p

current

íà ýòîé ïðÿìîé, ïîñêîëüêó â

ïðîòèâíîì ñëó÷àå îíà íå áûëà áû êðàéíåé

òî÷êîé âûïóêëîé îáîëî÷êè. Òîãäà âûïîë-

íÿåòñÿ îäíî èç äâóõ:

à) òî÷êà p

ëåæèò íà îòêðûòîì îòðåçêå

current

, p

) è, ñëåäîâàòåëüíî, îíà íå ìî-

æåò áûòü êðàéíåé òî÷êîé âûïóêëîé îáî-

ëî÷êè;

á) òî÷êà p

ëåæèò íà îòêðûòîì îòðåç-

êå (p

current

, p

). Ýòî îçíà÷àåò, ÷òî òåêóùàÿ

òî÷êà pnext íà ñàìîì äåëå íå ÿâëÿåòñÿ òîé

òî÷êîé, êîòîðóþ ìû èùåì. Îäíàêî ìû ïîêà

íå ìîæåì ñêàçàòü òàêîãî î p

, ïîñêîëüêó

âñå ðàññìîòðåííûå ðàíåå òî÷êè ëåæàò èëè

ëåâåå îðèåíòèðîâàííîãî îòðåçêà [p

current

, p

èëè íà íåì. Ïîýòîìó íà ýòîì øàãå ïîëî-

æèì p

←

Ïîñëå òîãî êàê â êà÷åñòâå p

ìû ïåðåáå-

ðåì âñå âîçìîæíûå òî÷êè ñ ïîìîùüþ ïðè-

âåäåííîãî àëãîðèòìà, ìû îáíàðóæèì p

ñëåäóþùóþ çà p

current

âåðøèíó âûïóêëîé

îáîëî÷êè (â íàïðàâëåíèè îáõîäà ïðîòèâ

÷àñîâîé ñòðåëêè). Àëãîðèòìè÷åñêàÿ çàïèñü

ýòîãî ïðîöåññà ïðèâåäåíà â ëèñòèíãå 4.

Çàïèñü A

REA(p

current

, p

) îçíà÷àåò âû-

÷èñëåíèå îðèåíòèðîâàííîé ïëîùàäè òðåó-

ãîëüíèêà

∆

current

Çàïèñü LENGTH(p

, p

current

) îçíà÷àåò âû-

÷èñëåíèå äëèíû îòðåçêà [p

, p

current

Òåïåðü ïðîàíàëèçèðóåì ñëîæíîñòü ðà-

áîòû àëãîðèòìà Äæàðâèñà. Îáîçíà÷èì êî-

ëè÷åñòâî òî÷åê èñõîäíîãî ìíîæåñòâà Q,

ÿâëÿþùèõñÿ âåðøèíàìè âûïóêëîé îáîëî÷-

êè, ÷åðåç h. Çàìåòèì, ÷òî öèêë while â ñòðî-

êàõ 3.23.6 àëãîðèòìà J

ARVIS-MARCH âû-

ïîëíÿåòñÿ â òî÷íîñòè h ðàç, à îäíà èòåðà-

öèÿ òàêîãî öèêëà òðåáóåò O(n) îïåðàöèé.

Ýòî îçíà÷àåò, ÷òî âðåìÿ âûïîëíåíèÿ àëãî-

ðèòìà Äæàðâèñà ðàâíî O(hn). Ëþáîïûòíûé

ôàêò çàêëþ÷àåòñÿ â òîì, ÷òî âðåìÿ âûïîë-

íåíèÿ äàííîãî àëãîðèòìà çàâèñèò íå òîëüêî

îò n (ðàçìåðà âõîäíûõ äàííûõ), íî è îò h

(ðàçìåðà âûõîäíûõ äàííûõ). Åñëè ìû çàðà-

íåå çíàåì, ÷òî ÷èñëî h íåâåëèêî, òî ýòîò

àëãîðèòì áóäåò î÷åíü ýôôåêòèâåí (ðèñ. 2.9).

Ðèñ. 2.9. Îäèí èç õóäøèõ ñëó÷àåâ

äëÿ àëãîðèòìà Äæàðâèñà

Ëèñòèíã 4.

3.4.1 p

←

current

3.4.2 for

∀

∈

Q | i

∈

[1..n] do

3.4.3 if (AREA(p

current

, p

) > 0) or

((AREA(p

current

, p

) = 0) and (LENGTH(p

current

, p

) < LENGTH(p

current

, p

))) then

3.4.4 p

←

3.4.5 end-if

3.4.6 end-do

Àëãîðèòìû âû÷èñëèòåëüíîé ãåîìåòðèè.

Âûïóêëûå îáîëî÷êè: ïðîñòûå àëãîðèòìû

ÈÍÔÎÐÌÀÒÈÊÀ

Ðèñ. 2.10. Òî÷êè ìíîæåñòâà Q \ {p

start

óïîðÿäî÷åííûå â ñîîòâåòñòâèè

ñ ââåäåííûì îòíîøåíèåì <

(i < j ⇒ q

< q

;

∀

i; j)

Íî òàê êàê â íåêîòîðûõ ñëó÷àÿõ âñå n

òî÷åê èñõîäíîãî ìíîæåñòâà ìîãóò áûòü âåð-

øèíàìè âûïóêëîé îáîëî÷êè (h = n), òî âðå-

ìÿ âûïîëíåíèÿ äàííîãî àëãîðèòìà â õóä-

øåì ñëó÷àå ðàâíî O(n

). Îñîáî ñòîèò îòìå-

òèòü, ÷òî ñóùåñòâóþò àëãîðèòìû äëÿ ïîñò-

ðîåíèÿ âûïóêëîé îáîëî÷êè â ïðîñòðàíñòâàõ

ðàçìåðíîñòè áîëüøå äâóõ (íàïðèìåð, â òðåõ-

ìåðíîì ñëó÷àå), èñïîëüçóþùèå òó æå èäåþ

«çàâîðà÷èâàíèÿ».

2.3. ÀËÃÎÐÈÒÌ ÃÐÝÕÅÌÀ

Â 1972 ãîäó Ðîíàëüä Ãðý-

õåì â îäíîé èç ïåðâûõ ðàáîò,

ñïåöèàëüíî ïîñâÿùåííûõ âîï-

ðîñó ðàçðàáîòêè ýôôåêòèâíûõ

ãåîìåòðè÷åñêèõ àëãîðèòìîâ,

ïîêàçàë, ÷òî, âûïîëíèâ ïðåä-

âàðèòåëüíî ñîðòèðîâêó òî÷åê,

êðàéíèå òî÷êè ìîæíî íàéòè çà

ëèíåéíîå âðåìÿ [2]. Èñïîëüçîâàííûé èì

ìåòîä ñòàë î÷åíü ìîùíûì ñðåäñòâîì â îá-

ëàñòè âû÷èñëèòåëüíîé ãåîìåòðèè.

Àëãîðèòì Ãðýõåìà èñïîëüçóåò ñòåê, â

êîòîðîì õðàíÿòñÿ òî÷êè, ÿâëÿþùèåñÿ êàí-

äèäàòàìè â âûïóêëóþ îáîëî÷êó. Êàê èçâåñ-

òíî [1], ñòåê ýòî äèíàìè÷åñêàÿ ïîñëåäîâà-

òåëüíàÿ ñòðóêòóðà äàííûõ, â êîòîðîé íå-

ïîñðåäñòâåííî äîñòóïåí òîëüêî òîò ýëåìåíò,

êîòîðûé áûë äîáàâëåí â íåãî ïîñëåäíèì. Â

äàííîì àëãîðèòìå áóäåò èñïîëüçîâàòüñÿ ìî-

äèôèêàöèÿ ñòåêà, â êîòîðîé äîñòóïíû äâà

ïîñëåäíèõ ýëåìåíòà. Íàì ïîíàäîáÿòñÿ ñëå-

äóþùèå îïåðàöèè ñî ñòåêîì (ñòåê îáîçíà-

÷åí çà S):

1) PUSH(S; e) äîáàâèòü ýëåìåíò e â

ñòåê S;

2) POP(S) óäàëèòü âåðõíèé ýëåìåíò ñòå-

êà S;

3) SIZE(S) êîëè÷åñòâî ýëåìåíòîâ, íàõî-

äÿùèõñÿ â ñòåêå S;

4) TOP(S) âåðõíèé ýëåìåíò ñòåêà S;

5) NEXT-TO-TOP(S) ýëåìåíò ñòåêà S, êî-

òîðûé ñëåäóåò çà âåðõíèì â ñòåêå;

Èòàê, ïðåäïîëîæèì, ÷òî íàéäåíà òî÷êà

start

, çàâåäîìî ÿâëÿþùàÿñÿ âåðøèíîé âû-

ïóêëîé îáîëî÷êè ìíîæåñòâà òî÷åê Q (çàäà-

÷à íàõîæäåíèÿ òàêîé òî÷êè óæå ðåøàëàñü â

àëãîðèòìå Äæàðâèñà). Óïîðÿäî÷èì îñòàëü-

íûå òî÷êè â ñîîòâåòñòâèè ñî çíà÷åíèÿìè

ïîëÿðíîãî óãëà îòíîñèòåëüíî òî÷êè p

start

êàê

íà÷àëà êîîðäèíàò (îñüþ â äàííîé ñèñòåìå

êîîðäèíàò áóäåò ãîðèçîíòàëüíûé ëó÷, èñ-

õîäÿùèé èç òî÷êè p

start

â ñòîðîíó óâåëè÷å-

íèÿ àáñöèññ), à ïðè ðàâåíñòâå ïîëÿðíûõ

óãëîâ óïîðÿäî÷èì òî÷êè ïî ðàññòîÿíèþ îò

òî÷êè p

start

Äðóãèìè ñëîâàìè ââåäåì íà îñòàâøèõñÿ

òî÷êàõ îòíîøåíèå ñòðîãîãî ïîðÿäêà <. Äëÿ

äâóõ òî÷åê p

è p

áóäåì ñ÷èòàòü p

< p

åñëè òî÷êà p

ëåæèò ïî ïðàâóþ ñòîðîíó îò

îðèåíòèðîâàííîãî îòðåçêà [p

start

, p

], ëèáî

òî÷êà p

ëåæèò íà ýòîì îòðåçêå, è äëèíà

îòðåçêà [p

start

, p

] ìåíüøå, ÷åì äëèíà îò-

ðåçêà [p

start

, p

]. Â äàííîì ñëó÷àå èñïîëü-

çîâàíèå îïðåäåëåíèÿ âçàèìíîãî ðàñïîëîæå-

íèÿ òî÷êè è îðèåíòèðîâàííîãî îòðåçêà óìå-

ñòíî, ïîñêîëüêó ïîëÿðíûå óãëû òî÷åê èç

ìíîæåñòâà Q \ {p

start

} íàõîäÿòñÿ â ïðåäåëàõ

[0;

) îòíîñèòåëüíî òî÷êè p

start

Àëãîðèòì Ãðýõåìà ñîñòîèò èç äâóõ ýòà-

ïîâ: íà ïåðâîì ýòàïå òî÷êè ñîðòèðóþòñÿ â

ñîîòâåòñòâèè ñ ââåäåííûì îòíîøåíèåì ïî-

ðÿäêà <; íà âòîðîì ýòàïå â ïðîöåññå îáõî-

äà óïîðÿäî÷åííîé ïîñëåäîâàòåëüíîñòè òî-

÷åê îòáðàñûâàþòñÿ òå òî÷êè, êîòîðûå ãà-

ðàíòèðîâàííî íå ÿâëÿþòñÿ âåðøèíàìè âû-

ïóêëîé îáîëî÷êè. Âòîðîé ýòàï àëãîðèòìà

Ãðýõåìà òàêæå íàçûâàåòñÿ îáõîäîì Ãðýõå-

ìà (ðèñ. 2.10).

Íà êàæäîì øàãå îáõîäà âûïóêëàÿ îáî-

ëî÷êà óæå ïðîéäåííûõ òî÷åê õðàíèòñÿ â

ñòåêå S, ïðè ýòîì âåðõíèé ýëåìåíò ñîîòâåò-

start

Èâàíîâñêèé Ñ.À., Ïðåîáðàæåíñêèé À.Ñ., Ñèìîí÷èê Ñ.Ê.

ñòâóåò ïîñëåäíåé îáðàáîòàííîé òî÷êå. Êîã-

äà âñå òî÷êè áóäóò îáðàáîòàíû, â ñòåêå áó-

äóò íàõîäèòüñÿ âñå òî÷êè âûïóêëîé îáî-

ëî÷êè (â ïîðÿäêå îáõîäà ïðîòèâ ÷àñîâîé

ñòðåëêè).

Äëÿ îáõîäà Ãðýõåìà êëþ÷åâûì ïîíÿòè-

åì ÿâëÿåòñÿ ïîíÿòèå ëåâîãî ïîâîðîòà.

Òðîéêà òî÷åê (p

, p

) íàçûâàåòñÿ ëå-

âûì ïîâîðîòîì, åñëè òî÷êà p

ëåæèò ñòðî-

ãî ñëåâà îò îðèåíòèðîâàííîãî îòðåçêà

, p

]. Åñëè áû ìû ïðÿìîëèíåéíî ïåðå-

ìåùàëèñü îò òî÷êè p

äî òî÷êè p

, à çàòåì

îò òî÷êè p

äî òî÷êè p

, òî â òî÷êå p

íàì

áû ïðèøëîñü ïîâåðíóòü íàëåâî, èìåííî ïî-

ýòîìó òàêîé ïîâîðîò íàçûâàåòñÿ ëåâûì.

Åñëè îáõîä ìíîãîóãîëüíèêà îñóùåñòâ-

ëÿåòñÿ ïðîòèâ ÷àñîâîé ñòðåëêè, òî ïðè äâè-

æåíèè ïî ðåáðó ñëåâà îò ðåáðà áóäåò îñòà-

âàòüñÿ âíóòðåííîñòü ìíîãîóãîëüíèêà. Íà

ðèñóíêå 2.11 çàêðàøåííàÿ îáëàñòü ñîîòâåò-

ñòâóåò âíóòðåííîñòè ìíîãîóãîëüíèêà ïðè

äâèæåíèè â íàïðàâëåíèè, óêàçàííîì ñòðåë-

êîé. Òàê êàê âûïóêëàÿ îáîëî÷êà ÿâëÿåòñÿ

âûïóêëûì ìíîãîóãîëüíèêîì ñ âåðøèíàìè â

êðàéíèõ òî÷êàõ, òî äëÿ íåå äîïóñòèìû òîëü-

êî ëåâûå ïîâîðîòû (â ñëó÷àå íà ðèñóíêå

2.11(á) òî÷êà p

íå ÿâëÿåòñÿ êðàéíåé, à â

ñëó÷àå íà ðèñóíêå 2.11(â) ìíîãîóãîëüíèê íå

áóäåò âûïóêëûì).

Äëÿ òîãî, ÷òî ïîääåðæèâàòü â ñòåêå S

âûïóêëóþ îáîëî÷êó óæå îáðàáîòàííûõ òî-

÷åê, íóæíî ïîääåðæèâàòü ñâîéñòâî, ÷òî

ëþáûå òðè ïîäðÿä èäóùèõ ýëåìåíòà ñòåêà

îáðàçóþò ëåâûé ïîâîðîò. Ïðè îáðàáîòêå

î÷åðåäíîé òî÷êè q

ýòî ñâîéñòâî ìîæåò íà-

ðóøèòüñÿ òîëüêî äëÿ òðîéêè òî÷åê

EXT-TO-TOP(S), TOP(S), q

). Åñëè òðîéêà

òî÷åê (N

EXT-TO-TOP(S), TOP(S), q

) íå îá-

ðàçóåò ëåâûé ïîâîðîò, òî íåîáõîäèìî óäà-

ëèòü âåðøèíó Top(S) èç ñòåêà, ïîñêîëüêó

îíà íå ìîæåò ÿâëÿòüñÿ âåðøèíîé âûïóêëîé

îáîëî÷êè (ñì. ðèñóíîê 2.11). Óäàëåíèå íå-

îáõîäèìî âûïîëíÿòü äî òåõ ïîð, ïîêà â ñòåêå

íå îñòàíåòñÿ îäèí ýëåìåíò èëè ïîêà òðîé-

êà òî÷åê (Next-To-Top(S), Top(S), q

) íå îá-

ðàçóåò ëåâûé ïîâîðîò. Â êîíöå øàãà â ñòåê

äîáàâëÿåòñÿ îáðàáàòûâàåìàÿ òî÷êà q

Çàïèøåì àëãîðèòì ôîðìàëüíî (ëèñ-

òèíã 5).

Âî âòîðîé ñòðîêå àëãîðèòìà ìû íàõî-

äèì òî÷êó p

start

; âñå îñòàëüíûå òî÷êè ìíî-

æåñòâà Q íàõîäÿòñÿ âûøå íå (èëè íà îä-

íîì óðîâíå, íî ïðàâåå), è ïîòîìó îíà çàâå-

äîìî âõîäèò â CH(Q). Â òðåòüåé ñòðîêå

îñòàâøèåñÿ òî÷êè ìíîæåñòâà Q óïîðÿäî-

÷èâàþòñÿ â ñîîòâåòñòâèè ñ ââåäåííûì îò-

íîøåíèåì ñòðîãîãî ïîðÿäêà <. Çàòåì â

÷åòâåðòîé ñòðîêå ìû ïîìåùàåì â ñòåê ïåð-

âóþ òî÷êó p

start

, ïîñëå ÷åãî ìîæåì óòâåðæ-

äàòü, ÷òî ñòåê ñîäåðæèò âûïóêëóþ îáîëî÷-

êó ìíîæåñòâà {p

start

}. Äàëüøå íà êàæäîé

èòåðàöèè öèêëà for, çàïèñàííîãî â ñòðî-

êàõ 510, ìû äîáàâëÿåì ïî îäíîé òî÷êå ê

âûïóêëîé îáîëî÷êå è ïîääåðæèâàåì ñâîé-

ñòâî, ÷òî â êîíöå k-îé èòåðàöèè ñòåê ñî-

äåðæèò âûïóêëóþ îáîëî÷êó ìíîæåñòâà òî-

÷åê {p

start

, q

, ... , q

} â âèäå ïîñëåäîâà-

òåëüíîñòè âåðøèí â ïîðÿäêå îáõîäà ïðî-

òèâ ÷àñîâîé ñòðåëêè. Çàìåòèì, ÷òî â íà-

ïðàâëåíèè îò äíà ñòåêà S ê åãî âåðõóøêå

ëþáûå òðè ïîäðÿä èäóùèõ ýëåìåíòà ñòåêà

, s

è s

îáðàçóþò ëåâûé ïîâîðîò, òî åñòü

òî÷êà s

ëåæèò ëåâåå îðèåíòèðîâàííîãî

îòðåçêà [s

, s

]. Ïîñëå äîáàâëåíèÿ î÷åðåä-

íîé òî÷êè â ñòåê ýòî ñâîéñòâî ìîæåò íàðó-

øèòüñÿ, ïîýòîìó ìîæåò ïîòðåáîâàòüñÿ óäà-

ëåíèå íåñêîëüêèõ âåðõíèõ ýëåìåíòîâ ñòå-

êà (ñì. ðèñóíîê 2.10), ÷òî è ïðîèñõîäèò â

Ðèñ. 2.11. Ïðèìåð òîãî, êàê òðîéêà òî÷åê (p

, p

) îáðàçóåò (à)

è íå îáðàçóåò (á, â) ëåâûé ïîâîðîò.

a) á) â)

Àëãîðèòìû âû÷èñëèòåëüíîé ãåîìåòðèè.

Âûïóêëûå îáîëî÷êè: ïðîñòûå àëãîðèòìû

ÈÍÔÎÐÌÀÒÈÊÀ

öèêëå while â ñòðîêàõ 67 àëãîðèòìà

GRAHAM-SCAN.

Íà ðèñóíêå 2.12 ïîêàçàí ïðèìåð èòåðàöèè

àëãîðèòìà GRAHAM-SCAN. Íà äàííîé èòåðà-

öèè îáðàáàòûâàåòñÿ òî÷êà q

. Ñíà÷àëà ïîñëå-

äîâàòåëüíîñòü òî÷åê NEXT-TO-TOP(S)

→

TOP(S)

→

íå ñîñòàâëÿåò ëåâûé ïîâîðîò

(ñì. ðèñóíîê 2.12 a). Ñëåäîâàòåëüíî, òî÷êà

Top(S) íå âõîäèò â âûïóêëóþ îáîëî÷êó. Ïîñ-

ëå äâóõ óäàëåíèé (ñì. ðèñóíîê 2.12 áâ)

òðîéêà òî÷åê (NEXT-TO-TOP(S), TOP(S), q

)

ñîñòàâëÿåò ëåâûé ïîâîðîò è òî÷êà q

äîáàâëÿåòñÿ â ñòåê. Â êîíöå èòåðàöèè

ñòåê ñîäåðæèò âûïóêëóþ îáîëî÷êó

start

, q

, ..., q

Ïîêàæåì òåïåðü, ÷òî âðåìÿ ðàáîòû àë-

ãîðèòìà GRAHAM-SCAN åñòü O(n log n). Ñîð-

òèðîâêà òî÷åê ìîæåò áûòü âûïîëíåíà çà

âðåìÿ O(n log n). Îñòàëüíàÿ ÷àñòü àëãîðèò-

ìà òðåáóåò âðåìåíè O(n). Ýòî íå ñðàçó î÷å-

âèäíî, ïîñêîëüêó î÷åðåäíàÿ èòåðàöèÿ öèê-

ëà for â ñòðîêàõ 510, ïîìèìî äîáàâëåíèÿ

îäíîé íîâîé òî÷êè, ìîæåò ïîòðåáîâàòü óäà-

ëåíèÿ íåñêîëüêèõ ñòàðûõ. Òåì íå ìåíåå,

ëþáàÿ òî÷êà q

äîáàâëÿåòñÿ â ñòåê S òîëüêî

îäèí ðàç, à ïîòîìó è óäàëÿåòñÿ íå áîëåå

Ðèñ. 2.12. Îäíà èòåðàöèÿ àëãîðèòìà GRAHAM-SCAN

Ëèñòèíã 5. algorithm GRAHAM-SCAN(Q)

→

CH(Q)

Âõîä. Èñõîäíîå ìíîæåñòâî òî÷åê Q = {p

| p

= (x

, y

), i ∈ [1..n]}.

Âûõîä. Âûïóêëàÿ îáîëî÷êà ìíîæåñòâà òî÷åê CH(Q), çàäàííàÿ ïîñëåäîâàòåëüíîñòüþ

âåðøèí (ïåðå÷èñëåííûõ â ïîðÿäêå îáõîäà ïðîòèâ ÷àñîâîé ñòðåëêè).

1 Ñîçäàòü ïóñòîé ñòåê S

2 Âûáðàòü òî÷êó ñ íàèìåíüøåé àáñöèññîé ñðåäè âñåõ òî÷åê èìåþùèõ ìèíèìàëüíóþ

îðäèíàòó (p

start

)

3 Îòñîðòèðîâàòü âñå òî÷êè ìíîæåñòâà Q = {p

start

} â ïîðÿäêå îòíîøåíèÿ <.

B ðåçóëüòàòå ïîëó÷èòñÿ ïîñëåäîâàòåëüíîñòü òî÷åê {q

}

n1

, òàêàÿ ÷òî

< q

< ... < q

n2

< q

n1

4PUSH(S, p

start

)

5 for i

←

1 to n  1 do

6 while SIZE(S) > 1 and òðè òî÷êè (NEXT-TO-TOP(S), TOP(S), q

) íå îáðàçóþò ëåâûé

ïîâîðîò do

7 POP(S)

8 end-do

9 PUSH(S, q

)

10 end-do

11 Âåðíóòü â êà÷åñòâå îòâåòà ïîñëåäîâàòåëüíîñòü òî÷åê, ñîäåðæàùóþñÿ â ñòåêå S (äíî

ñòåêà áóäåò ïåðâûì ýëåìåíòîì ðåçóëüòèðóþùåé ïîñëåäîâàòåëüíîñòè, à TOP(S)

ïîñëåäíèì)

N-T-T

EX T O OP

()S

N-T-T

EXT O OP

()S

á)

start

N-T-T

EXT O OP

()S

â)

start

(q )

Ивановский С.А., Преображенский А.С. Алгоритмы вычислительной геометрии. Выпуклые оболочки: простые алгоритмы

Подождите немного. Документ загружается.