我正在为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秒|
| 二十个|约2秒|
| 四十|约6秒|
| 六十|约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函数的用法，我建议观看上面链接的视频。*

(The if语句可以确保在尝试从画布边缘展开时不会得到IndexOutOfBoundsException。）
此函数将从包含XYPosition对象的xyPositionData列表中返回北、南、西和东像素的索引。
(The黑色像素是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)
}

将代码转换为使用Map后，速度提高了约20%，但算法仍然很慢。

在尝试使算法更快地工作后，我没有主意了，我不确定为什么expandToNeighbors函数要花很长时间。
不幸的是，由于整个列表索引到XYPosition的转换，它的实现相当混乱，但至少它是有效的-唯一的问题是性能。
所以我有两个主要的问题。
实际上我已经把填充工具作为KIOL（已知问题或限制）推到了GitHub，所以用户 * 可以 * 使用填充工具，如果他们愿意的话，但是他们需要知道限制/问题。这是为了让任何人都可以看到我的代码并重现bug。
链接到存储库：
https://github.com/realtomjoney/PyxlMoose

编辑

我知道这个问题很难回答，需要大量的思考。我建议克隆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乘80像素的区域，所以它在很大程度上帮助，虽然它仍然非常慢。