Flood fill algorithm without recursion?

[tyuo9980]

Tony @ Mon Jan 02, 2012 11:16 pm wrote:

right, but since you don't revisit checked areas, CArea could also effectively act as a border, as those points will not be crossed.

Well you still have to check if CArea is on the border or not. I might as well have another variable in place.

[Tony]

but your code is structured as

code:

if (!CArea [x] [y]) {    ...    if (!boundary) ...

that's an extra if-statement for every single point filled.

[tyuo9980]

i saw that early on as well, but for some reason it runs much faster with that there, even though its checking that point twice.

[Tony]

well that doesn't sound like a reasonable claim, so I wouldn't really trust such an assertion without seeing the testing code.

[tyuo9980]

here it is:

code:

public static void calcArea (int xx, int yy)     {         LinkedList listx = new LinkedList ();         LinkedList listy = new LinkedList ();         int x, y;         listx.addFirst (new Integer (xx));         listy.addFirst (new Integer (yy));         do         {             x = Integer.parseInt (listx.remove (0).toString ());             y = Integer.parseInt (listy.remove (0).toString ());             if (!CArea [x] [y])             {                 boundary = false;                 //if point is on wall                 for (int i = 1 ; i <= walls ; i++)                 {                     if (wallDir [i] == vertical)                     {                         if (x == wallx1 [i] && y >= wally1 [i] && y <= wally2 [i])                         {                             boundary = true;                             Boundary [x] [y] = true;                             break;                         }                     }                     else                     {                         if (y == wally1 [i] && x >= wallx1 [i] && x <= wallx2 [i])                         {                             boundary = true;                             Boundary [x] [y] = true;                             break;                         }                     }                 }                 if (!boundary)                                                  //if not at border                 {                     CArea [x] [y] = true;                     area++;                                         g.drawRect (x,y,0,0);                     c.ViewUpdate();                                         if (!CArea [x + 1] [y])                                     //checks right side                     {                         listx.addFirst (new Integer (x + 1));                         listy.addFirst (new Integer (y));                     }                     if (!CArea [x - 1] [y])                                     //left side                     {                         listx.addFirst (new Integer (x - 1));                         listy.addFirst (new Integer (y));                     }                     if (!CArea [x] [y + 1])                                     //below                     {                         listx.addFirst (new Integer (x));                         listy.addFirst (new Integer (y + 1));                     }                     if (!CArea [x] [y - 1])                                     //above                     {                         listx.addFirst (new Integer (x));                         listy.addFirst (new Integer (y - 1));                     }                 }             }         }         while (listx.size () != 0);     }

[Tony]

not sure what this is supposed to be, as it still uses boundary variable, still recalculates it inside the loop, and now also spends a bunch of time drawing things.

[tyuo9980]

o sry. i just wanted to see how it was filling

it is double checking but it is faster. around 10ms actually.

[tyuo9980]

http://www.mediafire.com/?ba2itzfrk54f0xx

if you want to take a look at the whole thing

[tyuo9980]

Heres the check for how long it takes to fill.

add this before the do while loop in the calcArea method:

long dly = System.currentTimeMillis ();

and this after the loop:

System.out.println (System.currentTimeMillis () - dly);

[Tony]

can you post the slower non-boundary code that this is benchmarked against?

[tyuo9980]

code:

public static void calcArea (int xx, int yy)     {         LinkedList listx = new LinkedList ();         LinkedList listy = new LinkedList ();         int x, y;         listx.addFirst (new Integer (xx));         listy.addFirst (new Integer (yy));         long awef = System.currentTimeMillis ();         do         {             x = Integer.parseInt (listx.remove (0).toString ());             y = Integer.parseInt (listy.remove (0).toString ());                 boundary = false;                 //if point is on wall                 for (int i = 1 ; i <= walls ; i++)                 {                     if (wallDir [i] == vertical)                     {                         if (x == wallx1 [i] && y >= wally1 [i] && y <= wally2 [i])                         {                             boundary = true;                             Boundary [x] [y] = true;                             break;                         }                     }                     else                     {                         if (y == wally1 [i] && x >= wallx1 [i] && x <= wallx2 [i])                         {                             boundary = true;                             Boundary [x] [y] = true;                             break;                         }                     }                 }                 if (!boundary)                                                  //if not at border                 {                     CArea [x] [y] = true;                     area++;                                         if (!CArea [x + 1] [y])                                     //checks right side                     {                         listx.addFirst (new Integer (x + 1));                         listy.addFirst (new Integer (y));                     }                     if (!CArea [x - 1] [y])                                     //left side                     {                         listx.addFirst (new Integer (x - 1));                         listy.addFirst (new Integer (y));                     }                     if (!CArea [x] [y + 1])                                     //below                     {                         listx.addFirst (new Integer (x));                         listy.addFirst (new Integer (y + 1));                     }                     if (!CArea [x] [y - 1])                                     //above                     {                         listx.addFirst (new Integer (x));                         listy.addFirst (new Integer (y - 1));                     }                 }             }         while (listx.size () != 0);         System.out.println (System.currentTimeMillis () - awef);     }

update:
this helps a bit too. eliminated an if statement.

code:

for (int i = 1 ; i <= walls ; i++)                 {                     if (x == wallx1 [i] && y >= wally1 [i] && y <= wally2 [i])  //vertical                     {                         boundary = true;                         Boundary [x] [y] = true;                         break;                     }                     else if (y == wally1 [i] && x >= wallx1 [i] && x <= wallx2 [i]) //horizontal                     {                         boundary = true;                         Boundary [x] [y] = true;                         break;                     }                 }

[tyuo9980]

x = listx.remove (0).hashCode ();
y = listy.remove (0).hashCode ();

returns an int value and i dont have to convert to int from string!

this cuts the calculation time in half!

[Tony]

well that's... a hack. Nice.

[mirhagk]

I don't get why you need that at all to be honest.

[Zren]

Suggestion:
Queue queue = new LinkedList();

We can define the variable as a Queue, which would force us to just use Queue-related functions. Now Queue is an interface, so we can't create an instance of it, so we have to create an instance of a class that implements it. In this case, a LinkedList.

The advantages of this? It will force yourself to only use the methods required for the Queue interface, thus your forced to learn how that data structure works instead of relying on methods from the List interface.

@Tony: Edit the next part if you feel like continuing to chuck hints at the man.

The properties of a List
A List can hold anything. You can store numbers (Integer, Double, Float, etc), Strings, and pretty much anything that inherits the class Object. Any time you insert a number, it's actually an instance of Integer (or Double depending on the case), not the primitive type (int, double, ...). So it's safe to say that List is a collection of Objects and it's children classes. So whenever we use list.get(id) or queue.poll(), we're actually returning an Object.

Read up about Generics: http://docs.oracle.com/javase/tutorial/extra/generics/intro.html