WorstForum WorstForum - 5 months ago 4x
Javascript Question

How can I fill enclosed shapes in a line?

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

a squiggly line, which loops over itself in some places to create enclosed circle and balloon shapes

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

the enclosed shapes are filled in with red

However when I fill this it simply turns into:

the beginning and end of the line have been invisibly connected, and the whole area filled in, enclosed shapes included

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");
// code to stroke path of mouse cursor;

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



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



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) {
    // any intersection?
    ip = intersection(points[i], points[i+1], points[i+2], points[i+3],
                      points[y], points[y+1], points[y+2], points[y+3]);
    // if hit, 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";

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

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>