如何实现洪水填充算法?

本文介绍了如何实现洪水填充算法?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在开发一个Paint应用程序，其中正在实现类似于MS Paint应用程序的BucketFill功能.

我已经使用了几种FloodFill算法对其进行了编码，但是填充颜色的过程花费了太多时间.我不太确定其背后的原因可能是由于高速缓存内存不足，算法不佳，或者可能需要花费大量时间来计算偏移量.

有人可以帮助我解决您对Flutter/Dart的了解吗?

尝试过的算法:

• 基于递归的方法(4或8个连接方法)
• 基于队列的方法
• 基于堆栈的方法
• 基于QueueLinear的方法

最重要的是，性能非常慢

import'dart:collection';导入'dart:math';导入'package:flutter/material.dart';导入'dart:ui';导入'dart:async';导入'package:flutter/rendering.dart';导入'dart:typed_data';将'dart:ui'导入为ui；class BucketFill {List< Offset>_points =< Offset> [];列出单词;静态整数宽度；颜色oldColor，像素；int imageWidth;int imageHeight;未来< List>capturePng(GlobalKey key，Offset offset)异步{RenderRepaintBoundary边界= key.currentContext.findRenderObject();ui.Image image =等待boundary.toImage();最终rgbaImageData =等待image.toByteData(format:ui.ImageByteFormat.rawRgba);imageHeight = image.height;imageWidth = image.width;单词= Uint32List.view(rgbaImageData.buffer，rgbaImageData.offsetInBytes，rgbaImageData.lengthInBytes〜/Uint32List.bytesPerElement);oldColor = _getColor(words，offset.dx，offset.dy);返回_floodfill(oldColor，offset.dx，offset.dy);}颜色_getColor(Uint32List words，double x1，double y1){int x = x1.toInt();int y = y1.toInt();var offset = x + y * imageWidth;返回Color(words [offset]);}//基于队列的方法.List< Offset>_floodfill(Color oldColor，double x，double y){队列< Offset>queue = new Queue();偏移温度；queue.add(Offset(x，y));_points = List.from(_points).. add(queue.first);while(queue.isNotEmpty){temp = queue.first;queue.removeFirst();如果(_shouldFillColor(temp.dx + 2，temp.dy)){queue.add(Offset(temp.dx + 2，temp.dy));_points.add(Offset(temp.dx + 2，temp.dy));}如果(_shouldFillColor(temp.dx-2，temp.dy)){queue.add(Offset(temp.dx-2，temp.dy));_points.add(Offset(temp.dx-2，temp.dy));}如果(_shouldFillColor(temp.dx，temp.dy + 2)){queue.add(Offset(temp.dx，temp.dy + 2));_points.add(Offset(temp.dx，temp.dy + 2));}如果(_shouldFillColor(temp.dx，temp.dy-2)){queue.add(Offset(temp.dx，temp.dy-2));_points.add(Offset(temp.dx，temp.dy-2));}}_points.add(null);返回_points;}bool _shouldFillColor(double x，double y){return(x> = 0&&x ＜imageWidth&&y> = 0&&&imageHeight&&！_points.contains(Offset(x，y)))?_getColor(words，x，y)== oldColor: 错误的;}}

解决方案

我最近为此制作了一个名为

如果您想了解有关我进行移植的更多信息，可以访问我的博客 www.meekcode/blog/flood-fill-in-flutter

I am working on one Paint application wherein I am implementing BucketFill functionality similar to MS paint application.

I have coded it using a couple of FloodFill algorithms but the filling color process is taking too much time. I am not pretty sure reasons behind it may happen due to the low cache memory, poor algorithm, or it may be taking a lot of time calculating offsets.

Can someone help me out with your Knowledge in Flutter/Dart?

Algorithms tried:

• Recursion Based Approach(4 or 8 connected Method)
• Queue-Based approach
• Stack Based Approach
• QueueLinear Based Approach

With above all the performance is very slow

import 'dart:collection'; import 'dart:math'; import 'package:flutter/material.dart'; import 'dart:ui'; import 'dart:async'; import 'package:flutter/rendering.dart'; import 'dart:typed_data'; import 'dart:ui' as ui; class BucketFill { List<Offset> _points = <Offset>[]; Uint32List words; static int width; Color oldColor, pixel; int imageWidth; int imageHeight; Future<List> capturePng(GlobalKey key, Offset offset) async { RenderRepaintBoundary boundary = key.currentContext.findRenderObject(); ui.Image image = await boundary.toImage(); final rgbaImageData = await image.toByteData(format: ui.ImageByteFormat.rawRgba); imageHeight = image.height; imageWidth = image.width; words = Uint32List.view(rgbaImageData.buffer, rgbaImageData.offsetInBytes, rgbaImageData.lengthInBytes ~/ Uint32List.bytesPerElement); oldColor = _getColor(words, offset.dx, offset.dy); return _floodfill(oldColor, offset.dx, offset.dy); } Color _getColor(Uint32List words, double x1, double y1) { int x = x1.toInt(); int y = y1.toInt(); var offset = x + y * imageWidth; return Color(words[offset]); } // Queue based approach. List<Offset> _floodfill(Color oldColor, double x, double y) { Queue<Offset> queue = new Queue(); Offset temp; queue.add(Offset(x, y)); _points = List.from(_points)..add(queue.first); while (queue.isNotEmpty) { temp = queue.first; queue.removeFirst(); if (_shouldFillColor(temp.dx + 2, temp.dy)) { queue.add(Offset(temp.dx + 2, temp.dy)); _points.add(Offset(temp.dx + 2, temp.dy)); } if (_shouldFillColor(temp.dx - 2, temp.dy)) { queue.add(Offset(temp.dx - 2, temp.dy)); _points.add(Offset(temp.dx - 2, temp.dy)); } if (_shouldFillColor(temp.dx, temp.dy + 2)) { queue.add(Offset(temp.dx, temp.dy + 2)); _points.add(Offset(temp.dx, temp.dy + 2)); } if (_shouldFillColor(temp.dx, temp.dy - 2)) { queue.add(Offset(temp.dx, temp.dy - 2)); _points.add(Offset(temp.dx, temp.dy - 2)); } } _points.add(null); return _points; } bool _shouldFillColor(double x, double y) { return (x >= 0 && x < imageWidth && y >= 0 && y < imageHeight && !_points.contains(Offset(x, y))) ? _getColor(words, x, y) == oldColor : false; } }

解决方案

I just recently made a package for this called floodfill_image

Basically I use the Queue-Linear Flood Fill Algorithm by J. Dunlap and ported it into Flutter.

Here's the source code that I use for Flutter:

//Original algorithm by J. Dunlap queuelinearfloodfill.aspx //Java port by Owen Kaluza //Android port by Darrin Smith (Standard Android) //Flutter port by Garlen Javier import 'dart:async'; import 'dart:collection'; import 'dart:ui'; import 'package:image/image.dart' as img; class QueueLinearFloodFiller { img.Image image; int _width = 0; int _height = 0; int _cachedWidth = -1; int _cachedHeight = -1; int _fillColor = 0; int _tolerance = 8; List<int> _startColor = [0, 0, 0, 0]; List<bool> _pixelsChecked; Queue<_FloodFillRange> _ranges; QueueLinearFloodFiller(img.Image imgVal, int newColor) { image = imgVal; _width = image.width; _height = image.height; setFillColor(newColor); } void resize(Size size) { if (_cachedWidth != size.width.toInt() || _cachedHeight != size.height.toInt()) { image = img.copyResize(image, width: size.width.toInt(), height: size.height.toInt()); _width = image.width; _height = image.height; _cachedWidth = _width; _cachedHeight = _height; } } void setTargetColor(int targetColor) { _startColor[0] = img.getRed(targetColor); _startColor[1] = img.getGreen(targetColor); _startColor[2] = img.getBlue(targetColor); _startColor[3] = img.getAlpha(targetColor); } void setTolerance(int value) { _tolerance = value.clamp(0, 100); } int getFillColor() { return _fillColor; } void setFillColor(int value) { _fillColor = value; } void _prepare() { // Called before starting flood-fill _pixelsChecked = List<bool>.filled(_width * _height, false); _ranges = Queue<_FloodFillRange>(); } // Fills the specified point on the bitmap with the currently selected fill // color. // int x, int y: The starting coords for the fill Future<void> floodFill(int x, int y) async { // Setup _prepare(); if (_startColor[0] == 0) { // ***Get starting color. int startPixel = image.getPixelSafe(x, y); _startColor[0] = img.getRed(startPixel); _startColor[1] = img.getGreen(startPixel); _startColor[2] = img.getBlue(startPixel); } // ***Do first call to floodfill. _linearFill(x, y); // ***Call floodfill routine while floodfill _ranges still exist on the // queue _FloodFillRange range; while (_ranges.length > 0) { // **Get Next Range Off the Queue range = _ranges.removeFirst(); // **Check Above and Below Each Pixel in the Floodfill Range int downPxIdx = (_width * (range.y + 1)) + range.startX; int upPxIdx = (_width * (range.y - 1)) + range.startX; int upY = range.y - 1; // so we can pass the y coord by ref int downY = range.y + 1; for (int i = range.startX; i <= range.endX; i++) { // *Start Fill Upwards // if we're not above the top of the bitmap and the pixel above // this one is within the color tolerance if (range.y > 0 && (!_pixelsChecked[upPxIdx]) && _checkPixel(i, upY)) { _linearFill(i, upY); } // *Start Fill Downwards // if we're not below the bottom of the bitmap and the pixel // below this one is within the color tolerance if (range.y < (_height - 1) && (!_pixelsChecked[downPxIdx]) && _checkPixel(i, downY)) { _linearFill(i, downY); } downPxIdx++; upPxIdx++; } } } // Finds the furthermost left and right boundaries of the fill area // on a given y coordinate, starting from a given x coordinate, filling as // it goes. // Adds the resulting horizontal range to the queue of floodfill _ranges, // to be processed in the main loop. // // int x, int y: The starting coords void _linearFill(int x, int y) { // ***Find Left Edge of Color Area int lFillLoc = x; // the location to check/fill on the left int pxIdx = (_width * y) + x; while (true) { // **fill with the color //pixels[pxIdx] = _fillColor; image.setPixelSafe(lFillLoc, y, _fillColor); // **indicate that this pixel has already been checked and filled _pixelsChecked[pxIdx] = true; // **de-increment lFillLoc--; // de-increment counter pxIdx--; // de-increment pixel index // **exit loop if we're at edge of bitmap or color area if (lFillLoc < 0 || (_pixelsChecked[pxIdx]) || !_checkPixel(lFillLoc, y)) { break; } } lFillLoc++; // ***Find Right Edge of Color Area int rFillLoc = x; // the location to check/fill on the left pxIdx = (_width * y) + x; while (true) { // **fill with the color image.setPixelSafe(rFillLoc, y, _fillColor); // **indicate that this pixel has already been checked and filled _pixelsChecked[pxIdx] = true; // **increment rFillLoc++; // increment counter pxIdx++; // increment pixel index // **exit loop if we're at edge of bitmap or color area if (rFillLoc >= _width || _pixelsChecked[pxIdx] || !_checkPixel(rFillLoc, y)) { break; } } rFillLoc--; // add range to queue _FloodFillRange r = new _FloodFillRange(lFillLoc, rFillLoc, y); _ranges.add(r); } // Sees if a pixel is within the color tolerance range. bool _checkPixel(int x, int y) { int pixelColor = image.getPixelSafe(x, y); int red = img.getRed(pixelColor); int green = img.getGreen(pixelColor); int blue = img.getBlue(pixelColor); int alpha = img.getAlpha(pixelColor); return (red >= (_startColor[0] - _tolerance) && red <= (_startColor[0] + _tolerance) && green >= (_startColor[1] - _tolerance) && green <= (_startColor[1] + _tolerance) && blue >= (_startColor[2] - _tolerance) && blue <= (_startColor[2] + _tolerance) && alpha >= (_startColor[3] - _tolerance) && alpha <= (_startColor[3] + _tolerance)); } } // Represents a linear range to be filled and branched from. class _FloodFillRange { int startX; int endX; int y; _FloodFillRange(int startX, int endX, int yPos) { this.startX = startX; this.endX = endX; this.y = yPos; } }

Here's a sample gif that would also show how fast this Algorithm in Flutter.

If you want to know more about the steps I made to port it, you can visit my blog www.meekcode/blog/flood-fill-in-flutter