Bucket-Fill Algorithm – What Is the Best Bucket-Fill Algorithm?

After a little browsing, I created my own solution a few months back but failed to post it here in the interest of anybody that would like to do the same. Therefore, I will quickly describe the method before showing the code. It's in kotlin, but if you're familiar with Java and/or AS3 you should be able to understand the syntax.

The Method

1. Scan the entire image and store each color in a table.
2. Determine which color shows up most often- this is the background color
3. Start at the top left and scan each line.
4. If a pixel does not match the background color, then it is a sprite.
5. Use a backtracking algorithm to "fill out" the entire sprite.
6. Create a rectangle out of this plot.
7. Store it and cut the sprite out of the image.
8. Repeat 4-7 until finished.

The Code

The source is available on github, and here is the code w/o documentation or imports.

 fun unpack(spriteSheet: Path): List<Image> {
    Preconditions.checkArgument(Files.exists(spriteSheet),
                                "The file ${spriteSheet.getFileName()} does not exist")

    logger.debug("Loading sprite sheet.")
    // TODO: Convert to png so we have an alpha layer to work with
    val spriteSheetImage = readImage(spriteSheet).toBufferedImage()

    logger.debug("Determining most probable background color.")
    val backgroundColor  = determineProbableBackgroundColor(spriteSheetImage)
    logger.debug("The most probable background color is $backgroundColor")

    return findSprites(spriteSheetImage, backgroundColor) map(::copySubImage.bindFirst(spriteSheetImage))
}

private fun findSprites(image: BufferedImage,
                        backgroundColor: Color): List<Rectangle> {
    val workingImage = copy(image)

    val spriteRectangles = ArrayList<Rectangle>()
    for (pixel in workingImage) {
        val (point, color) = pixel

        if (color != backgroundColor) {
            logger.debug("Found a sprite starting at (${point.x}, ${point.y})")
            val spritePlot = findContiguous(workingImage, point) { it != backgroundColor }
            val spriteRectangle = Rectangle(spritePlot, image)

            logger.debug("The identified sprite has an area of ${spriteRectangle.width}x${spriteRectangle.height}")

            spriteRectangles.add(spriteRectangle)
            eraseSprite(workingImage, backgroundColor, spritePlot)
        }
    }

    logger.info("Found ${spriteRectangles.size()} sprites.")
    return spriteRectangles
}

private fun findContiguous(image: BufferedImage, point: Point, predicate: (Color) -> Boolean): List<Point> {
    val unvisited = LinkedList<Point>()
    val visited   = HashSet<Point>()

    unvisited.addAll(neighbors(point, image) filter { predicate(Color(image.getRGB(it.x, it.y))) })

    while (unvisited.isNotEmpty()) {
        val currentPoint = unvisited.pop()
        val currentColor = Color(image.getRGB(currentPoint.x, currentPoint.y))

        if (predicate(currentColor)) {
            unvisited.addAll(neighbors(currentPoint, image) filter {
                !visited.contains(it) && !unvisited.contains(it) &&
                predicate(Color(image.getRGB(it.x, it.y)))
            })

            visited.add(currentPoint)
        }
    }

    return visited.toList()
}

private fun neighbors(point: Point, image: Image): List<Point> {
    val points = ArrayList<Point>()

    if (point.x > 0)
        points.add(Point(point.x - 1, point.y))
     if (point.x < image.getWidth(null) - 1)
     points.add(Point(point.x + 1, point.y))

     if (point.y > 0)
     points.add(Point(point.x, point.y - 1))
     if (point.y < image.getHeight(null) - 1)
     points.add(Point(point.x, point.y + 1))

     return points
 }

However, the code is not yet complete- packing and creating the metafile is missing- and has been languishing in my Github since March, but I'll hopefully complete it one day.

If the number of hours each person is available is constant (e.g. it's always 1 hour), then your problem can be modeled as a Network Flow, easily solvable in polynomial time with Ford-Fulkerson's algorithm.

To build your flow network, create two layers of nodes; the first layer represents your balls, the second layer represents your buckets. Add an edge from the source to each ball with capacity 1. Add an edge from each ball to each compatible bucket with capacity 1. Add an edge from each bucket to the sink with capacity corresponding to the bucket capacity. Maximum flow represents optimal assignment.

Otherwise, if the number of hours each person can contribute varies, then the above algorithm does not work due to your constraint that each person can only visit one location. (Network flow would solve the problem, but it might split one person's hours across multiple locations.) In this case you have something that's related to a Knapsack or Bin Packing problem.

If the number of hours each person can contribute is an integer, you can solve it via pseudo-polynomial dynamic programming. Otherwise, you have to either:

1. Implement a brute-force backtracking algorithm. This will give you an exact solution but will not work if the number of people or locations exceeds 50 or so.
2. Implement a combinatorial heuristic method, as Doc Brown suggested. Hill Climbing or Simulated Annealing will perform very well for this problem and give you optimal or nearly optimal results very quickly.