НОУ ІНТУІТ, Лекція, Заповненнябагатокутників та областей

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

Спробуємо дещо змінити попередній алгоритм. Замість того щоб зберігати в пам'яті точки перетину контуру з кожним рядком растру, обмежимося лише одним рядком - поточним. А саме, організуємо список "активних" ребер (САР), в якому зберігатимемо інформацію про всі ребри багатокутника, що перетинаються поточним рядком. Зручність такого підходу в тому, що при переході до нового рядка не потрібно повністю переформовувати САР. Достатньо лише видалити з нього "ребра, що закінчилися" (тобто ребра з САР, чий нижній кінець виявився вище нового значення y) і додати знову з'явилися.

Перейдемо до формального опису алгоритму. Для кожного ребра створимо структуру даних:

Усі такі структури помістимо до списку (далі - y-список) і впорядкуємо його за зростанням y .

Ребра, поміщені в САР , видаляються з y-списку з тією метою, щоб звести перевірку наявності в y-списку ребер, що починаються з даного рівня y до перевірки цієї умови для першого ребра в списку (це справедливо в силу впорядкованості списку). Цикл while використовується для збереження впорядкованості САР, яка може порушитись при зміні значень x на dx.

Приклад такої ситуації показано на рис. 6.3. При її виникненні зазначений цикл виконує локальне сортування САР методом "бульбашка".

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

Перевага двох наведених алгоритмів перед наступними полягає в тому, що операції виведення на екран (щодо "повільні" в багатьох системах) для кожного пікселя виконуються не більше одного разу. Недоліком є ​​використання динамічних структур даних (списків), що ускладнює код і вимагає додаткової пам'яті.