Android：基于迭代队列的泛洪填充算法 'expandToNeighborsWithMap()' 函数异常缓慢

Question

（已找到解决方案，请避免继续阅读。）

我正在为 Android 创建一个像素艺术编辑器，对于所有像素艺术编辑器来说，一个油漆桶（填充工具）是必不可少的。

为此，我在网上对洪水填充算法进行了一些研究。

我偶然发现了以下视频，该视频解释了如何在您的代码中实现迭代洪水填充算法。视频中使用的代码是 JavaScript，但我很容易将视频中的代码转换为 Kotlin：

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

以下是视频中 JavaScript 代码的摘录：

转换后的代码：

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)
                    }
                }
            }
        }

现在，我想解决我的代码中遇到的两个主要问题：

性能
~~泛洪故障~~（根据评论中的人的建议修复）

性能

填充需要非常快，不能少于一秒，问题是，假设我有一个 canvas 尺寸为 50 x 50，我决定填充整个canvas，最多可能需要 8 秒或更长时间。

这是我在给定 spanCount 值的情况下填写整个 canvas 时所编译的一些数据：

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

数据得出的结论是，flood fill 算法异常缓慢。

为了找出原因，我决定测试代码的哪些部分编译时间最长。我得出的结论是 expandToNeighbors 函数在所有其他任务中花费的时间最多：

这里是 expandToNeighbors 函数的摘录：

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)
}

要了解 expandToNeighbors 功能的使用，我建议观看上面链接的视频。

（if 语句用于确保如果您尝试从 canvas 的边缘扩展，您不会得到 IndexOutOfBoundsException。）

此函数将 return xyPositionData 列表中包含 XYPosition 个对象的北、南、西和东像素的索引。

（黑色像素是from参数。）

xyPositionData列表在convertXYDataToIndex函数中初始化一次，这里：

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)
}

所以，代码工作正常（有点），但是 expandToNeighbors 函数非常慢，这是洪水填充算法花费很长时间的主要原因。

我的同事建议 indexOf 可能会减慢一切，我应该切换到基于 Map 的实现，键为 XYPosition，值为 Int表示索引，所以我将其替换为以下内容：

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)
}

它的功能是一样的，只是这次它使用了一个在此处初始化的 Map:

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)
}

将代码转换为使用地图，速度提高了大约 20%，尽管算法仍然很慢。

在花了几天时间尝试使算法运行得更快之后，我没有想法，而且我不确定为什么 expandToNeighbors 函数需要很长时间。如果能解决此问题，我们将不胜感激。

如果我没有很好地解释确切的问题，我深表歉意，但我已尽力而为。不幸的是，由于整个列表索引到 XYPosition 转换，实现方面它非常混乱，但至少它有效 - 唯一的问题是性能。

所以我有两个一个主要问题，如果有人可以尝试找到解决方案，那就太好了，因为我自己尝试过，但运气不佳。

我实际上已经将填充工具作为 KIOL（已知问题或限制）推送到 GitHub，因此用户可以如果需要使用填充工具, 但他们需要注意 limitations/issues。 这是为了让任何想帮助我解决此问题的人都可以查看我的代码并重现错误。

Link 到存储库：

https://github.com/realtomjoney/PyxlMoose

赏金后编辑

我知道这个问题很难回答，需要很多思考。我已尝试自己解决这些问题，但收效甚微，因此我为任何可以提供帮助的人提供 50 声望。

我建议您克隆 PyxlMoose 并重现错误，然后从那里开始工作。仅仅依靠代码片段是不够的。

将XY位置转换为索引的公式

有人在评论中提出了一个将 XYPosition 转换为索引值的公式，我想出了以下有效的方法：

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

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

唯一的问题是 - 它提高了大约 50% 的速度，但它仍然需要大约 10-15 秒来填充 80 x 80 像素的区域，所以它在很大程度上有所帮助，尽管它仍然非常减缓。但是无论如何还是非常感谢你的建议，它帮助了很多:)

Answer 1

我认为性能问题是因为 expandToNeighbors 方法一直生成 4 个点。它在边界上变得至关重要，你最好在边界上生成 3 个（甚至角上 2 个）点，所以额外的点又是当前位置。所以第一个边界点在点数之后加倍，第二个边界点再次加倍（现在是 x4）等等。

如果我是对的，您看到的不是慢速方法起作用，而是它被调用得太频繁了。

Answer 2

我是如何修复它的：

摆脱 toList() 个电话。
正在创建一个 convertXYPositionToIndex() 函数。

这是我的新代码：

   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
        }

扩展到邻居 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
}

canvas 100 x 100 和 200 x 200 的尺寸需要不到一秒的时间，所以我认为它现在处于可用阶段。

我想说这是最简单的 Android 洪水填充算法之一，所以如果有人正在制作类似于我的应用程序并且他们想要一个洪水填充工具，他们可以复制我的代码。

评论中有个叫 EvilTalk 的人帮我解决了这个问题。

Android：基于迭代队列的泛洪填充算法 'expandToNeighborsWithMap()' 函数异常缓慢

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

algorithm

android

flood-fill

kotlin