Fast fill routine

This operation is taken for granted nowadays. Quite rightly too, as it is the most common graphics task after plotting points, and drawing lines, rectangles and circles. It will do no harm, however to take a closer look at it.

The general backtracking algorithm or the spreading inkblot method (Lee's algorithm) is too inefficient for this problem: Drawing entire lines (or even filling rectangles) is much faster than plotting their individual points.

The problem may seem ideally suited to recursion- it is not. The subprocesses spawned would be too numerous, the associated overhead too great. It has already been repeated in this site that 'recursion is most helpful at times, but not entirely necessary'. This, then, is as good an opportunity as any to introduce list based processing: A point is removed from a list and processed, possibly adding more points to the list. It is necessary occasionally to scan the list, deleting items if a faster method has already dealt with them. The program ends when the list is empty. Routines are needed to:

Add an item to the list.
Remove an item from the list.
Traverse the list, conditionally removing items already processed by a faster part of the algorithm.

Here is a first attempt at a fill routine:

A point inside the shape to be filled is supplied.
Move as far as possible to the left of the present point, while staying on pixels in the background colour. Repeat towards the right.
Plot the line segment just traced out. For each point (directly) above or below the present line, check if it is in the background colour, then add it to the head of the list.
Scan the list, deleting points already in the fill colour (none will be found in the first run.)
Remove the first point in the list, and repeat the previous steps.
The program ends when the list is empty.

(At the edgepoints of the line segment), it may be useful to include points diagonally above or below the present point (if not contributed already by a neighbouring point) , as marked in the legend below: However, this assumes that the enclosing lines of the shape to be filled have been properly drawn (by using overlapping line segments), or the program is in a lot of trouble. That's why it was written in the first place.

x x

x x

This works, but is a far cry from satisfactory: Most of the points are added to the list, only to be removed later without ever being processed. The faster method of plotting entire lines at a time has already taken care of them. Also, the space taken up for storage is too much: Almost as many points as there are on the screen may need to be kept (for the contrived worst case example at the end of this paragraph.) Using a random number to give precedence to the points below, rather than above, the present line (for each line), halves the space. This is still unacceptably large, though.

worst case

The following improvements are effectively mandatory:

While staying on the background colour, move down from the present point as far as possible.
Trace out and plot the line (directly) above the present line. (Store the endpoints, as they will needed later; the points above and below the line will still be checked afterwards.)
These steps will immensely reduce the number of points entered into the list by the present line. If the algorithm blocks (probably because a local peak has been met) the program proceeds by removing a point from the list. Processing continues by using this point, after repeating the first two steps.
The program ends again when the list is empty.

There is a little way to go yet: Consulting the beginning of the list is faster, but it is likely then that the algorithm will block again soon. The head of the list will probably contain a point near the edge of the shape to be filled. It is much safer to consult the middle of the list, if the latter holds more than two items. In addition, using the endpoint of a line segment as a basis to trace out the line above will fail if the shape is narrowing upwards. Choosing the midpoint of the present line will often be more successful.

Now the algorithm looks complete: Most of the work has been moved out of the list and into the fast portion of the program.

(There may be additional targets than reducing the size of the list. The 'get point colour' function may be expensive. Currently, it is used three times for most pixels. The programmer will wish to reduce that to one time for most pixels, in that condition. If the 'get pixel colour' call is fast, on the other hand, it is much more straightforward to shorten the list.)

The program is in Basic for no particular reason: Modern versions allow for more structured programs than interpreters of days gone by. The program must be compiled, rather than interpreted, if it going to be fast. Translation to another language is also possible, since scant use is made of the more esoteric features to Basic: Certainly, the (get colour of) Point and (draw) Line commands must be replaced by native calls. Points off- screen are assumed to return a value different from the background colour.

There are choices when presenting work: A simple version will barely scratch the surface of the problem, but will be hopefully more understandable. An advanced version, on the other hand performs more satisfactorily, but most visitors will probably not read it. The plain fill routine is already in place. Eventually, the more sophisticated version appears, too. After the main ideas have been grasped, it is easier to concentrate on optimisation. It was in working order, (otherwise it wouldn't get a section) but not quite in the state I want it when presenting work to others.

Digital faultfinding in sequential circuits