Зона кода

А давайте немного попрограммируем...

Примитивная графическая библиотека на C99. 2-я часть

C99Библиотека pgraph

Продолжаем создавать графическую библиотеку pgraph. В предыдущей статье мы построили ключевой тип нашей библиотеки — структуру image, создали несколько вспомогательных типов и написали функции, позволяющие осуществлять с изображениями некоторые действия. Мы уже умеем средствами библиотеки получать и изменять цвета пикселей изображения, а также записывать изображение в файл формата BMP.

На очереди — добавление к библиотеке возможностей построения прямых линий, заливки одноцветных областей, а также заливки всего изображения в целом. После решения этих задач мы напишем программу для тестирования нашей библиотеки.

Напомню, что код всех функций библиотеки мы размещаем в файле pgraph.c.

Прямые линии. Предварительные замечания

Итак, нам нужно построить функции, рисующие на изображении прямые линии. Под прямыми линиями мы здесь понимаем отрезки прямых, которые будут задаваться координатами своих вершин. По сути, мы будем окрашивать в заданный цвет пиксели изображения, лежащие на отрезках. Нашей первоначальной целью будет научиться получать наборы пикселей, подлежащих окраске.

Здесь мы прибегнем к помощи школьной математики. Из неё хорошо известно, что любая прямая, не параллельная оси ординат, может быть задана уравнением вида y = p x + q, где p и q — некоторые параметры, являющиеся характеристиками данной прямой. Как уже было сказано, мы будем иметь дело с отрезками, заданными координатами своих вершин. Предположим, например, что вершины отрезка, который нам нужно нарисовать, имеют координаты (x1, y1) и (x2, y2), где x1x2. Зададимся целью построить уравнение прямой, на которой лежит наш отрезок.

Наша задача сводится к выражению параметров p и q через координаты вершин и подстановке их в уравнение прямой. Читатель с лёгкостью решит эту задачу, поэтому не будем приводить здесь её решение, а сразу же перейдём к результату. p и q выражаются через координаты следующим образом:

p=y1-y2x1-x2, q=x1y2-x2y1x1-x2,

а уравнение прямой получается такое:

y=y1-y2x1-x2x+x1y2-x2y1x1-x2.

Итак, идея метода построения отрезков, полагаю, понятна. Все целые значения от x1 до x2 (сейчас неважно, какое из этих чисел больше) будем рассматривать как абсциссы пикселей, подлежащих окраске. А для нахождения ординат пикселей подставляем эти значения в построенное уравнение прямой вместо x, вычисляем полученные выражения и округляем до целых. Таким образом получаем искомые координаты пикселей.

Да, всё достаточно просто, но необходимо учесть два очень важных замечания.

Первое из них заключается в следующем. Если отрезок, который мы строим, не параллелен ни одной из координатных осей, то можно построить два его уравнения. В одном из них x выступает в качестве аргумента, а y — в качестве функции (такое уравнения как раз и было построено выше), а в другом — наоборот: y — это аргумент, а x — функция. Какой вариант выбрать? Оказывается, вопрос этот — не праздный, и выбор играет важную роль.

Давайте выясним, из какого количества пикселей будет состоять построенный нами отрезок. Их будет ровно столько, сколько значений принимает аргумент функции. В первом случае число пикселей будет равно |x1x2| + 1, а во втором — |y1y2| + 1. Если эти числа равны, то неважно, какую переменную назначить аргументом, а какую — функцией. Но если это не так, то в качестве аргумента нужно взять переменную, соответствующую той оси, длина проекции отрезка на которую (т. е. модуль разности координат вершин отрезка по данной оси) является наибольшей, т. е. если |x1 x2| > |y1 y2|, то в качестве аргумента берём x, а если |x1x2| < |y1y2|, то y.

Таким образом, из двух вариантов мы выбираем тот, который соответствует наибольшему количеству пикселей в составе отрезка. Если это требование нарушить, то наш отрезок, скорее всего, будет иметь разрывы, что устроить нас никак не может.

Кстати, такой выбор исключит ситуацию, когда в качестве функции берётся перемененная, ось которой параллельна отрезку (случай вырождения отрезка в точку мы сейчас не рассматриваем).

Второе замечание касается округления. Вычисленное значение функции может оказаться полуцелым числом, т. е. числом, дробная часть которого равна 0,5. В какую сторону округлять такое число? В математике в таких случаях принято производить округление в большую сторону. Но устроит ли нас такой вариант? Оказывается, нет.

Во-первых, если принять такое традиционное округление, то получится, что "конфигурация" отрезка, т. е. расположение "внутренних" его пикселей относительно вершин будет зависеть от направления осей. Не знаю, как ваше, уважаемый читатель, а моё эстетическое чувство протестует против такого подхода. Конфигурация отрезка должна определяться только взаимным расположением его вершин, и больше ничем.

А второе следует из первого. Предположим, у нас имеются два отрезка, такие, что вершины каждого их них симметричны вершинам другого относительно какой-нибудь прямой линии, параллельной одной из осей координат. Логично ожидать, что и отрезки целиком также будут симметричны друг другу относительно этой линии.

Но если в процессе вычисления координат пикселей отрезков по оси, перпендикулярной линии симметрии, происходило округление полуцелых чисел в большую сторону, то "соответствующие" друг другу пиксели с такими координатами симметричны друг другу не будут. При построении симметричных фигур, границы которых состоят из отрезков, такая асимметрия может оказаться весьма некстати.

Таким образом, при нахождении координат пикселей отрезков полуцелые числа в одних случаях нужно округлять в большую сторону, а в других — в меньшую. Договоримся поступать так: если функция возрастает, то округляем "вниз", а если убывает, то "вверх". Такой подход соответствует способу построения отрезков, используемому в графических редакторах.

Мы не стали уточнять, о какой именно функции идёт речь: о y(x) или о x(y). Это неважно. Можно легко показать, что, если возрастает (убывает) одна из них, то другая также является возрастающей (убывающей). А характер монотонности определяется знаками разностей x1x2 и y1y2. Если они имеют одинаковые знаки, то обе функции возрастают, а если разные, то убывают. Если же первая (вторая) разность равна 0, а вторая (первая) отлична от нуля, то функция y(x) (x(y)) не определена, а функция x(y) (y(x)) является постоянной. Эти утверждения также легко доказываются.

Ну что ж, теорию мы обсудили, пора перейти к практике!

Прямые линии. Вспомогательные функции

Начнём с построения вспомогательных функций. Эти функции не предназначены для непосредственного вызова пользователями библиотеки pgraph, поэтому их прототипы в заголовочном файле pgraph.h отсутствуют. Такие функции будем называть "внутренними".

Нам понадобится функция, выполняющая округление вещественных чисел до целых. Нас устроила бы стандартная библиотечная функция round(), объявленная в заголовочном файле <stdio.h>, если бы она не округляла полуцелые числа в большую сторону. Нам же требуется функция, которой мы сможем "указывать", в какую сторону производить округление. Напишем такую функцию:

//"Умное" округление (внутренняя функция)
uint smart_round(double d, bool flag)
{
    int i = d;
    if ((d - i) == 0.5)
        return flag ? i + 1 : i;
    return round(d);
}

Функция smart_round() принимает в качестве первого параметра округляемое вещественное число. Если оно оказывается полуцелым, то результат округления зависит от второго параметра. Если он равен true, то округление происходит в большую строну, а если false, то в меньшую. Если же округляемое число не полуцелое, то для его округления вызывается функция round(). Функция smart_round() возвращает округлённое число в виде значения типа uint.

Теперь переходим к функции create_line(), которая будет заниматься непосредственно построением прямой линии. Она также будет внутренней. Вот её код:

//Создание прямой линии (внутренняя функция)
void create_line(uint x1, uint y1, uint x2, uint y2,
                 uint width, color col, color pixels[])
{
    if (x1 == x2 && y1 == y2)
    {
        pixels[y2 * width + x2] = col;
        return;
    }
    int delta_x = x1 - x2, delta_y = y1 - y2;
    bool decreases = delta_x * delta_y < 0;
    if (abs(delta_x) > abs(delta_y))
    {   
        double p = delta_y / (double) delta_x;
        double q = (int) (x1 * y2 - x2 * y1) / (double) delta_x;
        int s = delta_x > 0 ? -1 : 1;
        x2 += s;
        for (uint x = x1; x != x2; x += s)
            pixels[smart_round(p * x + q, decreases) * width + x] = col;
    }
    else
    {
        double p = delta_x / (double) delta_y;
        double q = (int) (y1 * x2 - y2 * x1) / (double) delta_y;
        int s = delta_y > 0 ? -1 : 1;
        y2 += s;
        for (uint y = y1; y != y2; y += s)
            pixels[y * width + smart_round((p * y + q), decreases)] = col;
    }
}

Функция "окрашивает" пиксели изображения, лежащие на отрезке, заданным координатами своих вершин, в указанный цвет. Формальные параметры имеют следующий смысл:

  1. x1 — абсцисса первой вершины отрезка;
  2. y1 — ордината первой вершины отрезка;
  3. x2 — абсцисса второй вершины отрезка;
  4. y2 — ордината второй вершины отрезка;
  5. width — ширина изображения в пикселях;
  6. color — цвет, которым нужно закрасить пиксели;
  7. pixels — массив, содержащий цвета пикселей изображения.

Заметим, что в функции create_line() не проверяется корректность переданных ей координат. Предполагается, что данная проверка уже осуществлена в вызывающей функции.

Прокомментируем код функции.

В начале выясняется, не совпадают ли вершины отрезка. В случае совпадения единственный пиксель окрашивается в заданный цвет, после чего функция завершает работу (строки 5-9).

В противном случае вычисляются и сохраняются в переменных delta_x и delta_y разности абсцисс и ординат вершин отрезка соответственно (строка 10). Далее вычисляется значение переменной decreases (строка 11). Она будет содержать true, если функция, график которой мы строим, является убывающей. В противном случае decreases будет содержать false.

Затем с помощью инструкции if выясняется, какую переменную нужно принимать за аргумент, а какую — за функцию. В случае, если в качестве аргумента необходимо взять x, а в качестве функции — y, выполняются строки 13-20. Если наоборот, то выполняются строки 22-29. Остановимся более подробно на первом из этих фрагментов кода.

Думаю, что в общем и целом этот фрагмент понятен. Вычисляются и сохраняются в переменных p и q параметры прямой (строки 14-15), перебираются абсциссы пикселей, вычисляются их ординаты и тем элементам массива pixels, которым соответствуют эти координаты, присваивается "новый цвет" (строки 18-19). Однако внимание нужно обратить на 2 важные детали.

Первая деталь. В цикле for (см. строку 18) переменная цикла x пробегает значения от x1 до x2. Но значение переменной x2 может превышать значение переменной x1, а может, наоборот, быть меньше его. В первом случае значение x в ходе цикла должно увеличиваться, а во втором — уменьшаться. Для реализации этого мы в 16 строке вычисляем шаг изменения переменной x и присваиваем его переменной s. Шаг равен 1 в случае x1 < x2 или -1 в случае x1 > x2. Далее корректное изменение значений x обеспечивается операцией x += d.

Вторая деталь. Поскольку шаг изменения s может иметь произвольный знак, то в качестве условия окончания цикла мы должны взять равенство (а не неравенство!) переменной x определённому значению. Это значение вычисляется как сумма значений x2 и s; результат этой операции мы, чтобы не "плодить" новых переменных, присваиваем переменной x2 (см. строку 17).

Но может случиться так, что значение x2 изначально было равно 0, а значение s равно -1. Тогда, после выполнения операции сложения и присвоения результата x2, значение x2 будет равняться не -1, а 4294967295, поскольку x2 — это беззнаковое целое. Данное число является максимально возможным значением переменной типа uint.

Но в этом нет ничего страшного, поскольку в результате очередной итерации значение переменной x (которая тоже имеет тип uint) также окажется равным 4294967295, в силу чего условие продолжения цикла x != x2 нарушится, поэтому его выполнение закончится.

Построение прямых линий: функции line() и line_to()

Теперь переходим к пользовательским функциям, выполняющим построения прямых линий. Начинаем с функции line(). Вот её код:

//Проведение прямой линии из одной точки в другую
image *line(image *img, uint x1, uint y1, uint x2, uint y2)
{
    uint width = img->width, height=img->height;
    if (x1 >= width || y1 >= height || x2 >= width || y2 >= height)
        return img;
    create_line(x1, y1, x2, y2, width, img->cur_col, img->pixels);
    return img;
}

Функция принимает в качестве параметров адрес изображения, абсциссу и ординату первой вершины отрезка, а также абсциссу и ординату его второй вершины. Если координаты вершин корректны, то функция окрашивает пиксели изображения, находящиеся на отрезке, соединяющем вершины, в текущий цвет. Функция возвращает адрес изображения.

Как мы видим, работа функции line(), по сути, сводится к проверке вершин отрезка на нахождение их внутри изображения и вызове функции create_line().

Вторая функция — line_to(). Её программный код приведён ниже.

//Проведение прямой линии из текущей точки в заданную
image *line_to(image *img, uint x, uint y)
{
    uint x1 = img->cur_pnt.x, y1 = img->cur_pnt.y;
    uint width = img->width;    
    if (x >= width || y >= img->height)
        return img;
    create_line(x1, y1, x, y, width, img->cur_col, img->pixels);    
    img->cur_pnt = (point) {x, y};
    return img;
}

Функция принимает в качестве параметров адрес изображения, абсциссу и ординату одной вершины отрезка. Если координаты вершины корректны, то функция окрашивает пиксели изображения, находящиеся на отрезке, соединяющем текущую точку и заданную вершину, в текущий цвет, после чего изменяет текущую точку: новой текущей точкой становится заданная вершина. Функция возвращает адрес изображения.

Как мы видим, различия между функциями line() и line_to() минимальны и заключаются в использовании второй функцией в качестве одной из вершин отрезка текущей точки. Благодаря этому количество параметров второй функции меньше, чем у первой. Функцию line_to() удобно использовать для построения одноцветных ломаных.

Заливка одноцветных областей. Предварительные замечания

Перед тем, как говорить о заливке, нам нужно договориться об использовании определённых терминов.

Соседними пикселями будем называть два пикселя, если их координаты по одной оси совпадают, а по другой — различаются на единицу. Например, пиксели с координатами (1, 2) и (1, 3) являются соседними; таковыми же являются и пиксели с координатами (1, 2) и (0, 2). А вот пиксели с координатами (1, 2) и (2, 3) друг с другом не соседствуют.

Одноцветными областями будем называть наборы одинаковых по цвету пикселей, обладающие следующим свойством: любые два пикселя из набора можно соединить ломаной, звенья которой параллельны осям координат, состоящей целиком из пикселей, принадлежащих набору. Но в дальнейшем мы будем рассматривать только такие одноцветные области, которые удовлетворяют дополнительному условию: любой пиксель, соседствующий с пикселем из области, или имеет цвет, отличный от цвета области, или принадлежит области.

Заливкой такой одноцветной области будем называть процесс "покраски" всех пикселей области в один и тот же цвет. Этот цвет будем называть, для определённости, новым, а изначальный цвет области (до заливки) назовём старым.

Итак, какая информация нужна для того, чтобы залить одноцветную область заданного изображения? Очевидно, что для идентификации области будет достаточно знать координаты одного её пикселя (назовём его начальным). По нему можно восстановить все остальные пиксели области. Разумеется, также нужно знать цвет, которым необходимо залить область.

Таким образом, наша цель — построить функцию, которая заливает одноцветную область изображения, имеющую пиксель с заданными координатами, заданным цветом.

Полагаю, что примерный план действий читателю уже понятен. Закрашиваем начальный пиксель, находим всех его соседей, принадлежащих области, закрашиваем их, закрашиваем пиксели, являющиеся соседями соседей и т. д., до тех пор, пока все пиксели области не будут закрашены.

Но этот план слишком уж "примерный". А нам нужен алгоритм. Давайте его построим.

Но сначала сделаем предварительное замечание. Для реализации алгоритма нам потребуется некое "хранилище информации", изначально пустое. В него мы будем помещать в ходе алгоритма информацию о пикселях и извлекать её оттуда (после извлечения она в хранилище не остаётся). О том, как именно будет реализовано само хранилище, поговорим попозже. А сейчас — алгоритм.

Алгоритм закраски одноцветной области.

  • Шаг 1. Выясняем новый цвет по цвету начального пикселя.
  • Шаг 2. Если новый и старый цвета совпадают, то прекращаем работу алгоритма. В противном случае переходим к шагу 3.
  • Шаг 3. Помещаем информацию о начальном пикселе (его координаты и цвет) в хранилище.
  • Шаг 4. Извлекаем информацию о пикселе из хранилища. Если цвет этого пикселя — новый, то переходим к шагу 5. В противном случае закрашиваем данный пиксель новым цветом, перебираем всех его соседей, и информацию о тех из них, цвет которых — старый, помещаем в хранилище.
  • Шаг 5. Если хранилище пустое, то прекращаем работу алгоритма. В противном случае переходим к шагу 4.

Обратите внимание на начало 4-го шага. Ничего не сказано о том, информацию о каком именно пикселе нужно извлечь. Дело в том, что это совершенно неважно.

А ещё обратите внимание на второе предложение 4-го шага. Можно было бы не выяснять цвет пикселя, о котором идёт речь, а сразу же закрасить его новым цветом и перейти к перебору соседей.

Но дело в том, что информация об одном пикселе может быть размещена в хранилище дважды, например, из-за того, что он является общим соседом двух подряд окрашенных пикселей. Предположим, теперь, что один раз информация об этом пикселе уже была извлечена, он был окрашен в новый цвет, и соседи, окрашенные в старый цвет, уже "обработаны" (т. е. информация о них помещена в хранилище).

Если мы теперь, при втором извлечении информации о данном пикселе, не обратим внимание на его цвет, повторно его окрасим и повторно обработаем соседей, то, при условии, что к этому моменту информация о соседях (всех или некоторых), ещё не была извлечена, она снова будет помещена в хранилище, что приведёт к появлению дублей. Мы всё равно, в итоге, достигнем цели, но время работы алгоритма увеличится, что нам совершенно ни к чему.

Именно поэтому мы выясняем цвет пикселя на 4-м шаге.

А теперь давайте обсудим детали реализации алгоритма.

В качестве информации о пикселе, которую мы будем помещать в хранилище и извлекать оттуда, мы возьмём его координаты, т. е. значение типа point. Цвет пикселя всегда можно узнать по его координатам, поэтому помещать его в хранилище мы не будем.

Теперь о хранилище. Оно должно быть структурой данных с динамически изменяемым размером, позволяющей помещать туда значения типа point и извлекать их. Поскольку порядок извлечения неважен, такой структурой может быть и очередь, и стек, и дек.

Но не зря же полдесятка статей этого сайта были посвящены разработке стеков! Поэтому наш выбор очевиден. К тому же, ни очередей, ни деков, под рукой у нас нет.

Значения типа point имеют небольшой размер, а хранить значения других типов в стеке не требуется. По этим причинам наш стек будет кастомизированным, а его базовым типом будет point.

А теперь переходим к построению функций.

Заливка одноцветных областей. Вспомогательные функции

В процессе реализации алгоритма заливки нам придётся постоянно выяснять, совпадают ли два цвета, или нет. К сожалению, стандартом C99 операция == не поддерживается для значений структурного типа. Поэтому самостоятельно создадим соответствующую функцию:

//Проверка двух цветов на совпадение (внутренняя функция)
bool col_cmp(color col1, color col2)
{
    return col1.red == col2.red && col1.green == col2.green && col1.blue == col2.blue;
}

Функция col_cmp() принимает в качестве параметров 2 значения типа color. Она возвращает true, если значения совпадают (или, что то же самое, совпадают значения их полей) или false в противном случае.

Поскольку в функции, выполняющей заливку, будет использоваться стек, нам нужно обеспечить доступ к соответствующим типам и функциям. Обратимся к библиотеке custom_stack; её можно скачать по ссылке, завершающей статью "Кастомизация стека". Нам понадобятся только два файла, входящих в её состав: custom_stack.h и custom_stack.c. С последним из них поступим довольно бесцеремонно: скопируем из него нужные функции и вставим в файл pgraph.с.

Мы будем использовать лишь функции push() иpop(). Первая из них заталкивает значения в стек, а вторая — выталкивает их из него. Но из этих функций вызываются вспомогательные функции void_stack() и pmalloc(), поэтому в файл pgraph.с поместим и их тоже.

Ниже приведён код всех четырёх функций.

//-------Функции для работы с кастомизированным стеком-------------------

//Функция, прекращающая работу программы в случае попытки
//прочитать элемент пустого стека или вытолкнуть элемент
//из пустого стека
void void_stack()
{
    printf("Попытка обращения к верхнему элементу несуществующего стека\n");
    printf("Работа программы прекращена\n");
    exit(1);
}

//Функция, динамически выделяющая память размера size
//и возвращающая адрес выделенного участка в случае успеха,
//или завершающая работу программы в случае неудачи
void *pmalloc(size_t size)
{
    void *p = malloc(size);
    if (p)
        return p;
    printf("Недостаточно памяти. Работа программы прекращена\n");
    exit(1);
}

//Функция, проталкивающая в стек stack элемент element
//и возвращающая новое значение стековой переменной
node *push(node *stack, el_type element) 
{
    node *new_node = pmalloc(sizeof(node));       //Выделяем память на новый узел
    new_node->element = element;                  //Присваиваем значения
    new_node->next = stack;                       //его полям
    return new_node;                              //Возвращаем адрес созданного узла
}

//Функция, выталкивающая из стека верхний элемент
el_type pop(node **pstack)                     //Формальный параметр назовём pstack, чтобы
{                                              //подчеркнуть, что это адрес стековой переменной
    if (*pstack)                               //Если стек непустой
    {
        node *first_node = *pstack;            //Извлекаем 1-й узел списка
        *pstack = first_node->next;            //Помещаем в стековую переменную адрес 2-го узла
        el_type element = first_node->element; //Извлекаем из 1-го узла верхний элемент стека
        free(first_node);                      //Удаляем узел
        return element;                        //Возвращаем верхний элемент стека
    }
    void_stack();                              //Если стек пуст, то прекращаем работу программы
}

Эти функции непосредственного отношения к работе с графикой не имеют, и, чтобы они "не мешались", я решил поместить их в самый конец файла pgraph.с. Остальные функции, которые будут помещены в данный файл в дальнейшем, будут располагаться перед этими четырьмя.

Файл custom_stack.c нам больше не нужен. Теперь нам потребуется файл custom_stack.h, ведь в нём описан тип node и расположены прототипы функций push() и pop(). Остальное содержимое файла custom_stack.h является для нас лишним. Поэтому удалим из него все директивы препроцессора и прототипы остальных функций. В результате содержимое файла будет следующим:

struct node
{
    el_type element;         //Указатель, содержащий элемент стека
    struct node *next;       //Указатель на следующий узел
};
     
typedef struct node node;    //Для удобства введём короткое обозначение для struct node

node *push(node *stack, el_type element);
el_type pop(node **pstack);

Файл custom_stack.h будет частью нашего проекта. Нам нужно подключить его к файлу pgraph.c с помощью директивы #include, не забыв до этого определить посредством #define макрос element, означающий базовый тип нашего стека. Напомню, что таковым является тип point.

Ниже приведены начальные строки файла pgraph.c, содержащие директивы препроцессора.

#include "pgraph.h"
#define el_type point
#include "custom_stack.h"

Вспомогательные функции, необходимые для реализации алгоритма заливки, построены. Обратите внимание на то, что все они являются внутренними. А теперь переходим непосредственно к самой реализации алгоритма.

Заливка одноцветных областей: функция fill()

Вот код функции, выполняющей заливку:

//Заливка одноцветной области заданным цветом
image *fill(image *img, uint x, uint y, color col)
{
    uint width = img->width, height = img->height;
    if (x >= width && y >= height)
        return img;
    color *pixels = img->pixels, old_col = pixels[y * width + x];
    if (col_cmp(col, old_col))
        return img;
    node *stack = 0;
    stack = push(stack, (point) {x, y});
    do
    {
        point pnt = pop(&stack);
        uint x = pnt.x, y = pnt.y;
        if (col_cmp(pixels[y * width + x], col))
            continue;
        pixels[y * width + x] = col;
        if (x < width && col_cmp(pixels[y * width + x + 1], old_col))
            stack = push(stack, (point) {x + 1, y});
        if (x > 0 && col_cmp(pixels[y * width + x - 1], old_col))
            stack = push(stack, (point) {x - 1, y});
        if (y < height && col_cmp(pixels[(y + 1) * width + x], old_col))
            stack = push(stack, (point) {x, y + 1});
        if (y > 0 && col_cmp(pixels[(y - 1) * width + x], old_col))
            stack = push(stack, (point) {x, y - 1});
    }
    while(stack);
    return img;
}

Функция fill() принимает в качестве параметров адрес изображения, абсциссу и ординату начальной точки, а также цвет заливки. Если координаты заданы корректно, то функция осуществляет заливку одноцветной области, которой принадлежит начальная точка, заданным цветом. Функция возвращает адрес изображения.

Думаю, что код функции достаточно понятен. В строках 4 и 7 вводим вспомогательные переменные width, height и pixels, позволяющие избежать обращений к полям переменной, адресуемой указателем img. В строках 5 и 6 проверяем корректность координат начальной точки и прекращаем работу функции, если они эту проверку не проходят.

Непосредственная реализация алгоритма начинается с инициализации переменной old_col, в которую помещается старый цвет (см. строку 7). Если он совпадет с новым, то работа завершается (строки 8, 9). Если нет, то создаётся стек (строка 10), в который заталкивается начальная точка (строка 11).

Далее в цикле do while реализуются 4-й и 5-й шаги алгоритма. В строке 14 из стека выталкивается точка, в строках 16 и 17 соответствующий ей пиксель проверяется на "закрашенность" новым цветом, причём, если таковая имеет место быть, то текущая итерация завершается. В противном случае закрашиваем пиксель (строка 18) и перебираем соседние пиксели в строках 19-26, сравнивая их цвета со старым цветом с помощью функции col_cmp(). В случае совпадения цветов, точки, соответствующие пикселям, "отправляются" в стек.

Обратите внимание на то, что у некоторых пикселей могут отсутствовать соседи с одной или двух сторон. Такие "несуществующие" соседи, разумеется, исключаются из рассмотрения (см. условные выражения, входящие в операторы if).

Условием окончания цикла является опустошение стека (строка 28).

Заливка всего изображения заданным цветом: функция fill_all()

Как мы помним, функция create_image() после создания изображения закрашивает его белым цветом. Но в ходе обработки изображения может возникнуть необходимость его повторной полной окраски. Данная возможность реализована в функции fill_all():

//Заливка всего изображения заданным цветом
image *fill_all(image *img, color col)
{
    uint wh = img->width * img->height;
    for (uint i = 0; i < wh; i++)
        img->pixels[i] = col;
    return img;
}

Функция принимает в качестве параметра адрес изображения и цвет заливки. Она закрашивает все пиксели изображения заданным цветом и возвращает адрес изображения. Полагаю, что в комментировании её кода необходимости нет.

На этом разработка библиотеки pgraph закончена. Переходим к её тестированию.

Тестирующая программа

Напишем программу для тестирования библиотеки pgraph. Программа создаст изображение размером 401 x 301 (размер задан в пикселях) и нанесёт на него светло-голубые вертикальные и горизонтальные линии, имитирующие тетрадную "клетку". Далее будет построена прямоугольная система координат, центр которой совпадёт с центром изображения. За единицу по каждой из осей будет принята упятерённая длина стороны одной "клетки". В этой системе координат будут построены график функции y = sin(x) и окружность радиуса 2 с центром в начале координат. Синусоида будет красной, а окружность — зелёной. Наконец, область, расположенная в правой координатной полуплоскости и ограниченная синусоидой, окружностью и осью абсцисс, будет залита светло-серым цветом.

После создания изображения оно будет сохранено в файле test.bmp и помещено в тот каталог, из которого запущен исполняемый файл программы.

Программа будет состоять из единственной функции main(), содержащейся в файле pgraph_test.c, к которому будет подключён посредством директивы #include заголовочный файл pgraph.h. Ниже приведено содержимое файла pgraph_test.c.

#include "pgraph.h"

int main()
{
    image *img = create_image(401, 301);        //Создание изображения

    set_cur_col(img, (color) {153, 217, 234});  //Текущий цвет - светло-голубой

    for (uint i = 0; i <= 400; i += 10)         //Вертикальные
        line(img, i, 0, i, 300);                //линии

    for (uint i = 0; i <= 300; i += 10)         //Горизонтальные
        line(img, 0, i, 400, i);                //линии

    set_cur_col(img, BLACK);                    //Текущий цвет - чёрный

    line(img, 0, 150, 400, 150);                //Ось абсцисс

    line_to(set_cur_pnt(img, 390, 155), 400, 150);  //Cтрелка на
    line_to(img, 390, 145);                     //оси абсцисс

    line(img, 200, 0, 200, 300);                //Ось ординат

    line_to(set_cur_pnt(img, 195, 290), 200, 300);  //Cтрелка на
    line_to(img, 205, 290);                     //оси ординат

    set_cur_col(img, RED);                      //Текущий цвет - красный

    //Построение синусоиды
    set_cur_pnt(img, 0, (int) round (150 + 50 * sin (-4)));
    for (int x = 0; x < 401; x++)
    {
        int y = round (150 +   50 * sin ((x-200) / 50.0));
        line_to(img, x, y);
    }

    //Построение окружности
    double delta = 3.141592653589793 / 200;
    set_cur_col(img, GREEN);
    set_cur_pnt(img, 300, 150);
    for (int n = 0; n <= 400; n++)
    {
        int x = round(200 + 100 * cos (n * delta));
        int y = round(150 + 100 * sin (n * delta));
        line_to(img, x, y);
    }

    fill(img, 220, 160, WHITE);                 //Удаление решётки
    fill(img, 210, 155, WHITE);                 //Удаление остатков решётки
    fill(img, 220, 160, SILVER);                //Заливка области серым цветом

    if (!save_to_file(img, "test.bmp"))         //Запись изображения в файл
        puts("Не удалось сохранить файл");

    free(img);                                  //Удаление изображения

    return 0;
}

Действия, выполняемые программой, кратко прокомментированы прямо в коде. Обратите внимание на то, что синусоида и окружность строятся по-разному. В первом случае используется уравнение кривой, в котором y выражено через x. А во втором задействованы параметрические уравнения кривой. Заметим, ещё, что в обоих случаях кривые конструируются не из точек, а из отрезков. По сути, кривые изображаются в виде ломаных. Такой подход помогает избежать разрывов в изображениях кривых.

В результате работы программы в директории исполняемого файла появляется графический файл temp.bmp, опубликованный ниже (для публикации в Сети он был преобразован в формат PNG).

Синусоида и окружность

Результат выполнения тестирующей программы

В программе протестировано большинство функций библиотеки pgraph. Остальные функции читатель может протестировать самостоятельно.

Заключение

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

А наличие уже имеющихся функций открывает широкий простор для построения на C99 приложений, генерирующих растровую двухмерную графику. Думаю, что библиотека pgraph будет ещё неоднократно задействована в новых статьях.

Скачать исходный код