На этом шаге мы приведем реализацию данного алгоритма.
Алгоритм был разработан авторами работы [1] и предназначался для расчета центра тяжести объектов по соответствующим изображениям. Идея была навеяна волновым алгоритмом поиска трассы на графе, известным в САПР электронных схем. Суть подобных алгоритмов состоит в том, что для начальной точки (вершины на графе) находятся соседние точки (другие вершины), которые отвечают двум условиям: во-первых - эти вершины связаны с начальной; во-вторых - эти вершины еще не отмечены, то есть они рассматриваются впервые. Соседние вершины текущей итерации отмечаются в массиве описания вершин, и каждая из них становится текущей точкой для поиска новых соседних вершин в следующей итерации. Если в специальном массиве отмечать каждую вершину номером итерации, то когда будет достигнута конечная точка, можно совершить обратный цикл - от конечной точки к начальной по убыванию номеров итераций. В ходе обратного цикла и находятся все кратчайшие пути (если их несколько) между двумя заданными точками на графе. Подобный алгоритм можно также использовать, например, для поиска всех нужных файлов на диске. Относительно закрашивания растровых фигур, то здесь вершинами графа являются пиксели, а отметка пройденных пикселей делается прямо в растре цветом закрашивания. Как видим, это почти полностью повторяет идею предыдущего простейшего алгоритма, однако здесь мы не будем использовать рекурсию. Это обуславливает совсем другую последовательность обработки пикселей при закрашивании.
Запишем волновой алгоритм закрашивания на языке C++ с использованием графических функций API Windows.
void WaveFill(HDC hdc,int xst, int yst) { int numA,numB; POINT *stackA, *stackB; stackA=new POINT[10000]; // Открываем массивы stackB=new POINT[10000]; // для текущих фронтов волн numA=1; stackA[0].x=xst; // В массив stackA записываем stackA[0].y=yst; // координаты стартовой точки numB=0; // Массив stackB пока что пуст while (1) // Основной цикл { if (numA>0) OneStep(hdc,&numA,&numB,stackA,stackB); else break; if (numB>0) OneStep(hdc,&numB,&numA,stackB,stackA); else break; } delete[]stackB; delete[]stackA; } // ----------- Одна итерация (фронт) распространения волны ------------ // Из массива Src[] читаются координаты пройденных точек // для каждой точки находится соседняя и записывается // в массив Dest[] - в этом массиве будет новый фронт void OneStep(HDC hdc, int *numSrc, int *numDest, POINT *Src, POINT* Dest) { int x,y,i; *numDest=0; for(i=0;i<*numSrc;i++) { x=Src[i].x; y=Src[i].y; NearPix(hdc,x+1,y,numDest,Dest); NearPix(hdc,x-1,y,numDest,Dest); NearPix(hdc,x,y+1,numDest,Dest); NearPix(hdc,x,y-1,numDest,Dest); } } void NearPix(HDC hdc, int x, int y, int *numStack, POINT *Stack) { if (GetPixel(hdc,x,y)!=0) { SetPixel (hdc,x,y,0); // Пиксель закрашивания for (int e=0; e<1000; e++) for (int t=0; t<1000;t++) Stack[*numStack].x=x; // Координаты в массив Stack[*numStack].y=y; (*numStack)++; // Количество элементов в массиве } }
Здесь цвет закрашивания и цвет контура - черный цвет (код 0). Пример работы алгоритма приведен на рисунке 1.
Рис.1. Результат работы приложения
От начальной точки распространяется волна пикселей закрашивания в виде ромба. В одном цикле OneStep закрашиваются пиксели вдоль линии периметра ромба (или нескольких ромбов в зависимости от сложности фигуры). В качестве рабочих массивов для текущего сохранения координат пикселей фронтов волн использованы динамические массивы емкостью по 10 000 элементов. Максимальная емкость массивов обуславливается размерами контура и рассчитывается эмпирически.
Достаточно просто модифицировать приведенный алгоритм для случая отличающихся цветов контура и заполнения.
Необходимо заметить, что этот алгоритм не является самым быстрым из известных алгоритмов закрашивания, особенно если для его реализации использовать медленную функцию SetPixel для рисования отдельных пикселей в программах для Windows. Большую скорость закрашивания обеспечивают алгоритмы, которые обрабатывают не отдельные пиксели, а сразу большие блоки из многих пикселей, которые образовывают прямоугольники или линии.
(1)Блинова Т.А., Порев В.Н. Алгоритм определения центров яркости и площадей объектов полутоновых изображений // Тезисы докладов школы-семинара "Обработка изображений в цифровых системах". - Киев: 1992, с. 4-6.
На следующем шаге мы рассмотрим алгоритм закрашивания линиями.
