7.10. Заповнення багатокутників

Багато замкнених контурів є простими багатокутниками. Якщо контур складається з кривих ліній, то його можна апроксимувати багатокутником або багатокутниками. Найпростіший метод заповнення багатокутника полягає в перевірці на приналежність вмісту багатокутника кожного пікселя в растрі. Оскільки зазвичай більшість пікселів лежить поза багатокутником, то даний метод дуже трудомісткий. Затрати можна зменшити шляхом обчислення для багатокутника прямокутної оболонки − найменшого прямокутника, що містить всередині себе багатокутник. Як наведено на рис. 7.22, перевіряються лише внутрішні точки цієї оболонки. Використання прямокутної оболонки для багатокутника, що наведений на рис. 7.22,а, набагато скорочує кількість пікселів, що перевіряються. В той же час для багатокутника, наведеного на рис. 7.22,b, скорочення істотно менші.

Рис. 7.22. Прямокутна оболонка