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

Ãëàâà 10. ÏÎÑÒÐÎÅÍÈÅ ÏÎ ÒÎ×ÊÀÌ È ÂÎÑÏÐÎÈÇÂÅÄÅÍÈÅ ÊÐÈÂÛÕ

10.1. ÂÂÅÄÅÍÈÅ

 ðàçä. 7.6. îáñóæäàëèñü âîçìîæíîñòè çàäàíèÿ êðèâîé íà äèñêðåòíîé ñåòêå, à â ðàçä. 9.7 — ñïîñîáû ïîñòðîåíèÿ êðèâîé ïî åå îñòîâó. Ïðè ðåøåíèè îäíèõ ïðèêëàäíûõ çàäà÷ äîïóñòèìî ïðåäñòàâëåíèå êðèâîé â âèäå ïîñëåäîâàòåëüíîñòè ïèêñåëîâ, à ïðè ðåøåíèè äðóãèõ ïðåäïî÷òèòåëüíî çàäàâàòü êðèâóþ ñ ïîìîùüþ ìàòåìàòè÷åñêîãî âûðàæåíèÿ. Ïîñëåäíåå ìîæåò îêàçàòüñÿ çíà÷èòåëüíî êîìïàêòíåå äèñêðåòíûõ ïðåäñòàâëåíèé, êàê ñâèäåòåëüñòâóåò ñîïîñòàâëåíèå ðèñ. 9.8 è òàáë. 9.1. Îòûñêàíèå êðèâîé, ïðîõîäÿùåé ÷åðåç çàäàííîå ìíîæåñòâî òî÷åê, ñîñòàâëÿåò çàäà÷ó èíòåðïîëèðîâàíèÿ, à îòûñêàíèå êðèâîé, ïðîõîäÿùåé âáëèçè çàäàííîãî ìíîæåñòâà òî÷åê — çàäà÷ó àïïðîêñèìàöèè. Äëÿ îáîçíà÷åíèÿ îáåèõ çàäà÷ áóäåì ïîëüçîâàòüñÿ òåðìèíîì ïîñòðîåíèå êðèâîé ïî òî÷êàì. Ïðåäñòàâëÿåò òàêæå èíòåðåñ çàäà÷à âîñïðîèçâåäåíèÿ èçîáðàæåíèÿ êðèâîé, çàêëþ÷àþùàÿñÿ â ñëåäóþùåì: äëÿ çàäàííîãî ìàòåìàòè÷åñêîãî âûðàæåíèÿ òðåáóåòñÿ íàéòè ñîîòâåòñòâóþùèå ïèêñåëû è ïðèñâîèòü èì çíà÷åíèÿ, ïðè êîòîðûõ îíè ñîñòàâëÿþò èçîáðàæåíèå êðèâîé, îïèñûâàåìîé çàäàííûì âûðàæåíèåì. Ýòó çàäà÷ó íåëüçÿ ñ÷èòàòü òðèâèàëüíîé äàæå ïðè âîñïðîèçâåäåíèè èçîáðàæåíèé ïðÿìûõ (ñì. ðàçä. 7.6).

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

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

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

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

×àñòî ðåøàþùåå çíà÷åíèå ïðè ïîñòðîåíèè êðèâûõ ïî òî÷êàì ïðèîáðåòàåò âûáîð ìàòåìàòè÷åñêîãî îïèñàíèÿ (ôóíêöèè). Õîòÿ ìíîãî÷ëåíû — ïåðâîå, ÷òî ïðèõîäèò çäåñü â ãîëîâó, èõ ïðèìåíåíèå îáû÷íî äàåò ïëîõîå ðåøåíèå. Íàèáîëüøåå ðàñïðîñòðàíåíèå ïîëó÷èëè ìåòîäû, ïðåäóñìàòðèâàþùèå èñïîëüçîâàíèå êóñî÷íî-ïîëèíîìèàëüíûõ ôóíêöèé ðàçëè÷íûõ òèïîâ. Ïðè ðåøåíèè çàäà÷ àïïðîêñèìàöèè òàêæå ñëåäóåò óäåëÿòü âíèìàíèå âûáîðó êðèòåðèÿ, õàðàêòåðèçóþùåãî êà÷åñòâî ïðèáëèæåíèÿ. Ìàêñèìàëüíîå ðàññòîÿíèå òî÷åê îò êðèâîé èëè ïîâåðõíîñòè ïðåäñòàâëÿåòñÿ âïîëíå ðàçóìíûì êðèòåðèåì, îäíàêî ÷àñòî åãî èñïîëüçîâàíèå ïîðîæäàåò ñëîæíûå âû÷èñëèòåëüíûå ïðîáëåìû.  ïðèíöèïå, íåîáõîäèìî äîñòèæåíèå íåêîòîðîãî êîìïðîìèññà ìåæäó òåì, ÷òî èíòóèòèâíî êàæåòñÿ æåëàòåëüíûì, è òåì, ÷òî îêàçûâàåòñÿ ðåàëüíûì ñ âû÷èñëèòåëüíîé òî÷êè çðåíèÿ.

Íà÷íåì ñ ïîñòðîåíèÿ êðèâûõ ïî òî÷êàì ïðè ïîìîùè ìíîãî÷ëåíîâ.  äâóõ ñëåäóþùèõ ãëàâàõ áóäåò ðàññìîòðåíî ïîñòðîåíèå êðèâûõ ïî òî÷êàì êóñî÷íî-ïîëèíîìèàëüíûìè ìåòîäàìè. Îñíîâíîå âíèìàíèå áóäåò ñîñðåäîòî÷åíî íà àïïðîêñèìàöèè 5-ñïëàéíàìè è ìíîãîóãîëüíèêàìè, à â äàííîé ãëàâå ìû çàéìåìñÿ ìíîãî÷ëåíàìè Áåçüå. Íåêîòîðûå ìåòîäû ïîñòðîåíèÿ ïîâåðõíîñòåé ðàññìàòðèâàþòñÿ â ãë. 13.

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

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