A bug in the stroke algorithm

When we redesigned the stroke algorithms we added connections using line crossing calculations, but we always worked with open paths. But what happens if the path is closed, or if it intersects itself?

Javascript Editor

The situation is worse, if there ar multiple subpaths, we even get a javascript error, because a subpath can be empty.

Javascript Editor

If we want stroke letters, many paths will be composite.

First we need to accept in stroke that a subpath may be empty and we ignore it.

Second we need to adress the ovoerload. There are algorithms that create the union of vector paths, implicating crossing each line with each other, but we do not need them. At this stage, we are already at the raster image, so we just can stroke each segment individually. If we set a pixel black twice, it will be the same black. So this is what we do. We convert the path in two line segments for each line. We scanFill each segment individually. Then we scanFill the connecting polygon.

Javascript Editor

operators.closepath = function(context) {
    if (!context.graphics.current.length) {
       context.stack.push(new rpnError("nocurrentpoint"));
    } else if (!context.graphics.path.length) {
       context.stack.push(new rpnError("nocurrentpath"));
    } else {
      if (context.graphics.path.length) { 
         const subpath = context.graphics.path.pop();
         const x0 = subpath[0][1];
         const y0 = subpath[0][2];
         subpath.push( [ "L",context.graphics.current[0], context.graphics.current[1], x0, y0 ]);
         context.graphics.path.push(subpath);
         context.graphics.current = [ x0, y0 ];      }
    }

return context;
};

operators.rlineto = function(context) {
    const [y, x] = context.pop("number","number");
    if (!y) return context;
    if (!context.graphics.current.length) {
       context.stack.push(new rpnError("nocurrentpoint"));
    } else if (!context.graphics.path.length) {
       context.stack.push(new rpnError("nocurrentpath"));
    } else {
       const subpath = context.graphics.path.pop();
       const [xct, yct] = context.itransform(context.graphics.current[0], context.graphics.current[1]); 
       const [xt, yt] = context.transform(xct + x.value, yct + y.value); 
       subpath.push([ "L", context.graphics.current[0], context.graphics.current[1], xt, yt ]);
       context.graphics.path.push(subpath); 
       context.graphics.current = [ xt, yt];       
    }
    return context;
};

Javascript Editor

operators.stroke2 = function(context) {
   
   const w = context.graphics.linewidth / 2;
   const ad = 3.1415926535 / 2;
   if (!w) {
       return context;
   }
   for (var subpath of context.graphics.path) {
       var subflatpath = [];
       for (var line of subpath) {
           if (line[0] == "C") {
               const lines = bezier(line,-1);
               for (var elem of lines) {
                   subflatpath.push(elem)
               }
           } else {
               subflatpath.push(line);
           }
       }
       var olda = [];
       var oldb = [];
       if (!subflatpath.length) continue;
       if (subflatpath[0][1] == subflatpath[subflatpath.length-1][3] &&
       subflatpath[0][2] == subflatpath[subflatpath.length-1][4])
       subflatpath.push(subflatpath[0])
       for (var line of subflatpath) {
           const [type, x0, y0, x1, y1] = line;
           const a = Math.atan2(y1 - y0, x1 - x0);
           const x0a = x0 + Math.cos(a - ad) * w;
           const y0a = y0 + Math.sin(a - ad) * w;
           const x1a = x1 + Math.cos(a - ad) * w;
           const y1a = y1 + Math.sin(a - ad) * w;
           const x0b = x0 + Math.cos(a + ad) * w;
           const y0b = y0 + Math.sin(a + ad) * w;
           const x1b = x1 + Math.cos(a + ad) * w;
           const y1b = y1 + Math.sin(a + ad) * w;
           context.data = scanFill([ ["L",x0a, y0a, x1a, y1a], ["L",x0a, y0a, x0b, y0b],["L", x0b, y0b, x1b, y1b], ["L",x1a, y1a, x1b, y1b]], context.width, context.height, context.graphics.color, context.data)
           if (olda.length) {
               const [xa, ya] = lineIntersection(olda[1],olda[2],olda[3],olda[4],x0a, y0a, x1a, y1a);
               const [xb, yb] = lineIntersection(oldb[1],oldb[2],oldb[3],oldb[4],x0b, y0b, x1b, y1b);
               context.data = scanFill([ ["L",olda[3],olda[4], xa, ya], ["L",xa, ya, x0a, y0a],["L", x0a, y0a, x0b, y0b], ["L",x0b, y0b, xb, yb],["L",xb, yb, oldb[3], oldb[4]],["L", oldb[3], oldb[4], olda[3], olda[4]]], context.width, context.height, context.graphics.color, context.data);
           }
           olda = ["L", x0a, y0a, x1a, y1a];
           oldb = ["L", x0b, y0b, x1b, y1b];
       }
   }         
   
    context.graphics.path = [];
    context.graphics.current = [];

return context;
};

Javascript Editor

However, we still have rounding error as you can see with at lower left corner of the square. We never round, but we use trigonometric functions. In the beginning of stroke, I defined pi as 3.1415926536, the digits yi know by heart since school. Ten digits is not exact enough. We replace it with the Javascript constant Math.PI. We also must escape lineIntersection if the lines are parallel.

Javascript Editor

lineIntersection = function(x1, y1, x2, y2, x3, y3, x4, y4) {
    // https://en.wikipedia.org/wiki/Line–line_intersection
   const denom = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
   if (!denom) return ([null,null]);
   const nom1 = x1 * y2 - y1 * x2; 
   const nom2 = x3 * y4 - y3 * x4; 
   const x = (nom1 * (x3 - x4) - nom2 * (x1 - x2)) / denom;
   const y = (nom1 * (y3 - y4) - nom2 * (y1 - y2)) / denom;
   return [x, y];
}

operators.stroke3 = function(context) {
   
   const w = context.graphics.linewidth / 2;
   const ad = Math.PI / 2;
   if (!w) {
       return context;
   }
   for (var subpath of context.graphics.path) {
       var subflatpath = [];
       for (var line of subpath) {
           if (line[0] == "C") {
               const lines = bezier(line,-1);
               for (var elem of lines) {
                   subflatpath.push(elem)
               }
           } else {
               subflatpath.push(line);
           }
       }
       var olda = [];
       var oldb = [];
       if (!subflatpath.length) continue;
       if (subflatpath[0][1] == subflatpath[subflatpath.length-1][3] &&
       subflatpath[0][2] == subflatpath[subflatpath.length-1][4])
       subflatpath.push(subflatpath[0])
       for (var line of subflatpath) {
           const [type, x0, y0, x1, y1] = line;
           const a = Math.atan2(y1 - y0, x1 - x0);
           const x0a = x0 + Math.cos(a - ad) * w;
           const y0a = y0 + Math.sin(a - ad) * w;
           const x1a = x1 + Math.cos(a - ad) * w;
           const y1a = y1 + Math.sin(a - ad) * w;
           const x0b = x0 + Math.cos(a + ad) * w;
           const y0b = y0 + Math.sin(a + ad) * w;
           const x1b = x1 + Math.cos(a + ad) * w;
           const y1b = y1 + Math.sin(a + ad) * w;
           context.data = scanFill([ ["L",x0a, y0a, x1a, y1a], ["L",x0a, y0a, x0b, y0b],["L", x0b, y0b, x1b, y1b], ["L",x1a, y1a, x1b, y1b]], context.width, context.height, context.graphics.color, context.data)
           if (olda.length) {
               const [xa, ya] = lineIntersection(olda[1],olda[2],olda[3],olda[4],x0a, y0a, x1a, y1a);
               const [xb, yb] = lineIntersection(oldb[1],oldb[2],oldb[3],oldb[4],x0b, y0b, x1b, y1b);
               if (xa !== null && xb !== null) {
                   context.data = scanFill([ ["L",olda[3],olda[4], xa, ya], ["L",xa, ya, x0a, y0a],["L", x0a, y0a, x0b, y0b], ["L",x0b, y0b, xb, yb],["L",xb, yb, oldb[3], oldb[4]],["L", oldb[3], oldb[4], olda[3], olda[4]]], context.width, context.height, context.graphics.color, context.data);
               }
           }
           olda = ["L", x0a, y0a, x1a, y1a];
           oldb = ["L", x0b, y0b, x1b, y1b];
       }
   }         
   
    context.graphics.path = [];
    context.graphics.current = [];

return context;
};

Javascript Editor

The current version of the code has 1845 lines.
ps20240821.js

My Journey to PostScript