基于迭代队列的洪水填充算法“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)
                    }
                }
            }
        }

---

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

• 表现

• 洪水故障（根据评论中的建议修复）

---

表现

洪水填充需要非常快，并且不应少于一秒，问题是，假设我有一个尺寸为 50 x 50 的画布，并且我决定填充整个画布，则最多可能需要 8 秒或者更多。

以下是我在给定值的情况下填充整个画布所需的时间编译的一些数据spanCount：

跨度计数	填满整个画布所需的大约时间（以秒为单位）
10	<1秒
20	〜2秒
40	〜6秒
60	〜15秒
100	约 115 秒

从数据得出的结论是洪水填充算法异常缓慢。

为了找出原因，我决定测试代码的哪些部分编译时间最长。我得出的结论是，该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 语句的作用是确保您IndexOutOfBoundsException尝试从画布边缘扩展时不会出现 if 语句。）

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，因此用户可以根据需要使用填充工具，但他们需要了解限制/问题。这样任何人都可以查看我的代码并重现错误。

链接到存储库：

https://github.com/realtomjoney/PyxlMoose

编辑

我知道这个问题很难回答，需要很多思考。我建议克隆 PyxlMoose 并重现错误，然后从那里开始工作。仅仅依靠代码片段是不够的。

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

评论中有人提出了一个将 an 转换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

我是如何修复它的：

• 摆脱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
        }

扩展到邻居函数：

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
}

对于 100 x 100 和 200 x 200 的画布尺寸，只需不到一秒，所以我想说它现在处于可用阶段。

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

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