7.12. Простий алгоритм з впорядкованим списком ребер

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

Простий алгоритм з впорядкованим списком ребер

Підготувати дані.

Визначити для кожного ребра багатокутника точки петинів зі скануючими рядками, що проведені через середини інтервалів, для чого можна використовувати алгоритм Брезенхема або ЦДА. Горизонтальні ребра ігноруються. Занести кожен перетин (х, у +) у список.

Відсортувати список по рядках і по зростанню х у рядку; тобто (х_1, у₁) передує (х₂, у₂), якщо у₁ > у₂ або у₁ = у₂ та х₁ ≤ х₂.

Перетворити ці дані в растрову форму:

Виділити з відсортованого списку пари елементів (х_1, у₁) і (х₂, у₂). Структура списку гарантує, що у = у₁ = у₂ i х₁ ≤ х₂. Активувати на скануючому рядку у пікселі для цілих значень х таких, що

х₁ ≤ х + ≤ х₂.

Приклад 7.8. Простий упорядкований список ребер

Розглянемо багатокутник, наведений на рис. 7.23. Його вершини Р₁(1,1), Р₂(8,1), Р₃(8,6), Р₄(5,3) та Р₅(1,7). Перетини з серединами скануючих рядків наступні_:

скан. рядок 1.5: (8, 1.5), (1, 1.5)

скан. рядок 2.5: (8, 2.5), (1, 2.5)

скан. рядок 3.5: (8, 3.5), (5.5, 3.5), (4.5, 3.5), (1, 3.5)

скан. рядок 4.5: (8, 4.5), (6.5, 4.5), (3.5, 4.5), (1, 4.5)

скан. рядок 5.5: (8, 5.5), (7.5, 5.5), (2.5, 5.5), (1, 5.5)

скан. рядок 6.5: (1.5, 6.5), (1, 6.5)

скан. рядок 7.5: немає

Весь список сортується в поряду сканування спочатку зверху вниз і тоді – зліва направо

(1, 6.5), (1.5, 6.5), (1, 5.5), (2.5, 5.5), (7.5, 5.5), (8, 5.5), (1, 4.5), (3.5, 4.5), (6.5 , 4.5), (8, 4.5), (1, 3.5), (4.5, 3.5), (5.5, 3.5), (8, 3.5), (1,2.5), (8, 2.5), (1,1.5 ), (8, 1.5)

Виділяючи зі списку пари перетинів і застосовуючи алгоритм, що описаний вище, отримаємо список пікселів, які повинні бути активовані:

(1.6)

(1,5), (2, 5), (7, 5)

(1,4), (2, 4), (3,4), (6, 4), (7, 4)

(1, 3), (2, 3), (3, 3), (4, 3), (5, 3), (6, 3), (7, 3)

(1, 2), (2, 2), (3, 2) (4, 2), (5, 2), (6, 2), (7, 2) (1, 1), (2, 1 ), (3, 1), (4, 1), (5, 1), (6, 1), (7, 1)

Результат наведений на рис. 7.26. Зауважимо, що обидва вертикальних і нижнє ребра зображені вірно.

Рис. 7.26. Результат растрової розгортки суцільної області, що наведена на рис. 7.33