[net.micro] Graphics Space Fill?

KSPROUL@rutgers.arpa (04/10/83)

Does anybody know how to do graphics fill (i.e. given a point that
is inside of a shape, fill the shape)

I have seen this done on lots of computers and want to write one myself
Any information would be helpful

Keith Sproul
Ksproul@Rutgers
-------

SHULMAN@rutgers.arpa (04/10/83)

From:  Jeffrey Shulman <SHULMAN@rutgers.arpa>


	It is trivial to do recursively:


	PROCEDURE FILL(x,y:INTEGER; color,border:COLOR);

	   BEGIN
	     IF color_of_pixel(x,y) <> border THEN
		BEGIN
		   set_pixel_to_color(x,y,color);
		   IF color_of_pixel(x-1,y) <> color THEN
			FILL(x-1,y,color,border);
		   IF color_of_pixel(x,y-1) <> color THEN
			FILL(x,y-1,color,border);
		   IF color_of_pixel(x+1,y) <> color THEN
			FILL(x+1,y,color,border);
		   IF color_of_pixel(x,y+1) <> color THEN
			FILL(x,y+1,color,border);
		END;
	   END;


The 'border' is the color of the border and 'color' is the color you
wish to fill.  The first call to FILL must be a point inside the area
you wish to fill.

The 'IF' statements are added for efficiency, you can remove them but
you can wind up 'filling' already filled pixels' Also, there is one
case that this algorithm won't fill.  Can you figure it out?

Hope this helps.

						Jeff

-------

dap1 (04/14/83)

#R:sri-arpa:-87100:ihlpf:23200003:  0:1141
ihlpf!dap1    Apr 13 12:59:00 1983

The recursive method will work (although it seems that the "if" statements are
mandatory, not optional for efficiency's sake since otherwise you would end up
in an infinite loop repainting already painted pixels) but there is a better way
which is the way that DOS 1.1 and 1.0 handles it (based on the order in which
the pixels are filled in).  It is described in a book by Theo Pavlidis called
"Algorithms for Graphics and Image Processing".  I won't go into details but it
amounts to a row fill of pixels while keeping track of the rows immediately
above and below the current row.  Whenever there an "arm" "branches" up or down
that arm is placed on a stack and processed later.  This should be much more
efficient in both time and space that the recursive call method.  There is also
an article in an old SIGGRAPH Proceedings called "How to Fill in a Coloring 
Book" or some such.  It describes the same method in a little easier to
understand terms.

                                                   Darrell Plank
                                                   BTL-IH
                                                   ihlpf!dap1