I am using a flood fill algorithm that works fine for single color, solid color, and gradient color fills. However, it takes many seconds to complete coloring, whether for small or large areas.

Can anyone tell me why it takes so much time and how to improve it?

1. Is it possible to achieve fast flood fill performance in an Android application using Java or Kotlin?
2. I want to color the touched area within 1 second, whether it’s a small or large portion of the image.

Reference app link: InColor on Play Store

My FloodFill class code:

object FloodFill {
    private var floodFillInProgress = false

    suspend fun floodFill(
        bitmap: Bitmap,
        point: Point,
        targetColor: Int,
        shader: Shader?,
        newColor: Int,
        tolerance: Int = 0,
        onProgress: (Bitmap) -> Unit
    ) = withContext(Dispatchers.IO) {
        if (floodFillInProgress) return@withContext

        floodFillInProgress = true

        if (shader == null && targetColor == newColor) {
            floodFillInProgress = false
            return@withContext
        }

        try {
            val width = bitmap.width
            val height = bitmap.height
            val queue = kotlin.collections.ArrayDeque<Point>()
            queue.add(point)

            val fillInterval = if (isHighPerformanceDevice()) 1000 else 1000

            var count = 0

            val visited = BooleanArray(width * height)
            val buffer = IntArray(width * height)
            bitmap.getPixels(buffer, 0, width, 0, 0, width, height)

            val tempBitmap = Bitmap.createBitmap(width, height, Bitmap.Config.ARGB_8888)
            val shaderCanvas = Canvas(tempBitmap)
            val shaderPaint = Paint().apply {
                this.shader = shader
            }
            shaderCanvas.drawRect(0f, 0f, width.toFloat(), height.toFloat(), shaderPaint)

            while (queue.isNotEmpty()) {
                val p = queue.removeFirst()
                val x = p.x
                val y = p.y

                if (x < 0 || y < 0 || x >= width || y >= height) continue

                val index = y * width + x
                if (visited[index]) continue

                val pixelColor = buffer[index]
                if (pixelColor == Color.BLACK || !colorMatch(pixelColor, targetColor, tolerance)) continue

                visited[index] = true

                if (shader != null) {
                    buffer[index] = tempBitmap.getPixel(x, y)
                } else {
                    buffer[index] = newColor
                }

                queue.add(Point(x - 1, y))
                queue.add(Point(x + 1, y))
                queue.add(Point(x, y - 1))
                queue.add(Point(x, y + 1))

                count++
                if (count % fillInterval == 0) {
                    withContext(Dispatchers.Main) {
                        bitmap.setPixels(buffer, 0, width, 0, 0, width, height)
                        onProgress(bitmap)
                    }
                }
            }

            withContext(Dispatchers.Main) {
                bitmap.setPixels(buffer, 0, width, 0, 0, width, height)
                onProgress(bitmap)
            }
        } catch (e: IllegalStateException) {
            Log.e("FloodFill", "Bitmap was recycled during flood fill operation", e)
        } finally {
            floodFillInProgress = false
        }
    }

    private fun colorMatch(pixelColor: Int, targetColor: Int, tolerance: Int): Boolean {
        if (tolerance == 0) {
            return pixelColor == targetColor
        }

        val r = Color.red(pixelColor)
        val g = Color.green(pixelColor)
        val b = Color.blue(pixelColor)
        val targetR = Color.red(targetColor)
        val targetG = Color.green(targetColor)
        val targetB = Color.blue(targetColor)

        return abs(r - targetR) <= tolerance &&
                abs(g - targetG) <= tolerance &&
                abs(b - targetB) <= tolerance
    }

    private fun isHighPerformanceDevice(): Boolean {
        val memoryClass = (Runtime.getRuntime().maxMemory() / (1024 * 1024)).toInt()
        return memoryClass > 256
    }
}

View class where I call the flood fill:

private suspend fun paint(x: Int, y: Int) {
    Log.d("ColorPaintView", "paint called at: $x, $y")
    val bmp = bitmap ?: return
    if (bmp.isRecycled) return
    if (x < 0 || y < 0 || x >= bmp.width || y >= bmp.height) return
    val targetColor = bmp.getPixel(x, y)
    Log.d("ColorPaintView", "targetColor: $targetColor")
    if (targetColor == Color.BLACK) return

    val shader: Shader? = when (gradientType) {
        GradientType.NONE -> null
        GradientType.LINEAR -> {
            val angle = 235.0
            val angleInRadians = Math.toRadians(angle)
            val length = sqrt((bmp.width * bmp.width + bmp.height * bmp.height).toDouble()).toFloat()

            val startX = x.toFloat()
            val startY = y.toFloat()
            val endX = (x + length * cos(angleInRadians)).toFloat().coerceAtMost(bmp.width - 1f)
            val endY = (y + length * sin(angleInRadians)).toFloat().coerceAtMost(bmp.height - 1f)

            LinearGradient(startX, startY, endX, endY, gradientColors, gradientPositions, Shader.TileMode.MIRROR)
        }
        GradientType.RADIAL -> {
            RadialGradient(x.toFloat(), y.toFloat(), (bmp.width.coerceAtLeast(bmp.height) / 2).toFloat(), gradientColors, gradientPositions, Shader.TileMode.CLAMP)
        }
    }

    Log.d("ColorPaintView", "Starting flood fill")
    addLastAction(Bitmap.createBitmap(bmp))

    FloodFill.floodFill(bmp, Point(x, y), targetColor, shader, paintColor, 25) { updatedBitmap ->
        Log.d("ColorPaintView", "Flood fill completed")
        bitmap = updatedBitmap
        invalidate()
    }
}