Friday, December 11, 2009

Area Filling Algorithms (seed filling, ScanLine conversion)



  1. #include <graphics.h>


  2. #include <iostream>





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





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





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


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


  10.           return;


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


  12.                        putpixel(x, y, color);


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


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


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


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


  17.      }


  18. }





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


  21.      setcolor(color);


  22.      Point array[480];


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


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


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


  26.      }


  27.    


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


  29.              Point p1, p2;


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


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


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


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


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


  35.              }


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


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


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


  39.                      xd += 1/m;


  40.                      int x = ROUND(xd);


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


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


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


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


  45.              }


  46.      }


  47.    


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


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


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


  51. }





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


  54.      setcolor(WHITE);


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


  56.              Point p1, p2;


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


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


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


  60.      }


  61. }








  64. int main(){


  65.     int gd = DETECT, gm;


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


  67.     Point polygon[20];


  68.     int size = 0;


  69.     while(true) {


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


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


  72.                 std::cin >> size;


  73.                 if(size == -1)


  74.                         return 0;


  75.                 if(size > 20){


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


  77.                         continue;


  78.                 }


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


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


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


  82.                 }


  83.                 drawPolygon(polygon, size);


  84.                 FILL:


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


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


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


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


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


  90.                 int choice;


  91.                 std::cin >> choice;


  92.                 switch(choice) {


  93.                                case 1:


  94.                                     {


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


  96.                                         Point p;


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


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


  99.                                         break;


  100.                                     }


  101.                                case 2:


  102.                                     scanlineFill(polygon, size, BLUE);


  103.                                     break;


  104.                                default:


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


  106.                                        goto FILL;


  107.                                        break;


  108.                 }


  109.     }


  110. }




Labels: , , , ,
Posted by rooparam at 9:48 AM 2 comments

Tuesday, December 1, 2009

Eight Queens Solution with DFS using Backtracking (Step-by-step simulation)







  1. package eight_queen;



  3. import java.awt.AWTEvent;

  4. import java.awt.AlphaComposite;

  5. import java.awt.BorderLayout;

  6. import java.awt.Color;

  7. import java.awt.Composite;

  8. import java.awt.EventQueue;

  9. import java.awt.Frame;

  10. import java.awt.Graphics;

  11. import java.awt.Graphics2D;

  12. import java.awt.Image;

  13. import java.awt.Toolkit;

  14. import java.awt.event.ActionEvent;

  15. import java.awt.event.ActionListener;

  16. import java.awt.event.WindowEvent;

  17. import java.lang.reflect.InvocationTargetException;

  18. import java.util.Random;

  19. import java.util.Scanner;

  20. import java.util.concurrent.locks.Lock;

  21. import java.util.concurrent.locks.ReentrantLock;

  22. import java.util.logging.Level;

  23. import java.util.logging.Logger;

  24. import javax.swing.JButton;

  25. import javax.swing.JFrame;

  26. import javax.swing.JOptionPane;

  27. import javax.swing.JPanel;



  29. /**

  30.  *

  31.  * @author rooparam

  32.  */



  34. class Locations {

  35.     public Locations(int size ) {

  36.         at = new int[size];

  37.         top = 0;    // next coloumn of a queen

  38.     }

  39.     public int top;

  40.     public int[] at;

  41. }





  44. class MyButton extends JButton {

  45.     MyButton( ) {

  46.         super("continue");

  47.     }

  48. }



  50. class Board extends JPanel {

  51.     Board ( Locations Q ) {

  52.         queens = Q;

  53.         //setSize(640, 480);

  54.         setBackground(Color.WHITE);

  55.     }



  57.     @Override

  58.     public void paint ( Graphics g ) {

  59.         Image image = Toolkit.getDefaultToolkit().getImage("eight_queen/smvdu_logo_1.gif");

  60.         g.drawImage(image, 0, 0, getBounds().width, getBounds().height, this);

  61.         drawBoard ( g );

  62.         drawQueens(g);

  63.         drawRemaining(g);

  64.         g.setColor(Color.RED);

  65.         String str = "Coder : Rooparam Chaudhary";

  66.         g.drawString(str, getBounds().width - 180, getBounds().height - 10);

  67.     }



  69.     private Locations queens;



  71.     private void drawRemaining(Graphics g2) {

  72.         Graphics2D g = (Graphics2D)g2;

  73.         int rule = AlphaComposite.SRC_OVER;

  74.         float alpha = 0.8f;

  75.         Composite oldC = g.getComposite( );

  76.         g.setComposite(AlphaComposite.getInstance(rule, alpha));

  77.         g.setPaint(Color.BLACK);

  78.        

  79.         int width = getBounds( ).width;

  80.         int height = getBounds( ).height;

  81.         int w_Q = width / queens.at.length;

  82.         int h_Q = height / queens.at.length;

  83.         for(int col = queens.top; col < queens.at.length; ++col) {

  84.             for(int row = 0; row < queens.at.length; ++row) {

  85.                 if( !Main.isSafe(queens, row, col) )

  86.                     g.fill3DRect(col*w_Q, row*h_Q, w_Q, h_Q, true);

  87.             }

  88.         }

  89.         g.setComposite(oldC);

  90.     }



  92.     private void drawQueens(Graphics g) {

  93.         int width = getBounds( ).width;

  94.         int height = getBounds( ).height;

  95.         int w_Q = width / queens.at.length;

  96.         int h_Q = height / queens.at.length;

  97.         for(int col = 0; col < queens.top; ++col) {

  98.             drawQueen(g, col*w_Q, queens.at[col]*h_Q, w_Q, h_Q);

  99.         }

  100.     }



  102.     private void drawBoard(Graphics g2) {

  103.         Graphics2D g = (Graphics2D)g2;

  104.         int rule = AlphaComposite.SRC_OVER;

  105.         float alpha = 0.9f;

  106.         Composite oldC = g.getComposite( );

  107.         g.setComposite(AlphaComposite.getInstance(rule, alpha));

  108.         g.setPaint(Color.WHITE);

  109.         int width = getBounds( ).width;

  110.         int height = getBounds( ).height;

  111.         int w_Q = width / queens.at.length;

  112.         int h_Q = height / queens.at.length;

  113.         for(int col = 0; col < queens.at.length; ++col) {

  114.             for(int row = 0; row < queens.at.length; ++row) {

  115.                 //g.fillRect(col*w_Q, row*h_Q, w_Q, h_Q);

  116.                 g.fill3DRect(col*w_Q, row*h_Q, w_Q, h_Q, true);

  117.                 togglePen(g, Color.ORANGE );

  118.             }

  119.             togglePen(g, Color.ORANGE);

  120.         }

  121.         g.setComposite(oldC);

  122.     }



  124.     private void togglePen(Graphics g, Color clr) {

  125.         if( g.getColor( ) == Color.WHITE )

  126.             g.setColor(clr);

  127.         else

  128.             g.setColor(Color.WHITE);

  129.     }



  131.     private void drawQueen(Graphics g, int x, int y, int width, int height) {

  132.         Color oldPen = g.getColor( );

  133.         g.setColor(Color.BLUE);



  135.         g.fillArc ( x + width/8, y + 7*height/8, 3*width/4, height/4, 0, 180);



  137.         int lines = 16;

  138.         double xi = x + width/8.0;

  139.         double yi = y + height/2.0;

  140.         double step_x = 3.0*width/(4*lines);

  141.         double step_y = height/(2.0*lines);



  143.         g.drawLine((int)xi, (int)yi, (int)(xi+step_x), (int)( y+height-2) );

  144.         for(int i=0; i < lines/2; ++i) {

  145.             xi += step_x;   yi -= step_y;

  146.             g.drawLine((int)xi, (int)yi, (int)xi, (int)(y+height-2.0));

  147.         }

  148.         for(int i=1; i < lines/2; ++i) {

  149.             xi += step_x;   yi += step_y;

  150.             g.drawLine((int)xi, (int)yi, (int)xi, (int)(y+height-2.0));

  151.         }

  152.         xi += step_x;   yi += step_y;

  153.         g.drawLine((int)xi, (int)yi, (int)(xi-step_x), (int)(y+height-2.0));



  155.         g.setColor(oldPen);

  156.     }

  157. }

  158. public class Main extends JFrame {

  159.     Main( Locations Q ) {

  160.         enableEvents(AWTEvent.WINDOW_EVENT_MASK);

  161.         setLocation(100, 100);

  162.         setSize(640, 480);

  163.         setTitle("Eight Queens Problem (DFS using Backtracing)");

  164.         Board canvas = new Board ( Q );

  165.         button = new MyButton( );

  166.         buttonclk = new ActionListener() {



  168.             public void actionPerformed(ActionEvent e) {

  169.                     Main.go(true);

  170.                 Main.window.repaint( );

  171.             }

  172.         };

  173.         button.addActionListener(buttonclk);

  174.         setLayout(new BorderLayout( ));

  175.         add(canvas, BorderLayout.CENTER);

  176.         add(button, BorderLayout.SOUTH);



  178.         setVisible(true);

  179.     }



  181.     @Override

  182.     public void processWindowEvent( WindowEvent event ) {

  183.         if ( event.getID( ) == WindowEvent.WINDOW_CLOSING )

  184.             System.exit( 0 );

  185.     }



  187.     /**

  188.      * @param args the command line arguments

  189.      */

  190.     public static void main(String[] args) {

  191.         int size;

  192.         Scanner in = new Scanner(System.in);

  193.         System.out.println("Eight Queen Problem (DFS using Backtracing)");

  194.         //System.out.print("N : ");

  195.         //size = in.nextInt( );

  196.         //System.out.println("Wait .... ");

  197.         size = 8;

  198.         Locations queens = new Locations(size);             // stores row of queens

  199.         Main.solution = queens;

  200.         EventQueue.invokeLater(new Runnable() {



  202.             public void run() {

  203.                 Main.window = new Main(Main.solution);

  204.             }

  205.         });

  206.         Random dice = new Random(System.currentTimeMillis());

  207.         do {

  208.             int initial = dice.nextInt(size);

  209.             queens.at[(queens.top)++] = initial;

  210.         } while ( solve (queens, window) == false );



  212.         EventQueue.invokeLater(new Runnable() {



  214.             public void run() {

  215.                 Main.button.setText("D O N E");

  216.                 Main.button.removeActionListener(buttonclk);

  217.                 buttonclk = new ActionListener() {



  219.                     public void actionPerformed(ActionEvent e) {

  220.                         JOptionPane.showMessageDialog(null, "THANK YOU. source code at http://rooparam.blogspot.com",  "rooparam", JOptionPane.INFORMATION_MESSAGE);

  221.                     }

  222.                 };

  223.                 Main.button.addActionListener(buttonclk);

  224.             }

  225.         });



  227.         System.out.println("Positions of queens in Rows from left to right");

  228.         for ( int i=0; i< queens.at.length; ++i ) {

  229.             System.out.printf("%d  ", queens.at[i]);

  230.         }

  231.         System.out.println( );

  232.     }



  234.     private static boolean solve(Locations queens, Frame window) {

  235.         if(queens.top >= queens.at.length)

  236.             return true;

  237.        

  238.         Main.go(false);

  239.         while (!proceed) {

  240.             try {

  241.                 Thread.sleep(100);

  242.             } catch (InterruptedException ex) {

  243.                 Logger.getLogger(Main.class.getName()).log(Level.SEVERE, null, ex);

  244.             }

  245.         }

  246.         try {

  247.             EventQueue.invokeAndWait(new Runnable() {



  249.                 public void run() {

  250.                     Main.window.repaint();

  251.                 }

  252.             });

  253.         } catch (InterruptedException ex) {

  254.             Logger.getLogger(Main.class.getName()).log(Level.SEVERE, null, ex);

  255.         } catch (InvocationTargetException ex) {

  256.             Logger.getLogger(Main.class.getName()).log(Level.SEVERE, null, ex);

  257.         }



  259.         for(int i=0; i < queens.at.length; ++i) {

  260.             if ( isSafe ( queens, i, queens.top ) ) {

  261.                 queens.at[queens.top++] = i;

  262.                 if( solve ( queens, window) )

  263.                     return true;

  264.             }

  265.         }

  266.         queens.top--;

  267.         return false;

  268.     }



  270.     static boolean isSafe(Locations queens, int check, int col) {

  271.         for( int i=0; i < queens.top; ++i ) {

  272.             int col_i = i;

  273.             int row_i = queens.at[i];

  274.             int col_test = col;

  275.             int row_test = check;

  276.             // checking whether in same coloumn of in same row

  277.             if ( col_i == col_test || row_i == row_test )

  278.                 return false;

  279.             // digonal check

  280.             if ( ( col_i + row_i ) == ( col_test + row_test ) )

  281.                 return false;

  282.             if ( ( col_i - row_i ) == ( col_test - row_test ) )

  283.                 return false;

  284.         }

  285.         return true;

  286.     }



  288.     static boolean proceed = false;

  289.     static Frame window = null;

  290.     static Locations solution = null;



  292.     public static void go(boolean  b){

  293.         myLock.lock( );

  294.         try {

  295.             proceed = b;

  296.         } finally

  297.         {

  298.             myLock.unlock( );

  299.         }

  300.     }



  302.     public static final Lock myLock = new ReentrantLock( );

  303.     static MyButton button;

  304.     static ActionListener buttonclk;

  305. }



Labels: , , , , ,
Posted by rooparam at 3:55 PM 1 comments
Subscribe to: Comments (Atom)