The current version of draw-something uses PostScript’s fill operator to fill the shape with flat colour. Problem solved.
Or is it? Calling fill feels like cheating. draw-something should be colouring in, not flood filling. They are conceptually different. And they have different visual qualities. draw-something’s drawing is based on my drawing, so draw-something’s colouring in should be based on my colouring in.
The existing fill algorithm that I like is called the boundary fill algorithm. It’s a simple recursive fill. I think I could convert it from a bitmap-based system to a vector-based system using a turtle (like draw-something’s pen).
Something like (C pseudocode):
int step = 10; // Brush width
public void boundaryFill(Polyline outline, int fromX, int toX, int y, Polyline & fillOutline)
if (! outline.intersects(fromX, y, toX, y) && // Keep inside shape
! fillOutline.intersects(fromX, y, toX, y)) // Don’t re-colour. Will get slower 🙁
fillOutline.addLine(fromX, y, toX, y);
boundaryFill(toX, y, toX + step, y); // Try next along
boundaryFill(fromX, toX – step, y); // Try previous
boundaryFill(fromX, y + yStep, toX, y + step); // Try next up
boundaryFill(fromX, y – yStep, toX, y – step); // Try next down
But there are some things the system must do that a boundary fill won’t:
• If a section of the figure is very thin, follow it along its edge rather than scribbling left and right.
• If a section of the figure is thicker than the scribble width, break it into a number of columns and rows. Fill these diagonally top left to bottom right.