Полигонен пълнеж
Често има проблем със запълването на полигони, зададени от набор от върхове.
Задачата за запълване на полигони се решава на два етапа:
1) първо се извършва операцията по отрязване на многоъгълника;
2) след това получените полигони се запълват.
Стъпката на изрязване е необходима, за да се определят реалните области на полигона, които ще бъдат показани. Това е необходимо, ако полигонът е по-голям или се простира отвъд екрана или изходния прозорец.
Изрязването на многоъгълник най-често се прави, за да се изхвърлят части от полигона, които се простират извън правоъгълната област, която определя областта на екрана или прозореца. Изрязването обаче може да се извърши спрямо друг многоъгълник. Това генерира нов полигон или няколко нови полигона.
Помислете за алгоритъма на Съдърланд-Ходжман. Алгоритъмът използва стратегията „разделяй и владей“, която позволява решаването на общ проблем да бъде сведено до решаване на редица прости и подобни подпроблеми. Пример за такава подзадача е отрязването на многоъгълник спрямо една граница на отрязване. Последователното решение на четири такива проблема ви позволява да отсечете спрямо правоъгълна област (фиг. 2.17).
Фигура: 2.17. Последователно изрязване на многоъгълник
Алгоритъмът получава последователност от върхове на многоъгълника Vедин, V2, ..., Vн. Ръбовете на многоъгълника отиват отViда сеVi+1отVнда сеV1. С помощта на алгоритъма изрязването се извършва спрямо ръба и се показва друга последователност от върхове, която описва пресечения полигон.
Алгоритъмът "обикаля" около полигона от Vнда сеV1и обратно къмVн, проверка на всяка стъпка връзката между последователни върхове и границата на границата. Има четири случая за анализ:
Фигура: 2.18. Случаи при изрязване на полигони
Помислете за този, показан на фиг. 2 .18 ръб на многоъгълник, свързващ връх сс върхастр. В първия случай ръбът лежи изцяло вътре в границата на изрязване и върхът се добавя към изходния списъкстр. Във втория случай пресечната точка се показва като върховетеi, тъй като ръбът пресича границата и началната точка беше направена от първия случай. В третия случай и двата върха са извън границата и нито един от тях не се показва. В четвъртия случай пресечната точка се добавя към изходния списъкi,и върхастр.