[Gimp-developer] Polymorphic floodfill boundary test

[Torbjörn Rathsman <tormann telia com>]

I do not know how the floodfill decide if it comes to a boundary or not, but
I guess that it always sampels information from the point where I clicked.
However, sometimes another test would be more useful. This piece of code is
polymorphic in boundary check:

class Graymap
	{
	public:
		Graymap(unsigned int width,unsigned int height)
			{
			data=new unsigned char[width*height];
			memset(data,0,width*height);
			p_matrix=new unsigned char*[height];
			for(unsigned int i=0;i<height;i++)
				{
				p_matrix[i]=data+width*i;
				}
			}

		unsigned char& operator()(unsigned int x,unsigned int y)
			{
			return p_matrix[y][x];
			}

		~Graymap()
			{
			delete[] p_matrix;
			delete[] data;
			}
	private:
		unsigned char* data;
		unsigned char** p_matrix;

	};

class FloodfillConditionBoundary
	{
	public:
		virtual bool operator()(unsigned int x,unsigned int y)=0;
	};

struct FloodfillNode
	{
	unsigned int x;
	unsigned int y;
	};

void floodfill(unsigned int x,unsigned int y,const Pixel&
color_current,Image& dest, FloodfillConditionBoundary& boundaryAt)
	{

//	Implementation modified from http://en.wikipedia.org/wiki/Flood_fill

	Graymap dirty(dest.widthGet(),dest.heightGet());

//	1. Set Q to the empty queue.
	std::deque<FloodfillNode> Q;

	FloodfillNode node={x,y};
//	2. Add node to Q.
	Q.push_back(node);
//	3. For each element n in Q:
	while(!Q.empty())
		{
		FloodfillNode n=Q.front();
		Q.pop_front();

	//	3a Set w and e equal to n.
		FloodfillNode w=n;
		FloodfillNode e=n;
		assert(!w.x<dest.widthGet() && !w.y<dest.widthGet());
		if(dirty(w.x,w.y))
			{
			continue;
			}

		while( w.x!=0xffffffff) //3b Go west until we find the western boundary
			{
			if( boundaryAt(w.x,w.y) )
				{break;}
			dest(w.x,w.y)=color_current;
			dirty(w.x,w.y)=1;
			if(w.y-1!=0xffffffff)
				{
			//	3b1 If we have not been at the pixel one line below before
			//	And this pixel does not lie on the boundary
				if(!dirty(w.x,w.y-1) && !boundaryAt(w.x,w.y-1) )
					{Q.push_back((FloodfillNode){w.x,w.y-1});}
				}
			if(w.y+1<dest.heightGet())
				{
			//	3b2 If we have not been at the pixel one line above before
			//	And this pixel does not lie on the boundary
				if(!dirty(w.x,w.y+1) && !boundaryAt(w.x,w.y+1))
					{Q.push_back((FloodfillNode){w.x,w.y+1});}
				}
			w.x--;
			}
		e.x++;
		while(e.x<dest.widthGet()) //3c Go east...
			{
			if(boundaryAt(e.x,e.y))
				{break;}
			dest(e.x,e.y)=color_current;
			dirty(e.x,e.y)=1;
			if(e.y-1!=0xffffffff)
				{
			//	3c1 If we have not been at the pixel one line below before
			//	And this pixel does not lie on the boundary
				if(!dirty(e.x,e.y-1) && !boundaryAt(e.x,e.y-1) )
					{Q.push_back((FloodfillNode){e.x,e.y-1});}
				}
			if(e.y+1<dest.heightGet())
				{
			//	3c2 If we have not been at the pixel one line above before
			//	And this pixel does not lie on the boundary
				if(!dirty(e.x,e.y+1) && !boundaryAt(e.x,e.y+1))
					{Q.push_back((FloodfillNode){e.x,e.y+1});}
				}
			e.x++;
			}
		}
	}

One way to implement FloodfillConditionBoundary besides the traditional one
is to check the magnitude of the gradient vector at current pixel. This
would be useful if one has a picture with a smooth gradient surrounded by a
sharp edge and want to replace the smooth gradient with one solid color. If
I want to add the feature myself, where do I start?