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. }




Tuesday, December 1, 2009

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







  1. package eight_queen;



  2. import java.awt.AWTEvent;

  3. import java.awt.AlphaComposite;

  4. import java.awt.BorderLayout;

  5. import java.awt.Color;

  6. import java.awt.Composite;

  7. import java.awt.EventQueue;

  8. import java.awt.Frame;

  9. import java.awt.Graphics;

  10. import java.awt.Graphics2D;

  11. import java.awt.Image;

  12. import java.awt.Toolkit;

  13. import java.awt.event.ActionEvent;

  14. import java.awt.event.ActionListener;

  15. import java.awt.event.WindowEvent;

  16. import java.lang.reflect.InvocationTargetException;

  17. import java.util.Random;

  18. import java.util.Scanner;

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

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

  21. import java.util.logging.Level;

  22. import java.util.logging.Logger;

  23. import javax.swing.JButton;

  24. import javax.swing.JFrame;

  25. import javax.swing.JOptionPane;

  26. import javax.swing.JPanel;



  27. /**

  28.  *

  29.  * @author rooparam

  30.  */



  31. class Locations {

  32.     public Locations(int size ) {

  33.         at = new int[size];

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

  35.     }

  36.     public int top;

  37.     public int[] at;

  38. }





  39. class MyButton extends JButton {

  40.     MyButton( ) {

  41.         super("continue");

  42.     }

  43. }



  44. class Board extends JPanel {

  45.     Board ( Locations Q ) {

  46.         queens = Q;

  47.         //setSize(640, 480);

  48.         setBackground(Color.WHITE);

  49.     }



  50.     @Override

  51.     public void paint ( Graphics g ) {

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

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

  54.         drawBoard ( g );

  55.         drawQueens(g);

  56.         drawRemaining(g);

  57.         g.setColor(Color.RED);

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

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

  60.     }



  61.     private Locations queens;



  62.     private void drawRemaining(Graphics g2) {

  63.         Graphics2D g = (Graphics2D)g2;

  64.         int rule = AlphaComposite.SRC_OVER;

  65.         float alpha = 0.8f;

  66.         Composite oldC = g.getComposite( );

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

  68.         g.setPaint(Color.BLACK);

  69.        

  70.         int width = getBounds( ).width;

  71.         int height = getBounds( ).height;

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

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

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

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

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

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

  78.             }

  79.         }

  80.         g.setComposite(oldC);

  81.     }



  82.     private void drawQueens(Graphics g) {

  83.         int width = getBounds( ).width;

  84.         int height = getBounds( ).height;

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

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

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

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

  89.         }

  90.     }



  91.     private void drawBoard(Graphics g2) {

  92.         Graphics2D g = (Graphics2D)g2;

  93.         int rule = AlphaComposite.SRC_OVER;

  94.         float alpha = 0.9f;

  95.         Composite oldC = g.getComposite( );

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

  97.         g.setPaint(Color.WHITE);

  98.         int width = getBounds( ).width;

  99.         int height = getBounds( ).height;

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

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

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

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

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

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

  106.                 togglePen(g, Color.ORANGE );

  107.             }

  108.             togglePen(g, Color.ORANGE);

  109.         }

  110.         g.setComposite(oldC);

  111.     }



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

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

  114.             g.setColor(clr);

  115.         else

  116.             g.setColor(Color.WHITE);

  117.     }



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

  119.         Color oldPen = g.getColor( );

  120.         g.setColor(Color.BLUE);



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



  122.         int lines = 16;

  123.         double xi = x + width/8.0;

  124.         double yi = y + height/2.0;

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

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



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

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

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

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

  131.         }

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

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

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

  135.         }

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

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



  138.         g.setColor(oldPen);

  139.     }

  140. }

  141. public class Main extends JFrame {

  142.     Main( Locations Q ) {

  143.         enableEvents(AWTEvent.WINDOW_EVENT_MASK);

  144.         setLocation(100, 100);

  145.         setSize(640, 480);

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

  147.         Board canvas = new Board ( Q );

  148.         button = new MyButton( );

  149.         buttonclk = new ActionListener() {



  150.             public void actionPerformed(ActionEvent e) {

  151.                     Main.go(true);

  152.                 Main.window.repaint( );

  153.             }

  154.         };

  155.         button.addActionListener(buttonclk);

  156.         setLayout(new BorderLayout( ));

  157.         add(canvas, BorderLayout.CENTER);

  158.         add(button, BorderLayout.SOUTH);



  159.         setVisible(true);

  160.     }



  161.     @Override

  162.     public void processWindowEvent( WindowEvent event ) {

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

  164.             System.exit( 0 );

  165.     }



  166.     /**

  167.      * @param args the command line arguments

  168.      */

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

  170.         int size;

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

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

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

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

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

  176.         size = 8;

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

  178.         Main.solution = queens;

  179.         EventQueue.invokeLater(new Runnable() {



  180.             public void run() {

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

  182.             }

  183.         });

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

  185.         do {

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

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

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



  189.         EventQueue.invokeLater(new Runnable() {



  190.             public void run() {

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

  192.                 Main.button.removeActionListener(buttonclk);

  193.                 buttonclk = new ActionListener() {



  194.                     public void actionPerformed(ActionEvent e) {

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

  196.                     }

  197.                 };

  198.                 Main.button.addActionListener(buttonclk);

  199.             }

  200.         });



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

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

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

  204.         }

  205.         System.out.println( );

  206.     }



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

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

  209.             return true;

  210.        

  211.         Main.go(false);

  212.         while (!proceed) {

  213.             try {

  214.                 Thread.sleep(100);

  215.             } catch (InterruptedException ex) {

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

  217.             }

  218.         }

  219.         try {

  220.             EventQueue.invokeAndWait(new Runnable() {



  221.                 public void run() {

  222.                     Main.window.repaint();

  223.                 }

  224.             });

  225.         } catch (InterruptedException ex) {

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

  227.         } catch (InvocationTargetException ex) {

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

  229.         }



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

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

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

  233.                 if( solve ( queens, window) )

  234.                     return true;

  235.             }

  236.         }

  237.         queens.top--;

  238.         return false;

  239.     }



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

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

  242.             int col_i = i;

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

  244.             int col_test = col;

  245.             int row_test = check;

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

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

  248.                 return false;

  249.             // digonal check

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

  251.                 return false;

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

  253.                 return false;

  254.         }

  255.         return true;

  256.     }



  257.     static boolean proceed = false;

  258.     static Frame window = null;

  259.     static Locations solution = null;



  260.     public static void go(boolean  b){

  261.         myLock.lock( );

  262.         try {

  263.             proceed = b;

  264.         } finally

  265.         {

  266.             myLock.unlock( );

  267.         }

  268.     }



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

  270.     static MyButton button;

  271.     static ActionListener buttonclk;

  272. }