Android：基于迭代佇列的洪水填充演算法“expandToNeighborsWithMap()”函式例外緩慢

（已找到解決方案，請避免繼續閱讀。）

我正在為 Android 創建一個像素藝術編輯器，對于所有像素藝術編輯器，油漆桶（填充工具）是必須的。

為此，我在網上對洪水填充演算法進行了一些研究。

我偶然發現了以下視頻，其中解釋了如何在您的代碼中實作迭代洪水填充演算法。視頻中使用的代碼是 JavaScript，但我可以輕松地將視頻中的代碼轉換為 Kotlin：

轉換后的代碼：

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

現在，我想解決我的代碼遇到的兩個主要問題：

• 表現

• 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:

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:

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

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 spending a couple of days 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. Any help would be appreciated to fix this issue.

Apologies if I didn't do a good enough job of explaining the exact issue, but I have tried my best. 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, if anyone can try and find a solution for it, it would be great because I have tried to myself without much luck.

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 who wants to help me fix this can have a look at my code and reproduce the bugs.

Link to repository:

https://github.com/realtomjoney/PyxlMoose

Edit after bounty

I understand that this question is extremely difficult to answer and will require a lot of thinking. I've tried myself to fix these issues but haven't had much success, so I'm offering 50 reputation for anyone who can assist.

I would recommend you clone 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. But thank you very much for the suggestion anyways, it has helped a lot :)

uj5u.com熱心網友回復：

我認為性能問題是因為expandToNeighbors方法一直生成 4 個點。它在邊界上變得至關重要，在那里你最好生成 3 個（甚至 2 個在角落）點，所以額外的點又是當前位置。所以第一個邊界點在點數之后加倍，第二個又加倍（現在是 x4），依此類推。

如果我是對的，你看到的不是慢速方法有效，而是它被呼叫得太頻繁了。

uj5u.com熱心網友回復：

我是如何修復它的：

• 擺脫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 的人幫了我這個忙。

標籤：android algorithm kotlin flood-fill

上一篇：使陣列相等的最小傳輸

下一篇：如何驗證這種型別的變數？