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

12.5.2. ÏÐÎÑÒÎÉ ÀËÃÎÐÈÒÌ ÏÎÑÒÐÎÅÍÈß ÌÍÎÃÎÓÃÎËÜÍÈÊÀ ÏÎ ÒÎ×ÊÀÌ

Àëãîðèòì 12.2 îáåñïå÷èâàåò ïîñòðîåíèå ìíîãîóãîëüíèêà ïî òî÷êàì, îáðàáàòûâàÿ íåáîëüøèå ãðóïïû òî÷åê ðàçìåðîì òàê ÷òî (Òèïè÷íûå çíà÷åíèÿ ëåæàò â äèàïàçîíå 5—10). Àëãîðèòì ñòðîèò (îòñëåæèâàåò) òåêóùóþ ïðÿìóþ è íîâóþ ïðÿìóþ Åñëè ïðè ïðèìåíåíèè ñîîòâåòñòâóþùåãî òåñòà îáíàðóæèâàåòñÿ êîëëèíåàðíîñòü ãðóïïû òî÷åê (ïðîâåðêà íà øàãå 4 óñòàíàâëèâàåò, ÷òî â ðåçóëüòàòå èñïîëüçîâàíèÿ ïðîöåäóðû COLLINEAR ïîëó÷åíî èñòèííîå çíà÷åíèå), òî âûïîëíÿåòñÿ áëîê øàãîâ 5—10. Íà øàãå 5 îïðåäåëÿåòñÿ íîâàÿ ïðÿìàÿ ïðåäñòàâëÿþùàÿ ñîáîé ïðÿìóþ, ïîëó÷åííóþ â ðåçóëüòàòå ïðèìåíåíèÿ ïðîöåäóðû Åñëè ïåðâàÿ òî÷êà ãðóïïû íàçíà÷àåòñÿ òî÷êîé ñêëåèâàíèÿ òî íîâàÿ ïðÿìàÿ ñòàíîâèòñÿ òåêóùåé ïðÿìîé (øàã 6), à øàãè 7—9 ïðîïóñêàþòñÿ. Åñëè îòëè÷àåòñÿ îò ó, òî íà øàãå 8 èñïîëüçóåòñÿ òåñò íà ñëèÿíèå, çàêëþ÷àþùèéñÿ â ñðàâíåíèè ïðÿìûõ (ðèñ. 12.6).

Ðèñ. 126. Èëëþñòðàöèÿ ê àëãîðèòìó 12.2: çàäàíèå ïðÿìûõ

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

Åñëè òåñò íà êîëëèíåàðíîñòü, ïðîâîäèìûé íà øàãàõ 3 è 4, ïðèíîñèò îòðèöàòåëüíûé ðåçóëüòàò, òî îí ïðèìåíÿåòñÿ ê ãðóïïå òî÷åê, ðàñïîëîæåííûõ ìåæäó ïåðâîé òî÷êîé è òî÷êîé, â êîòîðîé îøèáêà ìàêñèìàëüíà (ïî àáñîëþòíîé âåëè÷èíå). Äëÿ ýòîãî èñïîëüçóåòñÿ øàã 11, íà êîòîðîì çàäàåòñÿ è îñóùåñòâëÿåòñÿ âîçâðàò ê íà÷àëó öèêëà, ÷òî îáåñïå÷èâàåò ïîâòîðíîå âûïîëíåíèå øàãà 3 (Îòìåòèì, ÷òî ïðè âûïîëíåíèè öèêëà ïðèðàùåíèå íå ïðîèñõîäèò àâòîìàòè÷åñêè.  öèêëå ëèøü ïðîâåðÿåòñÿ, íå äîøåë ëè àëãîðèòì äî îáðàáîòêè ïîñëåäíåé ýêñïåðèìåíòàëüíîé òî÷êè.)

Îïåðàöèè, ïðåäóñìîòðåííûå íà øàãàõ 8 è 9, ìîæíî çàìåíèòü ïîâòîðíûì ïðèìåíåíèåì òåñòà íà êîëëèíåàðíîñòü ê îáúåäèíåíèþ

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

Àëãîðèòì 12.2 îòíîñèòñÿ ê îïèñàííîìó â ëèòåðàòóðå êëàññó àëãîðèòìîâ, îñóùåñòâëÿþùèõ «ïðîñìîòð âäîëü» íåêîòîðîãî ìíîæåñòâà òî÷åê.  êàæäîé òî÷êå ïðÿìàÿ êîððåêòèðóåòñÿ è ïðîâåðÿåòñÿ, íå ïðåâûøàåò ëè îøèáêà äîïóñòèìîãî çíà÷åíèÿ. Åñëè çíà÷åíèå îøèáêè íàõîäèòñÿ â äîïóñòèìûõ ïðåäåëàõ, àëãîðèòì ïåðåõîäèò ê îáðàáîòêå ñëåäóþùåé ýêñïåðèìåíòàëüíîé òî÷êè, â ïðîòèâíîì ñëó÷àå ââîäèòñÿ ñîîòâåòñòâóþùàÿ òî÷êà ñêëåèâàíèÿ (ñì. ðàçä. 12.7). Ïðåäñòàâëåííûé íèæå àëãîðèòì îòíîñèòñÿ ê òèïó àëãîðèòìîâ, îñóùåñòâëÿþùèõ «ïðîñìîòð ñêà÷êàìè âäîëü» íåêîòîðîãî ìíîæåñòâà òî÷åê. Ýòîò àëãîðèòì ïðåäóñìàòðèâàåò èñïîëüçîâàíèå îäíîé ïðÿìîé äëÿ ãðóïïû òî÷åê, ÷òî ïîçâîëÿåò èñêëþ÷èòü âû÷èñëåíèÿ, ñâÿçàííûå ñ ïåðåñ÷åòîì ïðÿìîé â êàæäîé òî÷êå. Îäíàêî ïðè âîçíèêíîâåíèè îøèáêè àëãîðèòì äîëæåí âåðíóòüñÿ ê òî÷êå, â êîòîðîé îøèáêà ïðèíèìàåò ìàêñèìàëüíîå çíà÷åíèå. Òàêèì îáðàçîì, âàæíî âûáèðàòü ðàçìåð ãðóïïû òî÷åê äîñòàòî÷íî ìàëûì äëÿ ñíèæåíèÿ ÷àñòîòû âîçâðàòîâ. Ïðè ýòîò àëãîðèòì ñâîäèòñÿ ê àëãîðèòìó «ïðîñìîòðà âäîëü».  ýòîì ñëó÷àå òåñò íà êîëëèíåàðíîñòü âñåãäà àäåêâàòåí è àëãîðèòì ñâîäèòñÿ ê øàãàì 8 è 9.

Àëãîðèòì 12.2. Ïîñòðîåíèå ìíîãîóãîëüíèêà ïî òî÷êàì

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

(ñì. ñêàí)

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