Заповнення суцільних областей

Тест приналежності точки багатокутнику

Будемо розуміти під багатокутником фігуру на площині, обмежену простою (що не має самоперетинів) замкненою ламаною. Ця ламана задається набором своїх вершин. Задача полягає в тому, щоб одержати растрове розгорнення багатокутника, тобто ініціювати його внутрішні точки.

Нехай Р(x,y) – деяка точка площини, що не належить ламаній, і потрібно визначити, належить вона багатокутнику чи ні.

Проведемо через точку Р горизонтальну напівпряму з правим кінцем у точці Р. Тому що ламана обмежена, то завжди легко знайти на цій напівпрямій досить віддалену точку Q, що не належить багатокутнику. Якщо відрізок QP не має перетинів із границею багатокутника, то точки Q і Р лежать в одній компоненті зв’язності і, отже, точка Р – зовнішня.

Розглянемо випадок, коли відрізок QP перетинає ламану. Будемо рухатися від точки Q у напрямку до точки Р. Минуючи перше перетинання відрізка і границі, ми потрапимо усередину багатокутника. Минуючи наступне перетинання відрізка і границі, ми опинимося ззовні багатокутника, і так далі. Легко бачити, що якщо ми зустрінемо на своєму шляху парну кількість перетинань, то точка Р буде зовнішньою точкою стосовно багатокутника. Якщо ж кількість перетинань виявиться непарною, то точка Р буде внутрішньою точкою багатокутника. Важливо засвідчитися, що перетинання відрізка з границею були істотними, тобто відрізок дійсно перетнув ламану, а не просто є дотичним до неї в одній із вершин.

Для виявлення істотних перетинань можна скористатися наступним правилом. Перетинання відрізка з горизонтальними ребрами ігноруються. При підрахунку кількості перетинань відрізка PQ із негоризонтальними ребрами ламаної перетинання ігнорується, якщо точкою перетинання є верхня вершина ребра, і зараховується в будь-якому іншому випадку. Враховуючи цю угоду, дотичність відрізка PQ із ламаною у точках максимуму ігнорується, а в точках мінімуму лічиться двічі.

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

Помістимо багатокутник усередину мінімального за розмірами прямокутника із боками, рівнобіжними осям координат, і будемо аналізувати лише ті точки, що потрапили усередину прямокутника.

Ламана, що обмежує багатокутник, розбиває всяку горизонтальну пряму на інтервали, що чергуються, лежачі усередині або ззовні багатокутника. Для визначення кінців цих інтервалів можна використати наступний спосіб.

Зафіксуємо горизонтальну пряму L, на якій передбачається визначити місце розташування інтервалів, що знаходяться усередині багатокутника, шукаємо точки перетину з цією прямою, якщо вони є, кожного ребра багатокутника. Для перевірки наявності перетину попередньо переконаємося в тому, що кінці ребра розташовані по різні боки від прямої.

При пошуку точок перетинання будемо користуватися правилами, застосованими в тесті приналежності. Тоді кратні перетинання з контуром багатокутника в його вершинах будуть правильно враховані. Далі упорядкуємо отримані точки зліва направо і згрупуємо їх парами. Ці пари і будуть кінцями інтервалів, що лежать усередині багатокутника і мусять бути зафарбованими.

Викладена схема заповнення багатокутника зветься заповненням у порядку сканування рядків, а сам алгоритм відноситься до типу алгоритмів сканування по рядках.