Flood-fill, only half-working in Swift

Question

I am having trouble with the following function in swift. It is meant to flood-fill an arbitrary area. The filling color is stored in a variable called floodTargetPixel and the original in floodSourcePixel.

The four convenience methods: red(), green(), blue(), alpha(), rgba() are the same as here: Change color of certain pixels in a UIImage

(Problem:)Only part of the area is filled (the part above the starting point) and not the rest, what am I missing? The calling code is after the function itself.

    func floodFill(point:CGPoint)
    {
        let pixel = floodPixel.memory

        if (red(pixel) == floodTargetPixel[0] && green(pixel) == floodTargetPixel[1] &&
            blue(pixel) == floodTargetPixel[2] && alpha(pixel) == floodTargetPixel[3]) {
                return
        }

        if (red(pixel) != floodSourcePixel[0] || green(pixel) != floodSourcePixel[1] ||
            blue(pixel) != floodSourcePixel[2] || alpha(pixel) != floodSourcePixel[3]) {
                return
        }

        floodPixel.memory = rgba(red: floodTargetPixel[0], green: floodTargetPixel[1],
            blue: floodTargetPixel[2], alpha: floodTargetPixel[3])

        if (point.y >= 1.0) {
            floodPixel -= imageWidth
            self.floodFill(CGPointMake(point.x,point.y-1.0))
//            floodPixel += imageWidth
        }
        if (point.y <= CGFloat(imageHeight)-2.0) {
            floodPixel += imageWidth
            self.floodFill(CGPointMake(point.x,point.y+1.0))
//            floodPixel -= imageWidth
        }
        if (point.x >= 1.0) {
            floodPixel--
            self.floodFill(CGPointMake(point.x-1.0,point.y))
            floodPixel++
        }
        if (point.x <= CGFloat(imageWidth)-2.0) {
            floodPixel++
            self.floodFill(CGPointMake(point.x+1.0,point.y))
            floodPixel--
        }
    }

Here is the calling code:

…….
    pixelBuffer = UnsafeMutablePointer<UInt32>(CGBitmapContextGetData(context))
    var pixelPos:Int = imageWidth * Int(point.y) + Int(point.x)
    floodPixel = pixelBuffer!
    floodPixel += pixelPos
    self.floodFill(point)
…….

In the floodFill() method, if I uncomment the 2 commented lines, the program runs for a while and crashes at some point. I presume this is where the real issue is, because those lines should be uncommented.

If I permute the order of the 2 if-blocks: if (point.y >= 1.0) and if (point.y <= CGFloat(imageHeight)-2.0) then the part below the starting point is filled, instead the part above.

score 0 · Answer 1 · answered Oct 29 '15 at 07:00

0

Disclaimer: I do not know swift! But in general, a flood fill is recursive. So the function should be only dependent on it's arguments. In C++ that would be "static". But your function modifies "floodPixel" which is not an argument. Make sure your floodFill function only takes arguments to do it's work, not ANY class/object state.

answered Oct 29 '15 at 07:00

starmole

4,974
1
28
48

You are right, the use of floodPixel is there for optimization (having only one variable instead of one for each recursion). A way to make it for "static" which does not seem to exist in Swift. I do not think this is the problem here anyway. – Michel Oct 29 '15 at 07:41
I think it is the problem :) You modify "floodPixel" on every call. You should only modify point. And the first line should be something like pixel = floodpixels+point.x+point.y*floodpixles.width. – starmole Oct 29 '15 at 08:00
Hum, even though I have doubts I would like you to be right, if that could solve my problem. "floodPixel" is what I use to change the pixel color ( line:floodPixel.memory = rgba) and instead of your "pixel = floodpixels+point.x+point.y*floodpixles.width" I use: "floodPixel++","floodPixel += imageWidth",.... to change the pixel pointer location. As mentioned in the post, only the upper-left is displayed. Any shape is working properly (upper-left part). I had my previous trial using a local variable instead of a global, but it was crashing (probably to much memory needed for recursion). – Michel Oct 29 '15 at 08:14
I am very sure this is the main problem. Try stepping through it in your head. Why do you even change point on the recursive call? You never use it! But you change floodPixel but never change it back, Step through it on a piece of graph paper. – starmole Oct 29 '15 at 09:00
Maybe, I also thought about changing it back. See the 4 commented lines. But if I do that it crashes (don't know why). One more thing: if I invert the order of the 2 if blocks: “if (point.y >= 1.0)” and “if (point.y <= CGFloat(imageHeight)-2.0)” then bottom-left is displayed instead of the upper-left. That sounds like a stupid detail I am missing. – Michel Oct 29 '15 at 09:18
The cleanest thing would be to clip point at the start: if (point.x<0 || >width || ... ) return; It should be the first line. Then there is no need to check later. Then check if pixel at point is go/no go: if it is nay, return. Otherwise, fill it and recurse to 4 directions. No need to check any if there. If you pass in out of bounds, the next call will just ignore it. – starmole Oct 29 '15 at 09:26
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/93657/discussion-between-starmole-and-michel). – starmole Oct 29 '15 at 09:33

Flood-fill, only half-working in Swift

1 Answers1