Subtracting SVG paths programmatically

Question

I'm trying to find a way to subtract a SVG path from another, similar to an inverse clip mask. I can not use filters because I will need to find the intersection points of the compound path with other paths. Illustrator does this with the 'minus front' pathfinder tool like this:

The path of the red square before subtracting:

<rect class="cls-1" x="0.5" y="0.5" width="184.93" height="178.08"/>

After subtraction:

<polygon class="cls-1" points="112.83 52.55 185.43 52.55 185.43 0.5 0.5 0.5 0.5 178.58 112.83 178.58 112.83 52.55"/>

I need this to work with all types of shapes, including curves. If it matters, the input SVGs will all be transformed into generic paths.

Answer 1

You might use paper.js for this task.
The following example also employs Jarek Foksa's pathData polyfill.

paper.js example

var svg = document.querySelector("#svgSubtract");
// set auto ids for processing
function setAutoIDs(svg) {
  let svgtEls = svg.querySelectorAll(
    "path, polygon, rect, circle, line, text, g"
  );
  svgtEls.forEach(function(el, i) {
    if (!el.getAttribute("id")) {
      el.id = el.nodeName + "-" + i;
    }
  });
}
setAutoIDs(svg);


function shapesToPath(svg) {
  let els = svg.querySelectorAll('rect, circle, polygon');
  els.forEach(function(el, i) {
    let className = el.getAttribute('class');
    let id = el.id;
    let d = el.getAttribute('d');
    let fill = el.getAttribute('fill');
    let pathData = el.getPathData({
      normalize: true
    });
    let pathTmp = document.createElementNS("http://www.w3.org/2000/svg", 'path');
    pathTmp.id = id;
    pathTmp.setAttribute('class', className);
    pathTmp.setAttribute('fill', fill);
    pathTmp.setPathData(pathData);
    svg.insertBefore(pathTmp, el);
    el.remove();

  })
};

shapesToPath(svg);


function subtract(svg) {
  // init paper.js and add mandatory canvas
  canvas = document.createElement('canvas');
  canvas.id = "canvasPaper";
  canvas.setAttribute('style', 'display:none')
  document.body.appendChild(canvas);
  paper.setup("canvasPaper");

  let all = paper.project.importSVG(svg, function(item, i) {
    let items = item.getItems();
    // remove first item not containing path data
    items.shift();
    // get id names for selecting svg elements after processing
    let ids = Object.keys(item._namedChildren);

    if (items.length) {
      let lastEl = items[items.length - 1];
      // subtract paper.js objects
      let subtracted = items[0].subtract(lastEl);
      // convert subtracted paper.js object to svg pathData
      let subtractedData = subtracted
        .exportSVG({
          precision: 3
        })
        .getAttribute("d");
      let svgElFirst = svg.querySelector('#' + ids[0]);
      let svgElLast = svg.querySelector('#' + ids[ids.length - 1]);
      // overwrite original svg path
      svgElFirst.setAttribute("d", subtractedData);
      // delete subtracted svg path
      svgElLast.remove();
    }
  });
}

svg {
  display: inline-block;
  width: 25%;
  border: 1px solid #ccc
}

<script src="https://cdn.jsdelivr.net/npm/path-data-polyfill@1.0.3/path-data-polyfill.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/paper.js/0.12.0/paper-full.min.js"></script>

<p>
  <button type="button" onclick="subtract(svg)">Subtract Path </button>
</p>
<svg id="svgSubtract" viewBox="0 0 100 100">
        <rect class="cls-1" x="0" y="0" width="80" height="80" fill="red" />
        <path d="M87.9,78.7C87.9,84,86,88,82.2,91c-3.8,2.9-8.9,4.4-15.4,4.4c-7,0-12.5-0.9-16.2-2.7v-6.7c2.4,1,5.1,1.8,8,2.4
        c2.9,0.6,5.7,0.9,8.5,0.9c4.6,0,8.1-0.9,10.4-2.6c2.3-1.7,3.5-4.2,3.5-7.3c0-2.1-0.4-3.7-1.2-5.1c-0.8-1.3-2.2-2.5-4.1-3.6
        c-1.9-1.1-4.9-2.4-8.8-3.8c-5.5-2-9.5-4.3-11.8-7c-2.4-2.7-3.6-6.2-3.6-10.6c0-4.6,1.7-8.2,5.2-10.9c3.4-2.7,8-4.1,13.6-4.1
        c5.9,0,11.3,1.1,16.3,3.2l-2.2,6c-4.9-2.1-9.7-3.1-14.3-3.1c-3.7,0-6.5,0.8-8.6,2.4c-2.1,1.6-3.1,3.8-3.1,6.6
        c0,2.1,0.4,3.7,1.1,5.1c0.8,1.3,2,2.5,3.8,3.6c1.8,1.1,4.6,2.3,8.3,3.6c6.2,2.2,10.5,4.6,12.9,7.1C86.7,71.4,87.9,74.7,87.9,78.7z"
        />
</svg>

Path normalization (using getPathData() polyfill)

We need to convert svg primitives (<rect>, <circle>, <polygon>)
to <path> elements – at least when using paper.js Boolean operations.
This step is not needed for shapes natively created as paper.js objects.

The pathData polyfill provides a method of normalizing svg elements.
This normalization will output a d attribute (for every selected svg child element) containing only a reduced set of cubic path commands (M, C, L, Z) – all based on absolute coordinates.

Example 2 (multiple elements to be subtracted)

const svg = document.querySelector("#svgSubtract");
const btnDownload = document.querySelector("#btnDownload");
const decimals = 1;
// set auto ids for processing
function setAutoIDs(svg) {
  let svgtEls = svg.querySelectorAll(
    "path, polygon, rect, circle, line, text, g"
  );
  svgtEls.forEach(function(el, i) {
    if (!el.getAttribute("id")) {
      el.id = el.nodeName + "-" + i;
    }
  });
}
setAutoIDs(svg);


function shapesToPathMerged(svg) {
  let els = svg.querySelectorAll('path, rect, circle, polygon, ellipse ');
  let pathsCombinedData = '';
  let className = els[1].getAttribute('class');
  let id = els[1].id;
  let d = els[1].getAttribute('d');
  let fill = els[1].getAttribute('fill');

  els.forEach(function(el, i) {
    let pathData = el.getPathData({
      normalize: true
    });
    if (i == 0 && el.nodeName.toLowerCase() != 'path') {
      let firstTmp = document.createElementNS("http://www.w3.org/2000/svg", 'path');
      let firstClassName = els[1].getAttribute('class');
      let firstId = el.id;
      let firstFill = el.getAttribute('fill');
      firstTmp.setPathData(pathData);
      firstTmp.id = firstId;
      firstTmp.setAttribute('class', firstClassName);
      firstTmp.setAttribute('fill', firstFill);
      svg.insertBefore(firstTmp, el);
      el.remove();
    }
    if (i > 0) {
      pathData.forEach(function(command, c) {
        pathsCombinedData += ' ' + command['type'] + '' + command['values'].join(' ');
      });
      el.remove();
    }
  })
  let pathTmp = document.createElementNS("http://www.w3.org/2000/svg", 'path');
  pathTmp.id = id;
  pathTmp.setAttribute('class', className);
  pathTmp.setAttribute('fill', fill);
  pathTmp.setAttribute('d', pathsCombinedData);
  svg.insertBefore(pathTmp, els[0].nextElementSibling);
};

shapesToPathMerged(svg);


function subtract(svg) {
  // init paper.js and add mandatory canvas
  canvas = document.createElement('canvas');
  canvas.id = "canvasPaper";
  canvas.setAttribute('style', 'display:none')
  document.body.appendChild(canvas);
  paper.setup("canvasPaper");

  let all = paper.project.importSVG(svg, function(item, i) {
    let items = item.getItems();
    // remove first item not containing path data
    items.shift();
    // get id names for selecting svg elements after processing
    let ids = Object.keys(item._namedChildren);

    if (items.length) {
      let lastEl = items[items.length - 1];
      // subtract paper.js objects
      let subtracted = items[0].subtract(lastEl);
      // convert subtracted paper.js object to svg pathData
      let subtractedData = subtracted
        .exportSVG({
          precision: decimals
        })
        .getAttribute("d");
      let svgElFirst = svg.querySelector('#' + ids[0]);
      let svgElLast = svg.querySelector('#' + ids[ids.length - 1]);
      // overwrite original svg path
      svgElFirst.setAttribute("d", subtractedData);
      // delete subtracted svg path
      svgElLast.remove();
    }
  });
  // get data URL
  getdataURL(svg)

}

function getdataURL(svg) {
  let markup = svg.outerHTML;
  markupOpt = 'data:image/svg+xml;utf8,' + markup.replaceAll('"', '\'').
  replaceAll('\t', '').
  replaceAll('\n', '').
  replaceAll('\r', '').
  replaceAll('></path>', '/>').
  replaceAll('<', '%3C').
  replaceAll('>', '%3E').
  replaceAll('#', '%23').
  replaceAll(',', ' ').
  replaceAll(' -', '-').
  replace(/ +(?= )/g, '');

  let btn = document.createElement('a');
  btn.href = markupOpt;
  btn.innerText = 'Download Svg';
  btn.setAttribute('download', 'subtracted.svg');
  document.body.insertAdjacentElement('afterbegin', btn);
  return markupOpt;
}

<script src="https://cdnjs.cloudflare.com/ajax/libs/paper.js/0.12.0/paper-full.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/path-data-polyfill@1.0.3/path-data-polyfill.min.js"></script>


<p>
  <button type="button" onclick="subtract(svg)">Subtract Path </button>
</p>
<svg id="svgSubtract" viewBox="0 0 100 100" xmlns="http://www.w3.org/2000/svg">
        <rect class="cls-1" x="0" y="0" width="80" height="80" fill="red" />
        <path id="s"
            d="M87.9,78.7C87.9,84,86,88,82.2,91c-3.8,2.9-8.9,4.4-15.4,4.4c-7,0-12.5-0.9-16.2-2.7v-6.7c2.4,1,5.1,1.8,8,2.4
        c2.9,0.6,5.7,0.9,8.5,0.9c4.6,0,8.1-0.9,10.4-2.6c2.3-1.7,3.5-4.2,3.5-7.3c0-2.1-0.4-3.7-1.2-5.1c-0.8-1.3-2.2-2.5-4.1-3.6
        c-1.9-1.1-4.9-2.4-8.8-3.8c-5.5-2-9.5-4.3-11.8-7c-2.4-2.7-3.6-6.2-3.6-10.6c0-4.6,1.7-8.2,5.2-10.9c3.4-2.7,8-4.1,13.6-4.1
        c5.9,0,11.3,1.1,16.3,3.2l-2.2,6c-4.9-2.1-9.7-3.1-14.3-3.1c-3.7,0-6.5,0.8-8.6,2.4c-2.1,1.6-3.1,3.8-3.1,6.6
        c0,2.1,0.4,3.7,1.1,5.1c0.8,1.3,2,2.5,3.8,3.6c1.8,1.1,4.6,2.3,8.3,3.6c6.2,2.2,10.5,4.6,12.9,7.1C86.7,71.4,87.9,74.7,87.9,78.7z" />

        <path id="o" d="M30.2,22.4c0,8.3-5.8,12-11.2,12c-6.1,0-10.8-4.5-10.8-11.6c0-7.5,4.9-12,11.2-12C25.9,10.8,30.2,15.5,30.2,22.4z
        M12.4,22.6c0,4.9,2.8,8.7,6.8,8.7c3.9,0,6.8-3.7,6.8-8.7c0-3.8-1.9-8.7-6.7-8.7C14.5,13.8,12.4,18.3,12.4,22.6z" />
        <circle cx="50%" cy="50%" r="10%"></circle>
    </svg>

Answer 2

This is a nontrivial problem in general.

It can be solved easily (little code) if you can accept rasterizing the shapes to pixels, perform the boolean operation there, and then vectorize back the result using marching squares + simplification.

Known algorithms to compute instead a somewhat exact* geometric result are quite complex and difficult to implement correctly while keeping them fast.

Clipper is an easy to use library to perform this kind of computation in C++, with ports to Javascript.

Please note that what is difficult is to correctly handle edge cases (e.g. when input lines are partially overlapping or vertices fall exactly on a line and when the result includes zero-area parts).

Code that only reasons about cases in which crossings are clear is a lot easier to write, but unfortunately can produce results that are macroscopically wrong when those edge cases do actually happen.

Floating point math is too unpredictable to be used for these computations... see for example https://hal.inria.fr/inria-00344310/document for a detailed discussion of the kind of issues that will be present when using floating point math for exact geometric computation.

Even a "simple" equation like the one that tells if three points are collinear, clock-wise or counter-clokwise behave crazily when computed with floating point math... (images from the paper)

---

(*) A truly exact solution is impossible even in theory when using floating point numbers: the coordinates of the intersection of two segments with integer coordinates cannot, in general, be represented exactly by floating point numbers; thus ANY result in floating point (no matter how computed) will be an approximation as exact rationals are required for the correct result. What Clipper for example provide are fast computations and results that are guaranteed to be "close" to the exact result (i.e. avoiding macroscopic errors; they can still contain small inaccuracies and even small topological errors).