Search code examples
androidalgorithmkotlinflood-fill

Iterative queue-based flood fill algorithm 'expandToNeighborsWithMap()' function is unusually slow

I am creating a pixel art editor for Android, and as for all pixel art editors, a paint bucket (fill tool) is a must need.

To do this, I did some research on flood fill algorithms online.

I stumbled across the following video which explained how to implement an iterative flood fill algorithm in your code. The code used in the video was JavaScript, but I was easily able to convert the code from the video to Kotlin:

https://www.youtube.com/watch?v=5Bochyn8MMI&t=72s&ab_channel=crayoncode

Here is an excerpt of the JavaScript code from the video:

enter image description here

Converted code:

Tools.FILL_TOOL -> {
            val seedColor = instance.rectangles[rectTapped]?.color ?: Color.WHITE

            val queue = LinkedList<XYPosition>()

            queue.offer(MathExtensions.convertIndexToXYPosition(rectangleData.indexOf(rectTapped), instance.spanCount.toInt()))

            val selectedColor = getSelectedColor()

            while (queue.isNotEmpty() && seedColor != selectedColor) { // While the queue is not empty the code below will run
                val current = queue.poll()
                val color = instance.rectangles.toList()[convertXYDataToIndex(instance, current)].second?.color ?: Color.WHITE

                if (color != seedColor) {
                    continue
                }

                instance.extraCanvas.apply {
                    instance.rectangles[rectangleData[convertXYDataToIndex(instance, current)]] = defaultRectPaint // Colors in pixel with defaultRectPaint
                    drawRect(rectangleData[convertXYDataToIndex(instance, current)], defaultRectPaint)

                    for (index in expandToNeighborsWithMap(instance, current)) {
                        val candidate = MathExtensions.convertIndexToXYPosition(index, instance.spanCount.toInt())
                        queue.offer(candidate)
                    }
                }
            }
        }

Now, I want to address two major issues I'm having with the code of mine:

  • Performance

  • Flooding glitch (fixed by suggestion from person in the comments)

Performance

A flood fill needs to be very fast and shouldn't take less than a second, the problem is, say I have a canvas of size 50 x 50, and I decide to fill in the whole canvas, it can take up to 8 seconds or more.

Here is some data I've compiled for the time it's taken to fill in a whole canvas given the spanCount value:

spanCount approx time taken in seconds to fill whole canvas
10 <1 seconds
20 ~2 seconds
40 ~6 seconds
60 ~15 seconds
100 ~115 seconds

The conclusion from the data is that the flood fill algorithm is unusually slow.

To find out why, I decided to test out which parts of the code are taking the most time to compile. I came to the conclusion that the expandToNeighbors function is taking the most time out of all the other tasks:

enter image description here

Here is an excerpt of the expandToNeighbors function:

fun expandToNeighbors(instance: MyCanvasView, from: XYPosition): List<Int> {
    var asIndex1 = from.x
    var asIndex2 = from.x

    var asIndex3 = from.y
    var asIndex4 = from.y

    if (from.x > 1) {
        asIndex1 = xyPositionData!!.indexOf(XYPosition(from.x - 1, from.y))
    }

    if (from.x < instance.spanCount) {
        asIndex2 = xyPositionData!!.indexOf(XYPosition(from.x + 1, from.y))
    }

    if (from.y > 1) {
        asIndex3 = xyPositionData!!.indexOf(XYPosition(from.x, from.y - 1))
    }

    if (from.y < instance.spanCount) {
        asIndex4 = xyPositionData!!.indexOf(XYPosition(from.x, from.y + 1))
    }

    return listOf(asIndex1, asIndex2, asIndex3, asIndex4)
}

To understand the use of the expandToNeighbors function, I would recommend watching the video that I linked above.

(The if statements are there to make sure you won't get an IndexOutOfBoundsException if you try and expand from the edge of the canvas.)

This function will return the index of the north, south, west, and east pixels from the xyPositionData list which contains XYPosition objects.

(The black pixel is the from parameter.)

enter image description here

The xyPositionData list is initialized once in the convertXYDataToIndex function, here:

var xyPositionData: List<XYPosition>? = null
var rectangleData: List<RectF>? = null

fun convertXYDataToIndex(instance: MyCanvasView, from: XYPosition): Int {

    if (rectangleData == null) {
        rectangleData = instance.rectangles.keys.toList()
    }

    if (xyPositionData == null) {
        xyPositionData = MathExtensions.convertListOfSizeNToListOfXYPosition(
            rectangleData!!.size,
            instance.spanCount.toInt()
        )
    }

    return xyPositionData!!.indexOf(from)
}

So, the code works fine (kind of) but the expandToNeighbors function is very slow, and it is the main reason why the flood fill algorithm is taking a long time.

My colleague suggested that indexOf may be slowing everything down, and that I should probably switch to a Map-based implementation with a key being XYPosition and a value being Int representing the index, so I replaced it with the following:

fun expandToNeighborsWithMap(instance: MyCanvasView, from: XYPosition): List<Int> {
    var asIndex1 = from.x
    var asIndex2 = from.x

    var asIndex3 = from.y
    var asIndex4 = from.y

    if (from.x > 1) {
        asIndex1 = rectangleDataMap!![XYPosition(from.x - 1, from.y)]!!
    }

    if (from.x < instance.spanCount) {
        asIndex2 =  rectangleDataMap!![XYPosition(from.x + 1, from.y)]!!
    }

    if (from.y > 1) {
        asIndex3 =  rectangleDataMap!![XYPosition(from.x, from.y - 1)]!!
    }

    if (from.y < instance.spanCount) {
        asIndex4 = rectangleDataMap!![XYPosition(from.x, from.y + 1)]!!
    }

    return listOf(asIndex1, asIndex2, asIndex3, asIndex4)
}

It functions the same way, only this time it uses a Map which is initialized here:

var xyPositionData: List<XYPosition>? = null
var rectangleData: List<RectF>? = null
var rectangleDataMap: Map<XYPosition, Int>? = null

fun convertXYDataToIndex(instance: MyCanvasView, from: XYPosition): Int {

    if (rectangleData == null) {
        rectangleData = instance.rectangles.keys.toList()
    }

    if (xyPositionData == null) {
        xyPositionData = MathExtensions.convertListOfSizeNToListOfXYPosition(
            rectangleData!!.size,
            instance.spanCount.toInt()
        )
    }

    if (rectangleDataMap == null) {
        rectangleDataMap = MathExtensions.convertListToMap(
            rectangleData!!.size,
            instance.spanCount.toInt()
        )
    }

    return xyPositionData!!.indexOf(from)
}

Converting the code to use a map increased the speed by around 20%, although the algorithm is still slow.

After trying to make the algorithm work faster, I'm out of ideas and I'm unsure why the expandToNeighbors function is taking a long time.

Implementation-wise it is quite messy unfortunately because of the whole list index to XYPosition conversions, but at least it works - the only problem is the performance.

So I have two one major problem.

I've actually pushed the fill tool to GitHub as a KIOL (Known Issue or Limitation), so the user can use the fill tool if they want, but they need to be aware of the limitations/issues. This is so anyone can have a look at my code and reproduce the bugs.

Link to repository:

https://github.com/realtomjoney/PyxlMoose

Edit

I understand that this question is extremely difficult to answer and will require a lot of thinking. I would recommend cloning PyxlMoose and reproduce the errors, then work from there. Relying on the code snippets isn't enough.

Formula for converting XY position to an index

Somebody in the comments suggested a formula for converting an XYPosition to an index value, I came up with the following method which works:

    fun convertXYPositionToIndex(xyPosition: XYPosition, spanCount: Int): Int {
        val positionX = xyPosition.x
        val positionY = xyPosition.y

        return (spanCount - positionY) + (spanCount * (positionX - 1))
    }

The only problem is - it increases the speed by around 50% but it's still taking around 10-15 seconds to fill in an area of 80 by 80 pixels, so it has helped to a large degree although it's still very slow.

Solution

  • How I fixed it:

    • Getting rid of the toList() calls.
    • Creating an convertXYPositionToIndex() function.

    Here is my new code:

       Tools.FILL_TOOL -> {
            val seedColor = instance.rectangles[rectTapped]?.color ?: Color.WHITE

            val queue = LinkedList<XYPosition>()

            val spanCount = instance.spanCount.toInt()

            queue.offer(MathExtensions.convertIndexToXYPosition(rectangleData.indexOf(rectTapped), spanCount))

            val selectedColor = getSelectedColor()

            while (queue.isNotEmpty() && seedColor != selectedColor) {

                val current = queue.poll()

                val color = instance.rectangles[rectangleData[convertXYDataToIndex(spanCount, current)]]?.color ?: Color.WHITE

                if (color != seedColor) {
                    continue
                }

                instance.rectangles[rectangleData[convertXYDataToIndex(spanCount, current)]] = defaultRectPaint // Colors in pixel with defaultRectPaint
                instance.extraCanvas.drawRect(rectangleData[MathExtensions.convertXYPositionToIndex(current, spanCount)], defaultRectPaint)

                for (index in expandToNeighborsWithMap(spanCount, current)) {
                    val candidate = MathExtensions.convertIndexToXYPosition(index, spanCount)
                    queue.offer(candidate)
                }
            }
            val timeTakenForThis = (System.currentTimeMillis()-startTime)
            totalTime += timeTakenForThis
        }

    Expand to neighbors func:

    fun expandToNeighborsWithMap(spanCount: Int, from: XYPosition): List<Int> {
    val toReturn = mutableListOf<Int>()

    if (from.x > 1) {
        toReturn.add(MathExtensions.convertXYPositionToIndex(XYPosition(from.x - 1, from.y), spanCount))
    }

    if (from.x < spanCount) {
        toReturn.add(MathExtensions.convertXYPositionToIndex(XYPosition(from.x + 1, from.y), spanCount))
    }

    if (from.y > 1) {
        toReturn.add(MathExtensions.convertXYPositionToIndex(XYPosition(from.x, from.y - 1), spanCount))
    }

    if (from.y < spanCount) {
        toReturn.add(MathExtensions.convertXYPositionToIndex(XYPosition(from.x, from.y + 1), spanCount))
    }

    return toReturn
}

    It takes less than a second for canvas sizes of 100 by 100 and 200 by 200, so I'd say it's in the usable stage now.

    I would say this is one of the simplest Android flood fill algorithms out there to understand, so if anyone is making an app similar to mine and they want a flood fill tool they can copy my code.

    A guy in the comments called EvilTalk helped me with this.