Ãëàâíàÿ > Àëãîðèòìû ìàøèííîé ãðàôèêè è îáðàáîòêè èçîáðàæåíèé
<< Ïðåäûäóùèé ïàðàãðàô
Ñëåäóþùèé ïàðàãðàô >>
<< Ïðåäûäóùèé ïàðàãðàô Ñëåäóþùèé ïàðàãðàô >>
Ìàêåòû ñòðàíèö

9.5. ÁÛÑÒÐÛÉ ÀËÃÎÐÈÒÌ ÏÐÎÐÅÆÈÂÀÍÈß

Àëãîðèòìû, ðàññìîòðåííûå â ïðåäûäóùèõ ðàçäåëàõ, îñóùåñòâëÿþò ïðîöåäóðó ïðîðåæèâàíèÿ, ñèñòåìàòè÷åñêè îáðàáàòûâàÿ âñå èçîáðàæåíèÿ öåëèêîì. Âñòðå÷àþòñÿ, îäíàêî, òàêèå ïðèêëàäíûå çàäà÷è, ïðè ðåøåíèè êîòîðûõ õðàíåíèå èçîáðàæåíèÿ â ïàìÿòè îêàçûâàåòñÿ íåïðàêòè÷íûì, à ïðîðåæèâàíèå öåëåñîîáðàçíî ïðîâîäèòü áîëåå ïðîñòûì ñïîñîáîì. Àëãîðèòì 9.4 ðåàëèçóåò ÷ðåçâû÷àéíî ïðîñòîé ñïîñîá ïðîðåæèâàíèÿ, íî ïðè îáðàáîòêå ìíîãèõ îáúåêòîâ âûäåëèòü ÷àñòè îñòîâà ñ åãî ïîìîùüþ íå óäàåòñÿ. Ñ

äðóãîé ñòîðîíû, îí îáëàäàåò áûñòðîäåéñòâèåì, ñóùåñòâåííî áîëüøèì, ÷åì ëþáîé èç îïèñàííûõ â ïðåäûäóùèõ ðàçäåëàõ àëãîðèòìîâ, è, âîçìîæíî, áûëî áû íåïëîõî èñïîëüçîâàòü òàêîé àëãîðèòì â êà÷åñòâå ñðåäñòâà ïðåäâàðèòåëüíîé îáðàáîòêè, ïðè÷åì äàæå â òåõ ñëó÷àÿõ, êîãäà îáúåêòû íà èçîáðàæåíèÿõ íå ïðåäñòàâëåíû, ãëàâíûì îáðàçîì, òîíêèìè ëèíèÿìè.  òàêîé ñèòóàöèè ê ÷àñòÿì ñèëóýòà, îñòàâøèìñÿ íåïðîðåæåííûìè, ìîæíî ïðèìåíèòü îäèí èç óíèâåðñàëüíûõ àëãîðèòìîâ ïðîðåæèâàíèÿ.

Äàííûé àëãîðèòì âûïîëíÿåò ïîñëåäîâàòåëüíóþ ïîñòðî÷íóþ îáðàáîòêó, ïðè÷åì â ïàìÿòè äîëæíî õðàíèòüñÿ ëèøü íåáîëüøîå ÷èñëî ñòðîê èëè èõ ÷àñòåé. Äëÿ ïðîñòîòû áóäåì îïèñûâàòü ðàáîòó àëãîðèòìà êàê ïðîöåññ îáõîäà ãðàôà ñìåæíîñòè ñòðîê, õîòÿ çàïîìèíàíèå ïîñëåäíåãî â ÿâíîì âèäå íå ïðåäóñìàòðèâàåòñÿ. (Àíàëèç ïàðàëëåëüíîãî ðåæèìà ðàáîòû ïðîâåäåí â ãë. 8). Äëÿ äàííîãî àëãîðèòìà âåñüìà ñóùåñòâåííûì ÿâëÿþòñÿ ïîíÿòèÿ âåðòèêàëüíîãî, ãîðèçîíòàëüíîãî è äèàãîíàëüíîãî ìàðøðóòîâ, êîòîðûå ìû îïðåäåëèì ñëåäóþùèì îáðàçîì.

Îïðåäåëåíèå 9.4 à. Âåðòèêàëüíûì ìàðøðóòîì ÃÑÑ íàçûâàåòñÿ òàêîé ìàðøðóò, øèðèíà âñåõ âåðøèí êîòîðîãî ìåíüøå çíà÷åíèÿ çàäàííîãî ïîðîãà è ÷èñëî âåðøèí êîòîðîãî áîëüøå çàäàííîãî çíà÷åíèÿ

Îïðåäåëåíèå Ãîðèçîíòàëüíûì ìàðøðóòîì ÃÑÑ íàçûâàåòñÿ òàêîé ìàðøðóò, øèðèíà âñåõ âåðøèí êîòîðîãî áîëüøå ïîðîãîâîãî çíà÷åíèÿ ÷èñëî âåðøèí êîòîðîãî ìåíüøå çíà÷åíèÿ à âåðøèíû, ðàñïîëîæåííûå ïî îáåèì ñòîðîíàì ìàðøðóòà, èìåþò øèðèíó, íå ìåíüøóþ ïîðîãîâîãî çíà÷åíèÿ — ðàññòîÿíèå ìåæäó ëèíèÿìè ïðîñìîòðà).

Îïðåäåëåíèå 9.4 â. Äèàãîíàëüíûì ìàðøðóòîì ÃÑÑ ñ óãëîì íàêëîí íàçûâàåòñÿ òàêîé ìàðøðóò, âñå öåíòðû âåðøèí êîòîðîãî ïðèáëèæåííî êîëëííåàðíû (÷òîáû óáåäèòüñÿ â ýòîì, ìîæíî âîñïîëüçîâàòüñÿ îäíèì èç àëãîðèòìîâ, ïðèâåäåííûõ â ãë. 12), óãîë íàêëîíà ïðÿìîé, ïðîõîäÿùåé ÷åðåç ýòè öåíòðû, ðàâåí øèðèíà âñåõ âåðøèí ìåíüøå çíà÷åíèÿ è ÷èñëî âåðøèí áîëüøå çíà÷åíèÿ

Ïðèìåð 9.1. Íà ðèñ. 9.7, à ïðåäñòàâëåí ñèëóýò èçîáðàæåíèÿ è ñîîòâåòñòâóþùèé ÃÑÑ. Âèäíî, ÷òî äâà ðåáðà òî÷íî âûäåëåíû è èäåíòèôèöèðîâàíû àëãîðèòìîì 9.4. Ïîñêîëüêó øèðèíà âñåõ âåðøèí ìàëà, ïîäìàðøðóò 1—7 ìîæíî ñ÷èòàòü âåðòèêàëüíûì øòðèõîì Âåðøèíà 8 ñàìà ïî ñåáå îáðàçóåò ïîäìàðøðóò, êîòîðûé ìîæíî ðàññìàòðèâàòü êàê ãîðèçîíòàëüíûé øòðèõ Åñëè áû âåðøèíà 7 íå âõîäèëà â ïåðâûé ïîäìàðøðóò, åå ìîæíî áûëî áû èñïîëüçîâàòü â êà÷åñòâå âåðøèíû, ñâÿçûâàþùåé äâà âûäåëåííûõ øòðèõà. Ïðèìåð, ïðèâåäåííûé íà ðèñ. 9.7, á, èëëþñòðèðóåò ñëó÷àé, êîãäà ñ ïîìîùüþ äàííîãî àëãîðèòìà íå óäàëîñü âûäåëèòü êðèâîëèíåéíûé øòðèõ Âåðøèíó 3 êàê òàêîâóþ ìîæíî áûëî áû ñ÷èòàòü ãîðèçîíòàëüíûì øòðèõîì, îäíàêî, íàëè÷èå âåðøèíû 4 èñêëþ÷àþò âûíåñåíèå òàêîãî êëàññèôèêàöèîííîãî ðåøåíèÿ

Àëãîðèòì 9.4. Áûñòðûé àëãîðèòì ïðîðåæèâàíèÿ

(ñì. ñêàí)

(ñì. ñêàí)

<< Ïðåäûäóùèé ïàðàãðàô Ñëåäóþùèé ïàðàãðàô >>
Îãëàâëåíèå