Алгоритмы заливки
Posted: Fri Jan 21, 2011 2:25 pm
Алгоритмы заливки, ясное дело, бывают разные. Пытаюсь составить алгоритм, который был бы нетребователен к памяти и довольно быстр.
Итак, я попробовал сделать алгоритм, закрашивающий замкнутые области, в том числе с отверстиями внутри, при условии, что отверстия имеют размер хотя бы 1x1 пиксел и окружены границей минимум в 1 пиксел.
Изображение сканируется построчно, причем в некоторых случаях проверяется, будет ли иметься возможность закрашивания других точек в этой строке. Пространства для оптимизации море (например, выходить из цикла для строки, когда в строке достоверно больше не остается точек для закрашивания).
На JS это выглядит так:
Посмотреть на работающий пример!
Если хватит упертости, попробую сделать это на fasm, и посмотреть, насколько быстро работает
Итак, я попробовал сделать алгоритм, закрашивающий замкнутые области, в том числе с отверстиями внутри, при условии, что отверстия имеют размер хотя бы 1x1 пиксел и окружены границей минимум в 1 пиксел.
Изображение сканируется построчно, причем в некоторых случаях проверяется, будет ли иметься возможность закрашивания других точек в этой строке. Пространства для оптимизации море (например, выходить из цикла для строки, когда в строке достоверно больше не остается точек для закрашивания).
На JS это выглядит так:
Code: Select all
function flood(){ //заливка
for (y=0;y<maxy;y++){ //выполняем для каждой строки
fill=0; //строка не может начинаться с заливки
for (x=0;x<maxx;x++){ //для каждой точки в строке
if ((m[x][y]==1)&&(m[x+1][y]==1)) {fill=0;} else { //если текущая точка - граничная, и следующая - тоже граничная, то закрашивать следующую точку не нужно
if (m[x][y]==1&&(scanend(x,y)==1)) {fill==1 ? fill=0 : fill=1} //если текущая точка граничная, но за ней незакрашенная точка, а впереди есть граничные точки, то изменим положение пера (опущено/поднято) на противоположное. Таким образом, если мы встречаем первую граничную точку в строке, за которой можно закрашивать, то мы опускаем перо (т.е. мы во внутреннем контуре). Следующая за ней граничная точка, очевидно, показывает на окончание внутреннего контура, и мы поднимаем перо.
if (m[x][y]==1&&(scanend(x,y)==0)) {fill=0;} //если текущая точка граничная, но за ней нет граничных точек в строке, то заливать ничего не нужно
if ((m[x][y]==0)&&(fill==1)) {m[x][y]=2;}} //если текущая точка свободна, и перо опущено, то закрасим её
draw(x,y);}}} //отрисовка для пошаговой отладки, можно убрать
function scanend(x,y){
var xx=0; //сбросим значение функции
for (i=x+1;i<maxx;i++){ //для всех оставшихся точек в строке
if (m[i][y]==1) {xx=1;}} //если хоть одна граничная точка есть, то еще что-то можно закрасить
return xx;}
Если хватит упертости, попробую сделать это на fasm, и посмотреть, насколько быстро работает
Здесь обводка (т.е. пиксели типа 1) - это действительно обводка, а не просто закрашенные пиксели. Она как раз учитывает изгибы, выпуклые и вогнутые части фигуры, и может закрашивать, например, контуры с волнистым краем.
Пошел думать над алгоритмом дальше