java - Choose direction to start flood fill algorithm for loop detection -
i've implemented flood fill algorithm matrices in program, , i'd choose in direction starts. want detect loops created elements on grid: when there element @ given place on grid, 1 displayed in matrix. when there isn't anything, it's 0. , when elements won't moved, it's 2. flood fill algorithm starts on 1 , turns every 1 encounters 2.
example:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 1 1 1 0 0 0 0 0 2 0 0 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 would become:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 2 0 0 0 0 0 2 0 0 0 2 0 0 0 0 0 2 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 here code:
import tuio.*; import java.util.arrays; import java.util.scanner; tuioprocessing tuioclient; // create matrix static int[][] matrix = new int[10][10]; // these helper variables used // create scalable graphical feedback int k, l, id, x,y; string mytype; void setup() { size(1000, 600); nocursor(); nostroke(); fill(0); } void draw() { matrix [1][5]= 2; matrix [1][6]= 2; matrix [2][5]= 2; matrix [2][6]= 2; matrix [3][5]=1; arraylist<tuioobject> tuioobjectlist = tuioclient.gettuioobjectlist(); (int i=0; i<tuioobjectlist.size (); i++) { tuioobject tobj= tuioobjectlist.get(i); stroke(0); fill(0, 0, 0); pushmatrix(); translate(tobj.getscreenx(width), tobj.getscreeny(height)); rotate(tobj.getangle()); rect(-80, -40, 80, 40); popmatrix(); fill(255); x = round(10*tobj.getx ()); y = round(10*tobj.gety ()); id = tobj.getsymbolid(); int taille = fiducialslist.length; (int o = 0; o<taille; o++) { if (id == o) { mytype = fiducialslist [o]; } } activlist.add(new fiducial (x, y, id, mytype)); fiducialcoordinates (); matrix [x][y] = 1 ; circuitstate (); (int p = 0; p < 10; p++) { (int r = 0; r < 10; r++) { system.out.print(matrix[p][r] + " "); } system.out.print("\n"); } system.out.print("\n"); // activlist.removeall(activlist); } (int[] row : matrix) arrays.fill(row, 0); } public static class floodfill { public static void resolution(string[] args) { solve(matrix, 2, 5, 3); //result system.out.println("-------------------"); (int i=0; i<matrix.length; i++) { (int j=0; j<matrix[i].length; j++) { system.out.print(matrix[i][j] + " "); } system.out.print("\n"); } system.out.print("\n"); } public static void solve(int[][] matrix, int x, int y, int fillvalue) { if (x>=matrix.length) return; if (y>=matrix[x].length) return; int originvalue=matrix[x][y]; matrix[x][y]=fillvalue; // if (x-1>=0 && originvalue==matrix[x-1][y]) solve(matrix, x-1, y, fillvalue); // right if (y+1<matrix[x].length && originvalue==matrix[x][y+1]) solve(matrix, x, y+1, fillvalue); //south-east // down if (x+1<matrix.length && originvalue==matrix[x+1][y]) solve(matrix, x+1, y, fillvalue); //south-west // left if (y-1>=0 && originvalue==matrix[x][y-1]) solve(matrix, x, y-1, fillvalue); } } the algorithm created in floodfill class.the real cases lot more complex here problem: when starting point given, how can prevent in 1 direction (say on left)? there way this? don't want algorithm "look" @ position on left of starting point.
it java used in processing.
through comments, you've asked algorithm allows check loops. solution below using modified flood fill.
private static enum direction{ up, right, down, left, none; } public static boolean checkifpositionisinloop(int[][] matrix, int x, int y, int fillvalue){ int targetx = x; int targety = y; return fillreachestargetposition(matrix, x, y, targetx, targety, fillvalue, direction.left /*don't allow start filling left*/); } private static boolean fillreachestargetposition(int[][] matrix, int x, int y, int targetx, int targety, int fillvalue, direction forbiddendirection) { if (x>=matrix.length) return false; if (y>=matrix[x].length) return false; int originvalue=matrix[x][y]; matrix[x][y]=fillvalue; int xtofillnext; int ytofillnext; boolean fillingreachedtargetposition = false; // xtofillnext = x-1; ytofillnext = y; if(xtofillnext==targetx && ytofillnext==targety && !forbiddendirection.equals(direction.up)){ return true; } else if (xtofillnext>=0 && originvalue==matrix[xtofillnext][ytofillnext] && !forbiddendirection.equals(direction.up)){ fillingreachedtargetposition = fillreachestargetposition(matrix, xtofillnext, ytofillnext, targetx, targety, fillvalue,direction.down /*just came up- don't allow try filling here again*/); if(fillingreachedtargetposition){ return true; } } // right xtofillnext = x; ytofillnext = y+1; if(xtofillnext==targetx && ytofillnext==targety && !forbiddendirection.equals(direction.right)){ return true; } else if (ytofillnext<matrix[xtofillnext].length && originvalue==matrix[xtofillnext][ytofillnext] && !forbiddendirection.equals(direction.right)) { fillingreachedtargetposition = fillreachestargetposition(matrix, xtofillnext, ytofillnext,targetx, targety, fillvalue,direction.left /*just came right- don't allow try filling here again*/); if(fillingreachedtargetposition){ return true; } } // down xtofillnext = x+1; ytofillnext = y; if(xtofillnext==targetx && ytofillnext==targety && !forbiddendirection.equals(direction.down)){ return true; } else if (xtofillnext<matrix.length && originvalue==matrix[xtofillnext][ytofillnext] && !forbiddendirection.equals(direction.down)){ fillingreachedtargetposition = fillreachestargetposition(matrix, xtofillnext, ytofillnext, targetx, targety, fillvalue,direction.up /*just came up- don't allow try filling here again*/); if(fillingreachedtargetposition){ return true; } } // left xtofillnext = x; ytofillnext = y-1; if(xtofillnext==targetx && ytofillnext==targety && forbiddendirection.equals(direction.right)){ return true; } else if (ytofillnext>=0 && originvalue==matrix[xtofillnext][ytofillnext] && !forbiddendirection.equals(direction.left)){ fillingreachedtargetposition = fillreachestargetposition(matrix, xtofillnext, ytofillnext, targetx, targety, fillvalue,direction.right /*just came left- don't allow try filling here again*/); if(fillingreachedtargetposition){ return true; } } return false; } here's driver show in action:
public static void main(string[] arg){ system.out.println("show matrix loop, before fill"); int[][] matrix = getmatrixwithwideloop(); printmatrix(matrix); system.out.println("found loop: "+checkifpositionisinloop(matrix, 0, 2, 2 /*fill 2s*/)); system.out.println("-----------------------------------------"); system.out.println("show matrix without loop, before fill"); matrix = getmatrixwithoutloop(); printmatrix(matrix); system.out.println("found loop: "+checkifpositionisinloop(matrix, 0, 2, 2 /*fill 2s*/)); system.out.println("-----------------------------------------"); system.out.println("show matrix small loop, before fill"); matrix = getmatrixwithsmallloop(); printmatrix(matrix); system.out.println("found loop: "+checkifpositionisinloop(matrix, 0, 2, 2 /*fill 2s*/)); system.out.println("-----------------------------------------"); system.out.println("show matrix without loop, before fill"); matrix = getmatrixwithoutloop(); printmatrix(matrix); system.out.println("found loop: "+checkifpositionisinloop(matrix, 0, 1, 2 /*fill 2s*/)); } and output:
show matrix loop, before fill 01110 01010 01110 found loop: true ----------------------------------------- show matrix without loop, before fill 01110 00010 01110 found loop: false ----------------------------------------- show matrix small loop, before fill 01100 01100 00000 found loop: true ----------------------------------------- show matrix without loop, before fill 01110 00010 01110 found loop: false
Comments
Post a Comment