Реферат: Алгоритм Брезенхема
finish
Розгляд випадків для узагальненого алгоритму Брезенхема
Для ілюстрації розглянемо відрізок із точки (0, 0) у точку (-8, -4).
початкові установки
x=0
y=0
Dx=8
Dy=4
s1=-1
s2=-1
Обмін=0
е=0
Результати роботи покрокового циклу
| i | Plot | е | x | y |
| 0 | 0 | 0 | ||
| 1 | (0,0) | |||
| -16 | 0 | -1 | ||
| -8 | -1 | -1 | ||
| 2 | (-1, – 1) | |||
| 0 | -2 | -1 | ||
| 3 | (-2, – 1) | |||
| -16 | -2 | -2 | ||
| -8 | -3 | -2 | ||
| 4 | (-3,2) | |||
| 0 | -4 | -2 | ||
| 5 | (-4,2) | |||
| -16 | -4 | -3 | ||
| -8 | -5 | -3 | ||
| 6 | (-5, – 3) | |||
| 0 | -6 | -3 | ||
| 7 | (-6, – 3) | |||
| -16 | -6 | -4 | ||
| -8 | -7 | -4 | ||
| 8 | (-7, – 4) | |||
| 0 | -8 | -4 |
Результат роботи узагальненого алгоритму Брезенхема в третьому квадранті
На рис. 4.2 показаний результат. Порівнюючи з рис. 2.2 бачимо, що результати роботи двох алгоритмів відрізняються.
3. Алгоритм Брезенхема для генерації кола
У растр потрібно розкладати не тільки лінійні, але й інші, більш складні функції. Розкладанню конічних перетинів, тобто кіл, еліпсів, парабол, гіпербол, було присвячено значне число робіт. Найбільша увага, зрозуміло, приділена колу. Один з найбільш ефективних і простих для розуміння алгоритмів генерації кола належить Брезенхему. Для початку відмітимо, що необхідно згенерувати тільки одну восьму частину кола. Інші його частини можуть бути отримані послідовними відображеннями, як це показано на рис. 5.1. Якщо згенерований перший октант (від 0 до 45° проти годинникової стрілки), то другий октант можна отримати дзеркальним відображенням відносно прямої y=х, що дає в сукупності перший квадрант. Перший квадрант відбивається відносно прямої х=0 для отримання відповідної частини кола в другому квадранті. Верхнє півколо відбивається відносно прямої y=0 для завершення побудови. На рис. 5.1 наведені двовимірні матриці відповідних перетворень.
Генерація повного кола з дуги в першому октанті
Для виведення алгоритму розглянемо першу чверть кола з центром у початку координат. Помітимо, що якщо робота алгоритму починається в точці х=0, у=R, то при генерації кола за годинниковою стрілкою в першому квадранті у є монотонно спадною функцією аргумента х (рис. 5.2). Аналогічно, якщо вихідною точкою є у= 0, х =R, то при генерації кола проти годинникової стрілки х буде монотонно спадною функцією аргументу у. У нашому випадку вибирається генерація за годинниковою стрілкою з початком у точці х =0, у=R. Передбачається, що центр кола і початкова точка знаходяться точно в точках растра.
Для будь-якої заданої точки на колі при генерації за годинниковою стрілкою існує тільки три можливості вибрати наступний піксел, що щонайкраще наближає коло: горизонтально вправо, по діагоналі вниз і вправо, вертикально вниз. На рис. 5.3 ці напрямки позначені відповідно mH , mD , mV . Алгоритм вибирає піксел, для якого мінімальний квадрат відстані між одним з цих положень і колом, тобто мінімум з
mH =|(xi +1)2 +(yi )2 -R2 |
mD =|(xi +1)2 +(yi -1)2 -R2 |
mV =|(xi )2 +(yi -1)2 -R2 |
Різниця між квадратами відстаней від центра кола до діагонального піксела (xi +1, уi - 1) і від центра до точки на колі R2 дорівнює
Di =(xi +1)2 +(yi -1)2 -R2
Як і в алгоритмі Брезенхема для відрізка, для вибору відповідного піксела бажано використовувати тільки знак похибки, а не її величину.