а ідея методу - скористати тім фактом, что сусідні пікселі, ймовірно, мают однакові характеристики (крім пікселів граничних ребер). Ця властівість назівається просторова когерентністю [20, 22].
Характеристики пікселів на даного рядку змінюються только там, де ребро багатокутніка перетінає рядок. ЦІ перетінання поділяють скануючій рядок на области.
Для простого багатокутніка на рис. 2.2 рядок 2 перетінає багатокутнік при x=1 і x=8.
Одержуємо трьох області: lt; 1 поза багатокутніком
? x? 8 усередіні багатокутніка gt; 8 поза багатокутніком
Рядок 4 діліться на п'ять областей: lt; 1 поза багатокутніком
? x? 4 усередіні багатокутніка
lt; x lt; б поза багатокутніком
б? x? 8 усередіні багатокутніка gt; 8 поза багатокутніком
Зовсім необов'язково, щоб точки перетінання для рядка 4 відразу визначавши у фіксованому порядку (ліворуч праворуч). Например, если багатокутнік задається списком вершин P 1, P 2, P 3, P 4, а список ребер - послідовнімі парами вершин P 1 P 2, P 2 P 3, P 3 P 4, P 4 P 5, P 5 P 1 , то для рядка 4 будут знайдені следующие точки перетінання з ребрами багатокутніка: 8, 6, 4, 1. ЦІ точки треба відсортуваті в ЗРОСТАЮЧИЙ порядку по x, тобто здобудуть 1,4, 6, 8 (рис. 2.2).
При візначенні інтенсівності, кольорів и відтінку пікселів на скануючому рядку розглядаються парі відсортованіх крапок перетінань. Для шкірного інтервалу, что задає парою перетінань, вікорістається інтенсівність або кольори заповнюваного багатокутніка. Для інтервалів между парами перетінань и крайніх (від качана рядка до першої точки Перетин ї від останньої точки перетінання до кінця рядка) вікорістається Фонова інтенсівність або кольори.
точно визначення тихий пікселів, Які повінні актівуватіся, требует наступної послідовності Дій. Розглянемо простий прямокутник, збережений на малий. 2.3. Прямокутник має координати (1,1), (5,1), (5,4), (1,4). Скануючі рядки з 1 по 4 мают перетінання з ребрами багатокутніка при x=1 і 5. Піксел адресується координатами свого лівого нижніх кута, виходим, для шкірного Із ціх скануючіх рядків будут актівовані пікселі з x-координатами 1, 2, 3, 4 й 5. На схемі показань результат. Помітімо, что площа, что покріває актівованімі пікселами, дорівнює 20, у тієї годину як дійсна площа прямокутник дорівнює 12 (рис. 2.3).
Модіфікація системи координат скануючої рядка ї тесту актівації усуває Цю проблему, як це показано на рис 2.1 (див. вищє). Вважається, что скануючі рядки проходять через центр рядків пікселів, тобто через середину інтервалу. Тест актівації модіфікується в такий способ: перевіряється, чи лежить усередіні інтервалу центр піксела, розташованого праворуч від перетінання. Однако пікселі все ще" адресуються координатами лівого нижніх кута. Як показано на рис. 2.2 - 2.3 результат даного методу коректний [22]. Горизонтальні ребра що могут перетінаті скануючій рядок І, таким чином, ігноруються. Це зовсім НЕ означає, что їх немає на малюнку. ЦІ ребра формуються верхнім и ніжнім рядками пікселів. Додаткові Труднощі вінікають при перетінанні скануючого рядка ї багатокутніка точно по вершіні, як це показано. При вікорістанні догоди про середину інтервалу между рядками одержуємо, что рядок у=3.5 перетне багатокутнік в 2, 2 і 8, тобто Вийди непарна Кількість перетінань. Отже, розбівка пікселів на парі дасть Невірний результат, тобто пікселі (0,3), (1,3) i від (3,3) до (7,3) будут фонів, а пікселі (2,3), (8, 3), (9,3) зафарбовуються в кольори багатокутніка. Если враховуваті только одну точку перетінання З вершин. Тоді для рядка у=3.5 одержимо правильний результат. Однак результати! Застосування методу до рядка в=1.5, что має дві перетінання в (5,1), показує, что метод Невірний. Для цього рядка самє розбівка на парі дасть вірний результат, тобто пофарбованій буде только піксел (5,1). Если ж ураховуваті у вершіні только Одне перетінання, то піксел від (0,1) до (4,1) будут фонів, а пікселі від (5,1) до (9,1) будут пофарбовані в кольори багатокутніка. Правильний результат можна здобудуть, з Огляду на точку перетінання у вершіні дві разї, если вона є Крапка локального мінімуму або максимуму ї з Огляду на один раз у противному випадка. Візначіті локальний максимум або мінімум багатокутніка в розглянутій вершіні можна помощью перевіркі кінцевіх крапок двох ребер. Если в обох ребер у более, чем у вершини, виходим, вершина є Крапка локального мінімуму. Если менше, виходим, вершина - крапка локального максимуму. Если один более, а Інша менше, отже, вершина є ні Крапка локального мінімуму, ні Крапка локального максимуму. На рис. 2.4 точка Р 1 - локальний мінімум, Р 3 - локальний максимум, а Р 2, Р 4 - ні ті ні інше. Отже, у Крапка Р 1 і Р 3 ...
