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. Ïîñòðîåíèå ìíîãîóãîëüíèêà ïî òî÷êàì
Îáîçíà÷åíèÿ. Ìàññèâû
ñîäåðæàò êîîðäèíàòû ýêñïåðèìåíòàëüíûõ òî÷åê,
— èíäåêñ ïåðâîé, à ê — èíäåêñ ïîñëåäíåé òî÷êè ãðóïïû, ïðîâåðÿåìîé íà êîëëèíåàðíîñòü.
— ÷èñëî ýêñïåðèìåíòàëüíûõ òî÷åê, îáû÷íî âõîäÿùèõ â ñîñòàâ òàêîé ãðóïïû
— èíäåêñ ïîñëåäíåé âåðøèíû ìíîãîóãîëüíèêà è
ïðÿìàÿ, ñîåäèíÿþùàÿ òî÷êó
ñ òî÷êîé
— èíäåêñ òî÷êè, â êîòîðîé ïðè ïðîâåäåíèè òåêñòà íà êîëëèíåàðíîñòü áûëà çàôèêñèðîâàíà ìàêñèìàëüíàÿ îøèáêà.
(ñì. ñêàí)