How can I fill enclosed shapes in a line?

Question

I've used a html canvas to create this line:

I want the loops in the line filled, so that it looks like this:

However when I fill this it simply turns into:

I did try using paths, it was the exact same result, just with a line connecting the start to finish.

Abstraction of code:

var canvas = $("canvas")[0], ctx=canvas.getContext("2d");
ctx.moveto(0,0);
// code to stroke path of mouse cursor;

How can I get my desired result and fill in just the enclosed shapes in the line?

Answer 1

Updated

The problem is as Brett points out that fill() will implicitly close the path. There is nothing we can do about this using the API so we need to use a manual approach to fill the loops as separate closed paths.

Finding intersections

This algorithm does the following (have not checked for cases where these loops might overlap, but it should get you started). It can also be rewritten to do this in real-time while moving the mouse.

• We can iterate over all segments in the path. Compare each segment to all the others, but from current + two as the end-point of current segment would otherwise self-intersect with start point of next segment.
• If an intersection is found:
  • Build a path from the intersection point then add points using the segments between first and last intersecting line

Example

var points = [49,40,49,41,49,42,49,43,49,45,49,48,49,50,49,53,49,56,49,59,49,63,49,67,49,72,50,77,51,82,53,88,53,91,55,96,58,99,60,104,62,106,64,109,65,113,68,116,70,118,72,120,74,121,76,124,78,125,81,126,87,129,92,130,98,133,104,134,109,135,113,135,117,135,121,135,127,135,131,135,135,135,141,132,148,128,153,126,159,122,161,120,164,118,164,116,165,112,165,110,165,107,165,105,165,104,165,101,165,100,164,96,163,94,162,93,160,91,159,90,158,88,157,88,156,88,154,88,151,88,147,88,141,90,135,92,130,94,126,96,121,99,118,101,114,104,111,108,108,110,107,113,104,117,103,120,100,125,99,129,96,135,95,139,95,144,95,148,95,152,95,155,95,158,96,162,97,166,99,170,102,173,106,177,109,181,111,182,113,184,115,185,117,186,119,186,121,186,124,186,127,186,132,185,135,183,141,179,146,175,152,172,158,168,165,165,172,162,178,159,185,158,191,157,195,156,199,156,202,156,206,156,209,156,212,157,216,160,220,163,221,168,224,170,224,173,225,177,227,182,228,186,229,192,229,197,230,203,230,208,230,212,230,219,230,225,230,230,228,236,226,240,221,246,217,251,214,255,210,257,204,260,199,260,194,261,189,261,184,261,181,261,177,261,175,261,173,260,173,256,171,252,170,245,170,237,169,231,168,226,168,221,168,218,168,215,168,212,168,211,169,207,172,205,175,201,180,199,187,198,194,196,201,194,208,194,214,194,221,194,225,194,230,195,235,196,240,199,245,202,247,204,251,207,253,210,254,214,255,216,259,223,263,229,266,235,270,241,273,245,277,253,279,257,283,262,287,269,292,274,297,280,302,285,308,290,314,294,321,295,327,296,336,298,343,298,352,298,359,298,367,292,374,286,379,278,381,269,381,262,381,254,381,246,381,241,379,232,377,229,372,224,369,221,364,219,361,219,355,218,347,218,339,218,330,218,320,221,310,228,300,235,290,242,282,249,276,257,271,263,269,269,267,276,266,281,266,287,266,291,267,297,272,305,279,312,286,319,296,327,305,332,316,338,325,341,333,344,340,348,342,348,344,349,345,349,345,350,346,351,347,353,347,355,347,356,347,358,347,361,347,363,347,366,347,370,347,374,344,379,343,384,342,393,339,400,335,406,331,414,323,421,317,426,310,430,302,435,295,437],
    ctx = c.getContext("2d"),
    i, y, ip, t, l = points.length;

// compare each segments
for(i = 0; i < points.length - 4; i += 2) {
  for(y = i + 4; y < points.length - 2; y += 2) {
    
    ip = intersection(points[i], points[i+1], points[i+2], points[i+3],
                      points[y], points[y+1], points[y+2], points[y+3]);
    
    // any intersction? create a sub-path with segments between the intersecting lines
    if (ip) {
      ctx.moveTo(ip.x, ip.y);
      for(t = i + 2; t < y; t += 2) ctx.lineTo(points[t], points[t+1]);
    }
  } 
}

// fill all sub-paths at once
ctx.fillStyle = "red";
ctx.fill();

// stroke path itself
ctx.beginPath();
ctx.moveTo(points[0], points[1]);
for(i = 0; i < l; i += 2) ctx.lineTo(points[i], points[i+1]);
ctx.stroke();

function intersection(p0x, p0y, p1x, p1y, p2x, p2y, p3x, p3y) {

  var d1x = p1x - p0x, d1y = p1y - p0y,
      d2x = p3x - p2x, d2y = p3y - p2y,
      d = d1x * d2y - d2x * d1y,
      px, py, s, t;

    if (d) {
      px = p0x - p2x;
      py = p0y - p2y;
      s = (d1x * py - d1y * px) / d;
      if (s >= 0 && s <= 1) {
        t = (d2x * py - d2y * px) / d;
        if (t >= 0 && t <= 1) return {x: p0x + (t * d1x), y: p0y + (t * d1y)};
      }
    }
    return null
}

<canvas id=c width=500 height=500></canvas>

Answer 2

The problem is the fill() method is closing the path, basically drawing a line from the start point to the end point. The result is the entire path is filled as you've seen.

One possible solution, though it will be tough with the seemingly random line you have, is to return the pointer to a position where the fill() won't cause unwanted fills. The example below demonstrates this. After drawing the line I simply return the pointer to a position where the closePath() doesn't cause any closed regions to fill.

The canvas on the right has the final point moved to a neutral position to the fill() behaves as desired.

var canvas = document.getElementById('myCanvas');
var context = canvas.getContext('2d');

context.beginPath();
context.moveTo(100, 20);
context.lineTo(100, 120);
context.lineTo(150, 120);
context.lineTo(150, 70);
context.lineTo(50, 70);

context.fill();

context.lineWidth = 2;
context.strokeStyle = 'blue';
context.stroke();

var canvas = document.getElementById('myCanvas2');
var context = canvas.getContext('2d');

context.beginPath();
context.moveTo(100, 20);
context.lineTo(100, 120);
context.lineTo(150, 120);
context.lineTo(150, 70);
context.lineTo(50, 70);

// Go back to a position the line
// won't cause unwanted fills
context.lineTo(100, 70);

context.fill();

context.lineWidth = 2;
context.strokeStyle = 'blue';
context.stroke();

<canvas id="myCanvas" width="250" height="250"></canvas>
<canvas id="myCanvas2" width="250" height="250"></canvas>