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.

Javascript

operators.fill = function(context) {
   const crossings = []; 
   for (var subpath of context.graphics.path) {
       for (var line of subpath) {
          const type = line[0]; // we will have other types
          var x0 = line[1];
          var y0 = line[2];
          var x1 = line[3];
          var y1 = line[4];
          const dx = x1 - x0;
          const dy = y1 - y0;
          if (dy) {
              if (y1 < y0) { 
                  [y0, y1] = [y1, y0];
                  [x0, x1] = [x1, x0];
              }
              const ex = dx / dy;
              var x = x0;
              for(var y = y0; y < y1; y++) {
                  if (y >= 0 && y < context.height) {
                     if (! crossings[y] ) crossings[y] = [];
                     crossings[y].push(x);
                  }
                  x += ex;
              }
          }
       }
    } 
    for (var y in crossings) {
       const arr = crossings[y];
       arr.sort(function (a, b) { return a - b }); 
       for (var i = 0; i < arr.length - 1; i += 2) {
          var xstart = Math.round(arr[i]);
          var xend = Math.round(arr[i + 1]);
          var offset = ((context.height - 1 - y) * context.width + xstart) * 4;
          for (var j = xstart; j < xend; j++) {
                 
              for (var c = 0; c < 4; c++) {
                    context.data[offset + c] = context.graphics.color[c];
              }
              offset += 4;
          }
       } 
    }
    context.graphics.path = [];
    context.graphics.current = [];

return context; 
};

We try to fill our drawings from last chapter

Javascript Editor

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

Javascript Editor

We can draw complex things like letters

Javascript Editor

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

My Journey to PostScript