Friday, December 11, 2009

Area Filling Algorithms (seed filling, ScanLine conversion)



  1. #include <graphics.h>


  2. #include <iostream>





  3. #define ROUND(x) ((int)(x+0.5))





  4. typedef int Point[2];           // P[0] - x coordinate P[1] - y coordinate





  5. void seedFill(int x, int y, int color) {


  6.      if(x > 640 || x < 0 || y > 480 || y < 0)


  7.           return;


  8.      if(getpixel(x, y) == BLACK) {


  9.                        putpixel(x, y, color);


  10.                        seedFill(x+1, y, color);


  11.                        seedFill(x-1, y, color);


  12.                        seedFill(x, y+1, color);


  13.                        seedFill(x, y-1, color);


  14.      }


  15. }





  16. void scanlineFill(Point *polygon, int nodes, int color) {


  17.      setcolor(color);


  18.      Point array[480];


  19.      for(int i=0; i<480; ++i) {


  20.              array[i][0] = 640;


  21.              array[i][1] = 0;


  22.      }


  23.    


  24.      for(int i=0; i<nodes; ++i){


  25.              Point p1, p2;


  26.              p1[0] = polygon[i][0];   p1[1] = polygon[i][1];


  27.              p2[0] = polygon[(i+1)%nodes][0];               p2[1] = polygon[(i+1)%nodes][1];


  28.              if(p1[1] > p2[1]) {


  29.                       p2[0] = polygon[i][0];   p2[1] = polygon[i][1];


  30.                       p1[0] = polygon[(i+1)%nodes][0];               p1[1] = polygon[(i+1)%nodes][1];


  31.              }


  32.              double m = (double)(p2[1]-p1[1])/(p2[0]-p1[0]);


  33.              double xd = p1[0] - 1/m;


  34.              for(int y=p1[1]; y<=p2[1]; ++y) {


  35.                      xd += 1/m;


  36.                      int x = ROUND(xd);


  37.                      if(array[y][0] > x)


  38.                                     array[y][0] = x;


  39.                      if(array[y][1] < x)


  40.                                     array[y][1] = x;


  41.              }


  42.      }


  43.    


  44.      for(int i=0; i<480; ++i)


  45.              if(array[i][0] < array[i][1])


  46.                             line(array[i][0]+1, i, array[i][1]-1, i);


  47. }





  48. void drawPolygon(Point *polygon, int nodes) {


  49.      setcolor(WHITE);


  50.      for(int i=0; i<nodes; ++i){


  51.              Point p1, p2;


  52.              p1[0] = polygon[i][0];   p1[1] = polygon[i][1];


  53.              p2[0] = polygon[(i+1)%nodes][0];               p2[1] = polygon[(i+1)%nodes][1];


  54.              line(p1[0], p1[1], p2[0], p2[1]);


  55.      }


  56. }








  57. int main(){


  58.     int gd = DETECT, gm;


  59.     initgraph(&gd, &gm, "C:\\");


  60.     Point polygon[20];


  61.     int size = 0;


  62.     while(true) {


  63.                 std::system("cls");


  64.                 std::cout << "Enter size of polygon : (-1 for exit) : ";


  65.                 std::cin >> size;


  66.                 if(size == -1)


  67.                         return 0;


  68.                 if(size > 20){


  69.                         std::cout << "Enter size less than 20" << std::endl;


  70.                         continue;


  71.                 }


  72.                 for(int i=0; i < size; ++i) {


  73.                         std::cout << "Enter vertex : (x y) : ";


  74.                         std::cin >> polygon[i][0] >> polygon[i][1];


  75.                 }


  76.                 drawPolygon(polygon, size);


  77.                 FILL:


  78.                 std::system("cls");


  79.                 std::cout << "Choose an algorithm to fill." << std::endl;


  80.                 std::cout << "\t1. seed fill" << std::endl;


  81.                 std::cout << "\t2. scan line fill" << std::endl;


  82.                 std::cout << "choice: ";


  83.                 int choice;


  84.                 std::cin >> choice;


  85.                 switch(choice) {


  86.                                case 1:


  87.                                     {


  88.                                         std::cout << "Enter a point inside polygon: (x y) : ";


  89.                                         Point p;


  90.                                         std::cin >> p[0] >> p[1];


  91.                                         seedFill(p[0], p[1],RED);


  92.                                         break;


  93.                                     }


  94.                                case 2:


  95.                                     scanlineFill(polygon, size, BLUE);


  96.                                     break;


  97.                                default:


  98.                                        std::cout << "I can't interpret your choice." << std::endl;


  99.                                        goto FILL;


  100.                                        break;


  101.                 }


  102.     }


  103. }




2 comments:

Dheeraj Suthar said...

Hi Rooparam!,
First of all let me congratulate you on maintaining such a elegant but fruitful blog.You have presented data structure, otherwise considered as very bore and complex subject, in quite interesting manner. But please do add some commentary or introduction to topic along with code.
I also share with you the joys of programming (albeit my inclination is more towards web development and fav language is python). Hope you will find my site interesting too (www.dheerajsuthar.com). Its more about open source and some projects I have furnished.
Hoping to see more great postings from you.

Dheeraj Suthar
MCA I Yr.
NIT Warangal.

rooparam said...

thanks dheeraj for ur encouragement. as u might have guessed, i m also an engineering student and just learned programming during college days, so i still dont remember to comment my code properly. But i will try to make my code more readable in future posts. thanks again and plz do visit my blog regularly. And the link u have provided for ur site is no longer exist. plz post new link if u changed your site's domain name.

Rooparam Choudhary
BTech from smvdu
MTech from iisc (joining from july 2010).