ЗНАЙ ИНТУИТ, Лекция, Попълванеполигони и региони

Алгоритъм за активен списък на ръбовете

Нека се опитаме леко да променим предишния алгоритъм. Вместо да съхраняваме в паметта пресечните точки на контура с всяка линия от растера, ще се ограничим само до една линия – текущата. А именно, ще организираме списък с "активни" ръбове ( CAP ), в който ще съхраняваме информация за всички ръбове на многоъгълника, пресечен от текущата линия. Удобството на този подход е, че когато преминете към нова линия, не е необходимо да възстановявате напълно CAP. Достатъчно е просто да премахнете "завършените" ръбове от него (т.е. ръбовете от CAP, чийто долен край се оказа по-висок от новата стойност на y) и да добавите новопоявилите се.

Нека да преминем към формално описание на алгоритъма. За всеки ръб създайте структура от данни:

Поставяме всички такива структури в списък (наричан по-нататък y-списък) и го подреждаме във възходящ ред на y.

Ръбовете, поставени в CAP, се премахват от y-списъка, за да се намали тестът за наличие на ръбове в y-списъка, започвайки от дадено ниво y, до проверка на това условие за първия ръб в списъка (това е вярно поради подреждането на списъка). Цикълът while се използва за поддържане на подреждането на CAP, което може да бъде нарушено, когато стойностите на x се променят на dx.

Пример за такава ситуация е показан на фиг. 6.3. Когато това се случи, посоченият цикъл извършва локално сортиране на CAP, използвайки метода "балон".

интуит

Предимството на горните два алгоритъма пред следващите е, че операциите за показване (сравнително "бавни" на много системи) за всеки пиксел се изпълняват най-много веднъж. Недостатъкът е използването на динамични структури от данни (списъци), което значително усложнява кода и изисква допълнителна памет.