Алгоритмы заливки

• SoUrcerer

  Posts 2810

  Joined: Mon Sep 24, 2007 11:11 am

  Fri Jan 21, 2011 2:25 pm

  Алгоритмы заливки, ясное дело, бывают разные. Пытаюсь составить алгоритм, который был бы нетребователен к памяти и довольно быстр.
  Итак, я попробовал сделать алгоритм, закрашивающий замкнутые области, в том числе с отверстиями внутри, при условии, что отверстия имеют размер хотя бы 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, и посмотреть, насколько быстро работает

  • Quote

     BBB ? BBB ?
   BB...BBB.?.B
   B.....B..?.B
   BBB......BB
      BBBBBB ?

art_zh Kernel Developer

Posts 1465

Joined: Fri Aug 14, 2009 1:46 am

Fri Jan 21, 2011 7:11 pm

Sorcerer wrote:Почему векторные изображения нужно как-то иначе заливать? Ведь на экране все равно мы будем иметь растр? Можно ведь растрировать векторную картинку, и залить... Или есть более правильные решения?

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

А вопросительными знаками я обозначил фрагменты, на которых твой алгоритм может сбоить.
Надо как-то проверять контур на выпуклость/вогнутость.
И проще всего это делать в векторном режиме

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

• Quote

SoUrcerer

Posts 2810

Joined: Mon Sep 24, 2007 11:11 am

Fri Jan 21, 2011 8:02 pm

Так контур и проверяется Здесь обводка (т.е. пиксели типа 1) - это действительно обводка, а не просто закрашенные пиксели. Она как раз учитывает изгибы, выпуклые и вогнутые части фигуры, и может закрашивать, например, контуры с волнистым краем.
Сейчас выложу версию, где можно править карты вручную (правда, сделал это на скорую руку, не судите строго).
А вот и ссылка для экспериментов. Если еще не работает, то скоро будет
UPD: хотя, некоторые спорные места в алгоритме все же есть.

• Quote

SoUrcerer

Posts 2810

Joined: Mon Sep 24, 2007 11:11 am

Fri Jan 21, 2011 8:18 pm

Хм. А вот если предложенный контур повернуть.... Что будет, интересно.
Портится вся малина Пошел думать над алгоритмом дальше

(А портится она из-за того, что слежение "внутри контура"/"снаружи контура" ведется только по одной оси)

Может быть, у кого-нибудь есть идеи лучше?

• Quote

fin=0;x=k;y=100;l=0;
while (fin!=1) {
if (m[x+1][y]==2) {m[x+1][y]=3;x=x+1;} //2 - синий, 3 - зеленый
if (m[x-1][y]==2) {m[x-1][y]=3;x=x-1;} //Можно было бы не проверять прошлую клетку, но это потребовало бы еще один if, так какая разница?
if (m[x][y+1]==2) {m[x][y+1]=3;y=y+1;}
if (m[x][y-1]==2) {m[x][y-1]=3;y=y-1;}
if ((x==k)&&(y==99)) {fin=1;}}

for (z=0;z<160;++z){ //повторять до просветления
for (y=0;y<299;++y){
for (x=0;x<299;++x){
if (m[x][y]==3) {if (m[x-1][y]==2) {m[x-1][y]=3;}; if (m[x+1][y]==2) {m[x+1][y]=3;}; if (m[x][y-1]==2) {m[x][y-1]=3;}; if (m[x][y+1]==2) {m[x][y+1]=3;}}}}}

____1_____
___1*2____
__1***2___
__1****2__
___1111*2_
_______12_

    _____
   /   __  \
  /   /_1\  \
 /    _ _     \
/_2/      \ __\