# The scanfill algorithm

Every child learns how to color a drawing. They get coloring books with black and white drawings and fill them with color pencils. Primary school teachers have spent half of their lives explaining children not to color outside the lines. *Color outside the lines* is even a common english expression to behave in creative or in an unconventional way, to break the rules, i learnt from a recent interview with Margaret Atwood.

Color a drawing is much more complicated for computers than for children. Children can color, because they have a notion what is inside and what is outside a form, computers haven't.

There are various algorithms that can give computers a notion of inside and the one we will use because it is rather simple, but effective, is the scanfill algorithm.

We start at the border of a page we consider outside. A point is considered inside if it surrounded by borders, but only once in each direction.

So we can count. Each time we pass a border we flip outside and inside. If all forms are closed, we have a guarantee to be outside again at the end.

So this is what we do with our fill operator. We take each line segment and throw away the horizontal lines. We may have to turn it, so that it is always bottom up (remember: PostScript origin is bottom left). Then we calculate for each integer y value of the line the corresponding x value and add it to the corresponding array of y value.

When we have done all lines, we got through the y arrays, sort them and draw horizontal lines for each inside segment.

We try to fill our drawings from last chapter

This looks like an error but isn't. If paths overlap, they create holes. This allows to draw letters like A, D or Put.

We can draw complex things like letters

We can no fill any polygon. The next chapters tells us not only to draw lines, but also curves.

The codebase is now 1174 lines ps20240718.js