问题描述
我正在创建一个绘图应用程序。当我选择一种非常深的颜色并在熊猫的脸部内画画时，边缘会留白。我希望我的代码为边界内的整个区域着色。这是
[Edit2]迭代分段填充
标准递归填充填充的问题这是有潜在危险的，并且经常导致Stack Overflows用于更大或更复杂的填充（例如尝试使用许多螺钉的螺旋......）更不用说它通常很慢。泛洪填充所需的内存量大约为填充像素数的倍数（因此，请使用您使用的所有变量和操作数，并以像素为单位乘以图像大小，很快就会出现大量数字）。
为了避免这种情况，你可以通过使用线段而不是像素来限制递归层。这将加速一切并限制内存使用量。这种方法也可以迭代完成，在这种情况下更好，所以算法是这样的：
-
有一个细分列表
seg []
我选择了水平线，因此每个细分都有
x0，x1，y和一些标志变量已完成供以后使用。从开始，列表为空。 -
从填充开始位置添加新细分
x，y
因此，只需扫描
x，y之前和之后的所有像素，以涵盖所有结果开始颜色（col0）到左边x0和右边x1并使用标志done = 0将新段添加到列表中。 -
循环所有
done = 0
设置
done = 1并扫描与其相邻的所有像素x =< x0，x1>和y = {y-1，y + 1}如果找到则尝试添加新细分（就像在＃2 中一样）但在添加之前测试所有其他细分以进行重叠。如果找到任何重叠的段，则使用新找到的段放大它并设置其done = 0否则添加新段。这样，段数不会太高。 -
循环＃3进行任何更改
至加快这一点你可以使用索引表
idx [] []，它将保存特定y段的所有索引坐标。我设置/使用它所以段[idx [y] [？]]。y = y -
循环所有细分和重新着色像素
此处 C ++ 我的代码：
// ---------------- -------------------------------------------------- ---------
//变量
// ---------------------------- -----------------------------------------------
Graphics :: TBitmap * bmp = NULL; //你的形象
联合颜色{DWORD dd; BYTE db [4]; }; //直接RGB通道访问
DWORD ** pixel = NULL; //直接32位像素访问
int xs = 0，ys = 0; //图像分辨率
int mx = 0，my = 0; //鼠标位置
int treshold = 50000; //颜色匹配阈值
// --------------------------------------- ------------------------------------
//颜色与阈值
比较// ------------------------------------------------ ---------------------------
bool color_equal（DWORD c0，DWORD c1）
{
static颜色c;
static int r，g，b;
c.dd = c0& 0x00FFFFFF; //屏蔽alpha通道只是为了确保
r = c.db [0]; // r0，g0，b0
g = c.db [1];
b = c.db [2];
c.dd = c1& 0x00FFFFFF;
r- = c.db [0]; R * = R; //（r0-r1）^ 2，（g0-g1）^ 2，（b0-b1）^ 2
g- = c.db [1]; G * =克;
b- = c.db [2]; B * = B;
return（r + g + b< = treshold）;
}
// --------------------------------------- ------------------------------------
bool color_nonequal（DWORD c0，DWORD c1）
{
静态颜色c;
static int r，g，b;
c.dd = c0& 0x00FFFFFF; //屏蔽alpha通道只是为了确保
r = c.db [0]; // r0，g0，b0
g = c.db [1];
b = c.db [2];
c.dd = c1& 0x00FFFFFF;
r- = c.db [0]; R * = R; //（r0-r1）^ 2，（g0-g1）^ 2，（b0-b1）^ 2
g- = c.db [1]; G * =克;
b- = c.db [2]; B * = B;
return（r + g + b> treshold）;
}
// --------------------------------------- ------------------------------------
//洪水填充按行$ b $分割b // ----------------------------------------------- ----------------------------
struct _segment
{
int x0，x1，y;
int done;
_segment（）{}; _segment（_segment& a）{* this = a; }; 〜_segment（）{}; _segment * operator =（const _segment * a）{* this = * a;归还这个; }; / * _ segment * operator =（const _segment& a）{... copy ... return this; }; * /
};
void floodfill_segmented（int x，int y，DWORD col）//这是洪水填充（x，y）起始位置的主要调用，col是填充颜色
{
// init变量
int i，j，k，e，ee，x0，x1;
_segment s，* p;
列表< _segment> SEG; // H线段
列表<列表与LT; INT> > IDX; //索引表seg [idx [y]]。y = y加速搜索
DWORD col0 = pixel [y] [x]& 0x00FFFFFF;
DWORD col1 = col& 0x00FFFFFF;
//完整性检查
if（color_equal（col0，col1））return;
//准备段表和宏
seg.allocate（ys<< 3）; seg.num = 0;
idx.allocate（ys）; idx.num = YS; for（i = 0; i< ys; i ++）idx.dat [i] .num = 0;
//在（x，y）处添加新段
//扫描该行以将其放大至
//与已添加的段合并而不是在它们重叠时添加新段
// ee = 1如果已经进行了更改
#define _seg_add \
{\
s.x0 = x; s.x1 = X; s.y = Y; s.done = 0; \
for（x = s.x0; x> = 0; x--）if（color_equal（col0，pixel [y] [x]））s.x0 = x;否则打破; \
for（x = s.x1; x< xs; x ++）if（color_equal（col0，pixel [y] [x]））s.x1 = x;否则打破; \
for（ee = 0，k = 0; k< idx.dat [sy] .num; k ++）\
{\
j = idx.dat [sy]。 DAT [K]; P = seg.dat + J; \
if（（p-> x0> = s.x0）&&（p-> x0< = s.x1））ee = 1; \
if（（p-> x1> = s.x0）&&（p-> x1< = s.x1））ee = 1; \
if（（p-> x0< = s.x0）&&（p-> x1> = s.x0））ee = 1; \
if（（p-> x0< = s.x1）&&（p-> x1> = s.x1））ee = 1; \
if（ee）\
{\
if（p-> x0> s.x0）{p-> done = 0;对 - > X0 = s.x0; } \
if（p-> x1< s.x1）{p-> done = 0;对 - > X 1 = s.x1; } \
s = * p; \
休息; \
} \
} \
if（ee）ee = p-> done; else {idx.dat [s.y] .add（seg.num）; seg.add（一个或多个）; } \
}
//第一段;
_seg_add;
for（e = 1; e;）
{
//添加新的相邻段
for（e = 0，p = seg.dat，i = 0; i< seg.num; i ++，p ++）
if（！p-> done）
{
p-> done = 1;
y = p-> y-1; if（y> = 0）for（x = p-> x0; x< = p-> x1; x ++）if（color_equal（col0，pixel [y] [x]））{_ seg_add; ！E | = EE; X = s.x1; P = seg.dat + I; }
y = p-> y + 1; if（y x0; x< = p-> x1; x ++）if（color_equal（col0，pixel [y] [x]））{_ seg_add; ！E | = EE; X = s.x1; P = seg.dat + I; }
}
}
#undef seg_add
// recolor
for（p = seg.dat，i = 0; i< seg.num; i ++，p ++ ）
for（x = p-> x0，y = p-> y; x< = p-> x1; x ++）
pixel [y] [x] = col;
}
// --------------------------------------- ------------------------------------
color_equal 只是将颜色与阈值进行比较（并且它应该是一个宏而不是一个函数来获得更多速度）。
我还使用我的动态列表模板，因此：
-
列表与LT;双> xxx;与double xxx []; -
xxx相同。 add（5）;将5添加到列表的末尾 -
xxx [7]访问数组元素（安全） -
xxx.dat [7]访问数组元素（不安全但快速直接访问） -
xxx.num是数组的实际使用大小 -
xxx.reset（）清除数组并设置xxx.num = 0 -
xxx.allocate （100）预分配空间100items
这里可以比较：
左边是源图像 720x720 像素螺旋，右边是从左下角填充后的结果花了 40 ms 代码不使用 idx [] 并使用数组范围检查 440 ms 相反。如果我使用标准的洪水填充，它会在几秒钟后因堆栈溢出而崩溃。另一方面，对于较小的填充，标准的递归填充通常比此更快。
I am creating a drawing application. When I select a very dark color and paint inside the Panda's face, the edges are left white. I want my code to color entire area bound within the borders. This is the LINK. These are the functions that I am using in javascript. How can I make them better?
function matchOutlineColor(r, g, b, a) {
return (r + g + b < 75 && a >= 50);
};
function matchStartColor(pixelPos, startR, startG, startB) {
var r = outlineLayerData.data[pixelPos],
g = outlineLayerData.data[pixelPos + 1],
b = outlineLayerData.data[pixelPos + 2],
a = outlineLayerData.data[pixelPos + 3];
// If current pixel of the outline image is black
if (matchOutlineColor(r, g, b, a)) {
return false;
}
r = colorLayerData.data[pixelPos];
g = colorLayerData.data[pixelPos + 1];
b = colorLayerData.data[pixelPos + 2];
// If the current pixel matches the clicked color
if (r === startR && g === startG && b === startB) {
return true;
}
// If current pixel matches the new color
if (r === curColor.r && g === curColor.g && b === curColor.b) {
return false;
}
return true;
};
function colorPixel(pixelPos, r, g, b, a) {
colorLayerData.data[pixelPos] = r;
colorLayerData.data[pixelPos + 1] = g;
colorLayerData.data[pixelPos + 2] = b;
colorLayerData.data[pixelPos + 3] = a !== undefined ? a : 255;
};
function floodFill(startX, startY, startR, startG, startB) {
document.getElementById('color-lib-1').style.display = "none";
document.getElementById('color-lib-2').style.display = "none";
document.getElementById('color-lib-3').style.display = "none";
document.getElementById('color-lib-4').style.display = "none";
document.getElementById('color-lib-5').style.display = "none";
change = false;
var newPos,
x,
y,
pixelPos,
reachLeft,
reachRight,
drawingBoundLeft = drawingAreaX,
drawingBoundTop = drawingAreaY,
drawingBoundRight = drawingAreaX + drawingAreaWidth - 1,
drawingBoundBottom = drawingAreaY + drawingAreaHeight - 1,
pixelStack = [
[startX, startY]
];
while (pixelStack.length) {
newPos = pixelStack.pop();
x = newPos[0];
y = newPos[1];
// Get current pixel position
pixelPos = (y * canvasWidth + x) * 4;
// Go up as long as the color matches and are inside the canvas
while (y >= drawingBoundTop && matchStartColor(pixelPos, startR, startG, startB)) {
y -= 1;
pixelPos -= canvasWidth * 4;
}
pixelPos += canvasWidth * 4;
y += 1;
reachLeft = false;
reachRight = false;
// Go down as long as the color matches and in inside the canvas
while (y <= drawingBoundBottom && matchStartColor(pixelPos, startR, startG, startB)) {
y += 1;
colorPixel(pixelPos, curColor.r, curColor.g, curColor.b);
if (x > drawingBoundLeft) {
if (matchStartColor(pixelPos - 4, startR, startG, startB)) {
if (!reachLeft) {
// Add pixel to stack
pixelStack.push([x - 1, y]);
reachLeft = true;
}
} else if (reachLeft) {
reachLeft = false;
}
}
if (x < drawingBoundRight) {
if (matchStartColor(pixelPos + 4, startR, startG, startB)) {
if (!reachRight) {
// Add pixel to stack
pixelStack.push([x + 1, y]);
reachRight = true;
}
} else if (reachRight) {
reachRight = false;
}
}
pixelPos += canvasWidth * 4;
}
}
};
// Start painting with paint bucket tool starting from pixel specified by startX and startY
function paintAt(startX, startY) {
var pixelPos = (startY * canvasWidth + startX) * 4,
r = colorLayerData.data[pixelPos],
g = colorLayerData.data[pixelPos + 1],
b = colorLayerData.data[pixelPos + 2],
a = colorLayerData.data[pixelPos + 3];
if (r === curColor.r && g === curColor.g && b === curColor.b) {
// Return because trying to fill with the same color
return;
}
if (matchOutlineColor(r, g, b, a)) {
// Return because clicked outline
return;
}
floodFill(startX, startY, r, g, b);
redraw();
};
You are using exact color fill for dithered/smoothed/antialiased/lossy_compressed image. That leaves pixels with even slightly different color uncolored (borders) creating artifacts. There are 2 easy ways how to remedy it:
match close colors instead of exact
if you got 2 RGB colors
(r0,g0,b0)and(r1,g1,b1)right now (if I see it right) your checking is like this:if ((r0!=r1)&&(g0!=g1)&&(b0!=b1)) colors_does_not_match;You should do instead this:
if (((r0-r1)*(r0-r1))+((g0-g1)*(g0-g1))+((b0-b1)*(b0-b1))>treshold) colors_does_not_match;Where
tresholdis you max allowed distance^2 constant for filling. If too low treshold used the artifacts will remain. If too high treshold is used then the fill can bleed also to simila colors nearby ...If you want to have something more visually robust then you can compare colors in HSV space.
use enclosed border filling
It is basically the same as flood fill but you recolor all pixel not containing border color instead of only those containing start color. This will fill the area but there will be artifacts in the border (will be a bit tinner) but not as visually unpleasing as your current approach.
I sometimes use color homogenity fill
This one is good for editing photographs where the colors are shaded due to lighting or whatever. So I fill colors like in flood fill but the color match is considered if the color is not too far from start position by big treshold and not to far from last filled position with small treshold at the same time. This way I usually repair sky artifacts in stitched photos by recoloring to common color and blur the area out with some spray tool gradient patterns...
[Edit1] C++ examples
It uses VCL encapsulated GDI bitmap so rewrite the image access to your style. Also you can ignore the window stuff (I left it only to show how to use this...). I implemented both methods #1,#2 so choose which you want. Your borders are not sharp so the treshold is quite big (223^2) making the #2 option unstable. The static variables are only to ease up heap stack trashing so if you want to multithread this you need to remove it ...
//---------------------------------------------------------------------------
// variables
//---------------------------------------------------------------------------
Graphics::TBitmap *bmp=NULL; // your image
union color { DWORD dd; BYTE db[4]; }; // direct RGB channel access
DWORD **pixel=NULL; // direct 32bit pixel access
int xs=0,ys=0; // image resolution
int mx=0,my=0; // mouse position
int treshold=50000; // color match treshold
//---------------------------------------------------------------------------
// Flood fill
//---------------------------------------------------------------------------
DWORD _floodfill_col_fill; // temp storage to ease up recursion heap/stack trashing
DWORD _floodfill_col_start; // temp storage to ease up recursion heap/stack trashing
void _floodfill(int x,int y) // recursive subfunction do not call this directly
{
// variables
static color c;
static int r,g,b;
// color match
c.dd=pixel[y][x]&0x00FFFFFF; // mask out alpha channel just to be sure
if (_floodfill_col_fill==c.dd) return; // ignore already filled parts (exact match)
r=c.db[0]; // r0,g0,b0
g=c.db[1];
b=c.db[2];
c.dd=_floodfill_col_start;
r-=c.db[0]; r*=r; // (r0-r1)^2,(g0-g1)^2,(b0-b1)^2
g-=c.db[1]; g*=g;
b-=c.db[2]; b*=b;
if (r+g+b>treshold) return;
// recolor
pixel[y][x]=_floodfill_col_fill;
// 4 neighboars recursion
if (x> 0) _floodfill(x-1,y);
if (x<xs-1) _floodfill(x+1,y);
if (y> 0) _floodfill(x,y-1);
if (y<ys-1) _floodfill(x,y+1);
}
void floodfill(int x,int y,DWORD col) // This is the main call for flood fill (x,y) start position and col is fill color
{
// init variables
_floodfill_col_start=pixel[y][x]&0x00FFFFFF;
_floodfill_col_fill =col &0x00FFFFFF;
// sanity check
color c;
int r,g,b;
c.dd=_floodfill_col_fill;
r=c.db[0];
g=c.db[1];
b=c.db[2];
c.dd=_floodfill_col_start;
r-=c.db[0]; r*=r;
g-=c.db[1]; g*=g;
b-=c.db[2]; b*=b;
if (r+g+b<=treshold) return;
// fill
_floodfill(x,y);
}
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
// Border fill
//---------------------------------------------------------------------------
DWORD _borderfill_col_fill; // temp storage to ease up recursion heap/stack trashing
DWORD _borderfill_col_border; // temp storage to ease up recursion heap/stack trashing
void _borderfill(int x,int y) // recursive subfunction do not call this directly
{
// variables
static color c;
static int r,g,b;
// color match
c.dd=pixel[y][x]&0x00FFFFFF; // mask out alpha channel just to be sure
if (_borderfill_col_fill==c.dd) return; // ignore already filled parts (exact match)
r=c.db[0]; // r0,g0,b0
g=c.db[1];
b=c.db[2];
c.dd=_borderfill_col_border;
r-=c.db[0]; r*=r; // (r0-r1)^2,(g0-g1)^2,(b0-b1)^2
g-=c.db[1]; g*=g;
b-=c.db[2]; b*=b;
if (r+g+b<=treshold) return;
// recolor
pixel[y][x]=_borderfill_col_fill;
// 4 neighboars recursion
if (x> 0) _borderfill(x-1,y);
if (x<xs-1) _borderfill(x+1,y);
if (y> 0) _borderfill(x,y-1);
if (y<ys-1) _borderfill(x,y+1);
}
void borderfill(int x,int y,DWORD col_fill,DWORD col_border) // This is the main call for border fill (x,y) start position then fill and border colors
{
// init variables
_borderfill_col_fill =col_fill &0x00FFFFFF;
_borderfill_col_border=col_border&0x00FFFFFF;
// sanity check
color c;
int r,g,b;
c.dd=_borderfill_col_fill;
r=c.db[0];
g=c.db[1];
b=c.db[2];
c.dd=_borderfill_col_border;
r-=c.db[0]; r*=r;
g-=c.db[1]; g*=g;
b-=c.db[2]; b*=b;
if (r+g+b<=treshold) return;
// fill
_borderfill(x,y);
}
//---------------------------------------------------------------------------
// Window code
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner):TForm(Owner)
{
// [init event]
// input image
bmp=new Graphics::TBitmap; // VCL encapsulated GDI bitmap rewrite/use to whatever you got instead
bmp->LoadFromFile("test.bmp"); // cropped part of your image
bmp->HandleType=bmDIB; // allow direct pixel access
bmp->PixelFormat=pf32bit; // set 32bit pixels for easy addressing
xs=bmp->Width; // get the image size
ys=bmp->Height;
ClientWidth=xs; // just resize my App window to match image size
ClientHeight=ys;
// direct pixel access
pixel = new DWORD*[ys]; // buffer for pointers to all lines of image
for (int y=0;y<ys;y++) // store the pointers to avoid slow GDI/WinAPI calls latter
pixel[y]=(DWORD*)bmp->ScanLine[y];
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormDestroy(TObject *Sender)
{
// [exit event]
delete bmp;
delete pixel;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormPaint(TObject *Sender)
{
// [on paint event]
Canvas->Draw(0,0,bmp);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormClick(TObject *Sender)
{
// [on mouse click event]
floodfill(mx,my,0x00FF0000);
// borderfill(mx,my,0x00FF0000,0x00000000);
Paint(); // shedule repaint event
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormMouseMove(TObject *Sender, TShiftState Shift, int X,int Y)
{
// [on mouse move event]
mx=X; my=Y; // store actual mouse position
}
//---------------------------------------------------------------------------
And gfx result:
[Edit2] iterative segmented flood fill
The problem with standard recursive flood fill is that it is potentially dangerous and often leads to Stack Overflows for larger or complicated fills (for example try a spiral with many screws ...) not to mention it is usually slow. The amount of memory needed for flood fill is a around multiple of filled pixels count (so take all of the variables and operands you use and multiply by image size in pixels and soon you hit huge numbers).
To avoid that you can limit the recursion layers a lot by using line segments instead of pixels. That will speed up everything and limit memory usage a lot. Also this approach can be done iteratively which is better in this case so the algorithm is like this:
have a list of line segments
seg[]I chose horizontal lines so each segment has
x0,x1,yand some flag variabledonefor later use. From start the list is empty.add new segment from filling start position
x,ySo just scan all the pixels before and after
x,yhorizontally to cover all consequent start colors (col0) to the leftx0and rightx1and add new segment to the list with flagdone=0.loop all segments with
done=0Set its
done=1and scan all pixels neighboring itx=<x0,x1>andy={y-1,y+1}if found try to add new segment (just as in #2) but before adding it test all other segments for overlaps. If any overlapping segments are found enlarge it with newly found segment and set itsdone=0otherwise add the new segment. This way the segment count will not be too high.loop #3 while any changes has been made
To speed up this you can use index tables
idx[][]that will hold all the indexes of segments at specificycoordinate. I set/use it sosegment[idx[y][?]].y=yloop all the segments and recolor pixels
Here the C++ code of my for this:
//---------------------------------------------------------------------------
// variables
//---------------------------------------------------------------------------
Graphics::TBitmap *bmp=NULL; // your image
union color { DWORD dd; BYTE db[4]; }; // direct RGB channel access
DWORD **pixel=NULL; // direct 32bit pixel access
int xs=0,ys=0; // image resolution
int mx=0,my=0; // mouse position
int treshold=50000; // color match treshold
//---------------------------------------------------------------------------
// Color compare with treshold
//---------------------------------------------------------------------------
bool color_equal(DWORD c0,DWORD c1)
{
static color c;
static int r,g,b;
c.dd=c0&0x00FFFFFF; // mask out alpha channel just to be sure
r=c.db[0]; // r0,g0,b0
g=c.db[1];
b=c.db[2];
c.dd=c1&0x00FFFFFF;
r-=c.db[0]; r*=r; // (r0-r1)^2,(g0-g1)^2,(b0-b1)^2
g-=c.db[1]; g*=g;
b-=c.db[2]; b*=b;
return (r+g+b<=treshold);
}
//---------------------------------------------------------------------------
bool color_nonequal(DWORD c0,DWORD c1)
{
static color c;
static int r,g,b;
c.dd=c0&0x00FFFFFF; // mask out alpha channel just to be sure
r=c.db[0]; // r0,g0,b0
g=c.db[1];
b=c.db[2];
c.dd=c1&0x00FFFFFF;
r-=c.db[0]; r*=r; // (r0-r1)^2,(g0-g1)^2,(b0-b1)^2
g-=c.db[1]; g*=g;
b-=c.db[2]; b*=b;
return (r+g+b>treshold);
}
//---------------------------------------------------------------------------
// Flood fill segmented by lines
//---------------------------------------------------------------------------
struct _segment
{
int x0,x1,y;
int done;
_segment(){}; _segment(_segment& a){ *this=a; }; ~_segment(){}; _segment* operator = (const _segment *a) { *this=*a; return this; }; /*_segment* operator = (const _segment &a) { ...copy... return this; };*/
};
void floodfill_segmented(int x,int y,DWORD col) // This is the main call for flood fill (x,y) start position and col is fill color
{
// init variables
int i,j,k,e,ee,x0,x1;
_segment s,*p;
List<_segment> seg; // H-line segments
List< List<int> > idx; // index table seg[idx[y]].y=y to speed up searches
DWORD col0=pixel[y][x]&0x00FFFFFF;
DWORD col1=col &0x00FFFFFF;
// sanity check
if (color_equal(col0,col1)) return;
// prepare segment table and macros
seg.allocate(ys<<3); seg.num=0;
idx.allocate(ys ); idx.num=ys; for (i=0;i<ys;i++) idx.dat[i].num=0;
// add new segment at (x,y)
// scan the line to enlarge it as much as can
// merge with already added segment instead of adding new one if they overlap
// ee=1 if change has been made
#define _seg_add \
{ \
s.x0=x; s.x1=x; s.y=y; s.done=0; \
for (x=s.x0;x>=0;x--) if (color_equal(col0,pixel[y][x])) s.x0=x; else break; \
for (x=s.x1;x<xs;x++) if (color_equal(col0,pixel[y][x])) s.x1=x; else break; \
for (ee=0,k=0;k<idx.dat[s.y].num;k++) \
{ \
j=idx.dat[s.y].dat[k]; p=seg.dat+j; \
if ((p->x0>=s.x0)&&(p->x0<=s.x1)) ee=1; \
if ((p->x1>=s.x0)&&(p->x1<=s.x1)) ee=1; \
if ((p->x0<=s.x0)&&(p->x1>=s.x0)) ee=1; \
if ((p->x0<=s.x1)&&(p->x1>=s.x1)) ee=1; \
if (ee) \
{ \
if (p->x0>s.x0) { p->done=0; p->x0=s.x0; } \
if (p->x1<s.x1) { p->done=0; p->x1=s.x1; } \
s=*p; \
break; \
} \
} \
if (ee) ee=p->done; else { idx.dat[s.y].add(seg.num); seg.add(s); } \
}
// first segment;
_seg_add;
for (e=1;e;)
{
// add new adjacent segments
for (e=0,p=seg.dat,i=0;i<seg.num;i++,p++)
if (!p->done)
{
p->done=1;
y=p->y-1; if (y>=0) for (x=p->x0;x<=p->x1;x++) if (color_equal(col0,pixel[y][x])) { _seg_add; e|=!ee; x=s.x1; p=seg.dat+i; }
y=p->y+1; if (y<ys) for (x=p->x0;x<=p->x1;x++) if (color_equal(col0,pixel[y][x])) { _seg_add; e|=!ee; x=s.x1; p=seg.dat+i; }
}
}
#undef seg_add
// recolor
for (p=seg.dat,i=0;i<seg.num;i++,p++)
for (x=p->x0,y=p->y;x<=p->x1;x++)
pixel[y][x]=col;
}
//---------------------------------------------------------------------------
The color_equal just compares colors with tresholds (and also it should be a macro instead of a function to gain more speed).
I also use mine dynamic list template so:
List<double> xxx;is the same asdouble xxx[];xxx.add(5);adds5to end of the listxxx[7]access array element (safe)xxx.dat[7]access array element (unsafe but fast direct access)xxx.numis the actual used size of the arrayxxx.reset()clears the array and set xxx.num=0xxx.allocate(100)preallocate space for100items
Here something to compare to:
On the left is source image 720x720 pixels spiral and on the right is the result after filling from the bottom left side It took 40 ms Code without using idx[] and using array range checks took around 440 ms instead. If I use standard flood fill it crashes with stack overflow after few seconds. On the other hand for smaller fills the standard recursive flood fill is usually faster then this.
这篇关于当我着色时，绘制算法在边缘留下白色像素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！