Flood fill algorithm without recursion?

[tyuo9980]

i implemented a queue and it eliminated the overflow error, but its SUPER DUPER WHOPPERINGLY slow.

code:

public static void calcArea (int xx, int yy)     {         LinkedList listx = new LinkedList ();         LinkedList listy = new LinkedList ();         int listLength = 1;         int x, y;         listx.add (new Integer (xx));         listy.add (new Integer (yy));         for (int l = 0 ; l < listLength ; l++)         {             x = Integer.parseInt (listx.get (l).toString ());             y = Integer.parseInt (listy.get (l).toString ());             if (!CArea [x] [y])             {                 boundary = false;                 for (int i = 1 ; i <= walls ; i++)                 {                     if (x == wallx1 [i] && x == wallx2 [i] && y >= wally1 [i] && y <= wally2 [i]) //vertical                     {                         boundary = true;                         Boundary [x] [y] = true;                     }                     else if (y == wally1 [i] && y == wally2 [i] && x >= wallx1 [i] && x <= wallx2 [i]) //horizontal                     {                         boundary = true;                         Boundary [x] [y] = true;                     }                 }                 if (!boundary)                 {                     CArea [x] [y] = true;                     area++;                     if (!CArea [x + 1] [y])                     {                         listx.add (new Integer (x + 1));                         listy.add (new Integer (y));                         listLength++;                     }                     if (!CArea [x - 1] [y])                     {                         listx.add (new Integer (x - 1));                         listy.add (new Integer (y));                         listLength++;                     }                     if (!CArea [x] [y + 1])                     {                         listx.add (new Integer (x));                         listy.add (new Integer (y + 1));                         listLength++;                     }                     if (!CArea [x] [y - 1])                     {                         listx.add (new Integer (x));                         listy.add (new Integer (y - 1));                         listLength++;                     }                 }             }         }     }

[mirhagk]

Why do you need to parse the integers?

[Tony]

I would guess that parsing is a workaround for the list being of a generic "Object" type, but that's not really the problem in comparison to:

get(int index) is an O(n) operation

which is bad bad news, considering that nothing is ever removed from the queue.

[tyuo9980]

On opertation? I dont quite get you there.

How would removing items from the queue be beneficial? i dont think that i need to remove anything from the queue since it just goes through the list until it ends.

[mirhagk]

Well tony, recurisively is potentially O(n) as well,

basically what it means is that the time and memory grows linearly with the number of pixels inside the area.

[tyuo9980]

ahh i see. so if i remove items from the queue it would take less time to grab the values.

[mirhagk]

No it won't take less time, just less memory

[tyuo9980]

memory isnt an issue. how would i make it faster?

[Tony]

The way a linked list works is that to get 3rd element, you start at element 1 to find out where element 2 is, then follow that to 3rd. This continues linearly, so to get(n) you need to perform ~n operations -- thus it's of the order O(n) -- http://en.wikipedia.org/wiki/Big_O_notation

It's a good idea to remove elements, so that you only ever grab stuff from the front, as get(1) is about 1000 times faster than get(1000)

[tyuo9980]

thanks. this helps out a lot. i'll get that done in a few minutes and see how it results.

[tyuo9980]

its MUCH MUCH faster now. however its still not fast enough. i need something that's almost instant on my computer as the ones at school are pretty slow.

The whole area takes around 285ms to calculate. Are there any other improvements that I can make?

code:

public static void calcArea (int xx, int yy)     {         LinkedList listx = new LinkedList ();         LinkedList listy = new LinkedList ();         int x, y;         listx.add (new Integer (xx));         listy.add (new Integer (yy));         do         {             x = Integer.parseInt (listx.get (0).toString ());             y = Integer.parseInt (listy.get (0).toString ());             listx.remove (0);             listy.remove (0);                         if (!CArea [x] [y])             {                 boundary = false;                 for (int i = 1 ; i <= walls ; i++)                 {                     if (x == wallx1 [i] && x == wallx2 [i] && y >= wally1 [i] && y <= wally2 [i]) //vertical                     {                         boundary = true;                         Boundary [x] [y] = true;                     }                     else if (y == wally1 [i] && y == wally2 [i] && x >= wallx1 [i] && x <= wallx2 [i]) //horizontal                     {                         boundary = true;                         Boundary [x] [y] = true;                     }                 }                 if (!boundary)                 {                     CArea [x] [y] = true;                     area++;                     if (!CArea [x + 1] [y])                     {                         listx.add (new Integer (x + 1));                         listy.add (new Integer (y));                     }                     if (!CArea [x - 1] [y])                     {                         listx.add (new Integer (x - 1));                         listy.add (new Integer (y));                     }                     if (!CArea [x] [y + 1])                     {                         listx.add (new Integer (x));                         listy.add (new Integer (y + 1));                     }                     if (!CArea [x] [y - 1])                     {                         listx.add (new Integer (x));                         listy.add (new Integer (y - 1));                     }                 }             }         }         while (listx.size() != 0);     }

[Tony]

You probably dont need that boundary-finding loop to be inside the main loop. Just calculate all the boundary points once, instead of checking again and again for every point.

If you mark boundary points as CArea, then you wouldn't even need a separate boundary check.

Also, you might want to use addFirst instead of add, to stick stuff into the front. This makes your LinkedList behave as a Stack instead of a Queue, but should be faster for the same reasons as described before (it's slow to get to the end... unless the internal implementation keeps a tail pointer; I don't know if that is the case or not).

Some other points:
- remove(index) also returns the element at that index, so you can do

code:

x = Integer.parseInt (listx.remove (0).toString ());

- would casting be faster than parsing?

code:

x = (Integer)listx.remove(0);

- since x is already an Integer, we could just do

code:

listx.add (x);

which skips half of Integer constructor calls

[tyuo9980]

Tony @ Mon Jan 02, 2012 10:15 pm wrote:

You probably dont need that boundary-finding loop to be inside the main loop. Just calculate all the boundary points once, instead of checking again and again for every point.

If you mark boundary points as CArea, then you wouldn't even need a separate boundary check.

Also, you might want to use addFirst instead of add, to stick stuff into the front. This makes your LinkedList behave as a Stack instead of a Queue, but should be faster for the same reasons as described before (it's slow to get to the end... unless the internal implementation keeps a tail pointer; I don't know if that is the case or not).

^^I'll be looking into that later. thanks


thanks for that. shaved off 10ms.

- remove(index) also returns the element at that index, so you can do

code:

x = Integer.parseInt (listx.remove (0).toString ());

I'm unable to cast in ready to program IDE. it works in eclipse but it wont be an option at school.

- would casting be faster than parsing?

code:

x = (Integer)listx.remove(0);

I get the no overload for the method was found in LinkedList error.

- since x is already an Integer, we could just do

code:

listx.add (x);

which skips half of Integer constructor calls

[tyuo9980]

CArea is the checkedArea. if it has been checked, then it becomes true.

Boundary is the check to see which parts of the field is the border (the outline of the filled polygon) and I use that for boundary collision.
If I had another way to check where the border is, it would massively speed up the flood fill.

Eclipse is also 4 times faster than Ready and there would still be a huge delay even if java didnt have a stack limit.

Comparing queuing and recursion on eclipse, it seems that queuing is 2 times slower.

[Tony]

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