in this paper, a filling algorithm with a list of edges and a flag is implemented, and the algorithm execution time is also measured.
algorithm, filling, algorithm running time
Алгоритм заполнения со списком рёбер и флагом [1]
Одной из отличительных черт данного алгоритма – наличие флага, который является признаком расположения пикселя внутри или вне многоугольника.
Сам алгоритм состоит из двух этапов, шагов.
Первый шаг – отрисовывается контур, который ограничивает область. А второй – само заполнение (заполнение областей располагающихся между ограничивающими пикселями).
На первом этапе обрабатываются рёбра многоугольника, путём применения множества сканирующих строк. Производятся вычисления точек пересечения ребра и сканирующей строки (для наибольшей эффективности реализуется итеративный способ, чтобы избежать дополнительных затратных вычислений). После этого вычисляется самый левый пиксель, расположенный справа от точки пересечения.
Таким образом, получается контур фигуры.
На втором этапе осуществляется проход по сканирующим строкам, в процессе которого анализируется положение очередного пикселя. Флаг, равный лжи (False), является признаком того, что пиксель не принадлежит области заполнения, а если он равен истине (True), то наоборот, принадлежит. На основе этого признака пикселю присваивается либо цвет фона, либо цвет многоугольника. В начале программы флаг равен значению лжи (False).
Сам признак меняется, когда очередной пиксель имеет граничное значение.
Важный момент
На момент отрисовки контура может возникнуть следующая ситуация: при достаточно малых углах ребра могут “сливаться”, т.е. иметь 1 (или больше, если угол очень маленький по величине) общий пиксель. Это значит, что признак не изменится в нужный момент. Чтобы избежать этой проблемы, нужно в процессе работы проверить эту ситуацию, и если она возникает, то следует высветить соседний пиксель.
Преимущества алгоритма
Одно из главных преимуществ является то, что каждый пиксель обрабатывается только 1 раз (что очень сильно сокращает временные затраты по сравнению с другими алгоритмами).
Кроме того, в этом алгоритме не требуется сортировка рёбер (следовательно, не тратится и время на это).
Реализация
Отрисовка контура фигуры (рисунок 1).
Рисунок 1 – отрисовка контура фигуры
Заполнение (перед этим были вычислены значения min_x/min_y, max_x/max_y – параметры прямоугольной оболочки) (рисунок 2).
Рисунок 2 – заполнение
В конце условие для задержек, которые можно задать в начале работы; при задержке, равной нулю, фигура будет отрисовываться в обычном режиме.
Анализ времени
Производится анализ зависимости времени работы алгоритма от площади заданной фигуры. В качестве примера был взят квадрат. По оси ОХ указано значение площади (рисунок 3).
Рисунок 3 – зависимость времени работы от площади
На основе этого графика можно сделать вывод о том, что время работы линейно зависит от площади фигуры.
1. ACKLAND B. D., WESTE N.: The edge flag algorithm - a fill method for raster scan displays. IEEE Trans. Computers 30, 1 (1981), 41–48.
2. FOLEY J. D., VAN DAM A., FEINER S. K., HUGHES J. F.: Computer graphics: principles and practice (2nd ed.). Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1990.
Authors: Bayramova Aygyun Seymur kyzy
