FloodFill in iPhone

Question

I'm very new to iPhone development. I want to create a application using FloodFill algorithm in iPhone. I'm have no idea about FloodFill. Please Explain me the purpose of FloodFill algorithm.If you give a sample application for FloodFill(iPhone)means I'm really, really happy..Because I'm exploring about FloodFill since morning but, nothing I'm found.

My task is, I want to fill the image with color as part by part. Which means, if I'm choosing one color and click on the particular area of the image means it gets colored with the selected color.

Please help me to do this.

Edit: I am not able to write a code for floodfill algorithm implementation for iPhone.

Answer 1

It's a recursive algorithm, meaning that it calls itself to accomplish smaller parts of the whole process.

Flood fill will start at one pixel. Then it will check the four adjacent pixels (up, down, left, right). For any of those four pixels that are the same colour as the one we started with, it will call another flood fill starting from that pixel.

Imagine a small picture where . is one colour, and X is another colour. The numbers are just there for reference, so 7,0 is the top right. (Ignore the red / black syntax hilighting!)

 01234567
0........
1.XXXX...
2.X..X...
3.X...X..
4.XXX..X.
5...X..X.
6...XXX..
7........

Now imagine you start a flood fill at 3,3. It will change 3,3 to the new colour. It will then check up,down,left,right. For up (3,2), the colour there is the same (a dot), so it will start another flood fill from there. For down (3,4), the colour is different, so this branch will stop. Left, (2,3), and right (4,3) are also the same (a dot), so more branches of flood fill start from there.

Let's say that new colour is O, so we now have this:

 01234567
0........
1.XXXX...
2.X.OX...
3.XOOOX..
4.XXX..X.
5...X..X.
6...XXX..
7........

The "up" branch started a new flood fill from (3,2). From here, up is X, so that stops. Right is X, so that stops, down is O, so that stops, but left (2,2) is the same (a dot), so it starts a new flood fill from there.

Similarly, the "right" branch from the original flood fill began from (4,3). The only branch it can use is down (4,4). Now we have this:

 01234567
0........
1.XXXX...
2.XOOX...
3.XOOOX..
4.XXXO.X.
5...X..X.
6...XXX..
7........

And so the flood fill continues from (4,4), by branching right and down. One of those two branches will then branch into (5,5). By that time, there will be no further possible branches.

And that is my lunchtime filled :)

Answer 2

This is a very curious question. Do you mean:

1. A "flood filled" polygon? Where polygon means anything from trivial polygons all the way up to a sophisticated Even / Odd rule arbitrary polygon filler (where polygon may be defined by Bézier curve paths)?

2. A "pick a point and flood fill" type algorithm? Sort of like the old "paint can" flood fill tool you see (well, at least you used to see, it's been a long time for me) in paint programs (I'm thinking MacPaint / Deluxe Paint era here). These algorithms range anywhere from the trivial 2D plane of pixels that "stop" when it hits an "edge" (usually a different "color" than the one where the flood fill started), all the way up to very sophisticated automagic edge detection algorithms you might see in high end paint / photo manipulation programs (i.e., PhotoShop).

I'm going to assume you're not looking for any of the trivial cases because... well, you've probably got some other nuts you need to crack before you try to crack this one.

So, in the case of #1, you should probably start by reading the documentation. Mac OS X / iOS has an extremely sophisticated 2D graphics API, largely based on the PDF / PostScript rendering model. CoreGraphics / Quartz will do "flood fill" for you automatically, and you can do it at the level of Bézier curves to boot.

In the case of #2, you should probably start by reading the exact same documentation. You're probably going to have to interact with it at this level anyways. However, OpenGL + programable shaders may be a better choice, depending on how sophisticated you want your "automagic" edge detection to be. But it's been my experience that people who are banging on the rendering pipe directly like this usually have a pretty good grasp of the fundamental algorithms used in manipulating pixel data, so I suspect this technique may not be appropriate for you.

Mixing CoreGraphics and OpenGL in the same context is a bit of an advanced technique, so you'll probably have to pick either CoreGraphics or OpenGL as your primary rendering API. However, CoreGraphics also has some pretty advanced and snazzy API's for doing the same type of stuff, but that gets way beyond your basic CoreGraphics API usage (but you'll find all the info by going through the various iOS graphics documentation, which is both extensive and very well documented).