Strict Standards: Non-static method utf_normalizer::nfc() should not be called statically in /www/htdocs/w006661d/anddev/includes/utf/utf_tools.php on line 1781
[phpBB Debug] PHP Notice: in file /includes/session.php on line 1007: Cannot modify header information - headers already sent by (output started at /includes/utf/utf_tools.php:1781)
[phpBB Debug] PHP Notice: in file /includes/session.php on line 1007: Cannot modify header information - headers already sent by (output started at /includes/utf/utf_tools.php:1781)
[phpBB Debug] PHP Notice: in file /includes/session.php on line 1007: Cannot modify header information - headers already sent by (output started at /includes/utf/utf_tools.php:1781)

Strict Standards: Non-static method utf_normalizer::nfc() should not be called statically in /www/htdocs/w006661d/anddev/includes/utf/utf_tools.php on line 1781

Strict Standards: Non-static method utf_normalizer::nfc() should not be called statically in /www/htdocs/w006661d/anddev/includes/utf/utf_tools.php on line 1781
[phpBB Debug] PHP Notice: in file /includes/functions.php on line 4362: Cannot modify header information - headers already sent by (output started at /includes/utf/utf_tools.php:1781)
[phpBB Debug] PHP Notice: in file /includes/functions.php on line 4364: Cannot modify header information - headers already sent by (output started at /includes/utf/utf_tools.php:1781)
[phpBB Debug] PHP Notice: in file /includes/functions.php on line 4365: Cannot modify header information - headers already sent by (output started at /includes/utf/utf_tools.php:1781)
[phpBB Debug] PHP Notice: in file /includes/functions.php on line 4366: Cannot modify header information - headers already sent by (output started at /includes/utf/utf_tools.php:1781)
anddev.org • View topic - Flood Fill Algorithm

Flood Fill Algorithm

Put your problem here if it does not fit any of the other categories.

Flood Fill Algorithm

Postby nicholas.hauschild » Sun Dec 13, 2009 3:31 am

Has anyone successfully implemented a Flood Fill algorithm that could fill the entire screen pixel by pixel. Every attempt I have made is way too slow (more than a few minutes).

NOTE: I am not trying to fill the screen, I understand how to do that, I am asking because I want my Flood Fill algorithm to be performant under the worse case scenario.

Thanks!
-Nick
nicholas.hauschild
Master Developer
Master Developer
 
Posts: 310
Joined: Fri Dec 04, 2009 4:50 am

Top

Postby nicholas.hauschild » Sun Dec 13, 2009 6:18 am

Well, I got something working, but my current implementation is taking about 6 seconds to do a fill for the whole screen (480x854 on a Moto Droid currently)

I have some ideas about how to speed it up a bit. If anyone is interested about this or my implementation, ask away or PM me.

Here is the pseudo code I used to make my implementation, taken from Flood Fill:

Flood-fill (node, target-color, replacement-color):
1. Set Q to the empty queue.
2. If the color of node is not equal to target-color, return.
3. Add node to Q.
4. For each element n of Q:
5. If the color of n is equal to target-color:
6. Set w and e equal to n.
7. Move w to the west until the color of the node to the west of w no longer matches target-color.
8. Move e to the east until the color of the node to the east of e no longer matches target-color.
9. Set the color of nodes between w and e to replacement-color.
10. For each node n between w and e:
11. If the color of the node to the north of n is target-color, add that node to Q.
If the color of the node to the south of n is target-color, add that node to Q.
12. Continue looping until Q is exhausted.
13. Return.
nicholas.hauschild
Master Developer
Master Developer
 
Posts: 310
Joined: Fri Dec 04, 2009 4:50 am

Top

Return to Other Coding-Problems

Who is online

Users browsing this forum: Google [Bot] and 9 guests