Is there a way to reduce the number of coordinates in a complex enclosed SVG path?

Question

What I'd like to do is take an SVG shape drawn by an enclosed path (in this case, a region of a map) and reduce the number of points to create a simpler shape.

I've tried implementing the Ramer-Douglas-Peucker algorithm to reduce the number of points. For example, here's a fiddle using the simplify.js library:

https://jsfiddle.net/0t3n8762/

After reading about the issue, if I understood it correctly, it seems the algorithm isn't really designed to work on enclosed shapes but open ended paths. I tried splitting each path into two (so there are two lines that together make the entire shape) and running the algorithm on each before recombining them, though the results seem essentially identical:

https://jsfiddle.net/caqwL3t7/

It may be (and indeed is quite likely) that I'm just not grasping how the algorithm is supposed to work and am implementing it incorrectly. Or perhaps that I should be trying a completely different method altogether.

coords = pathToCoords($("#JP-01").attr("d"));

for (var i = 0; i < coords.length; i++) {
 newCoords[i] = simplify(coords[i], 2);
}

newPath = coordsToPath(newCoords);

$("#JP-01").attr("d", newPath);

What I would want to produce is a simpler path that still retains the overall shape of the original, drawn with fewer points. The actual result is a distorted shape that shares little in common with the original.

Answer 1

As Paul pointed out in the comments, you haven't considered about l and v command in a path.

I made a snippet to show how to achieve your goal but it won't work in all the cases (I guess) and it still needs to be improved.

Kindly find the snippet and comments below.

$("#simplify-1").on("click", function(){
    var coords;
    var newCoords = [];
    var newPath;
    var coordsObject;

    // get the coordinates from a given path
    function pathToCoords(path) {
      // save each path individually (.i.e islands are stored separately)
      var data = path.match(/(?<=m).*?(?=z)/igs);
      var coordsArray = [];
      var objectArray = [];
      var objectArrayA = [];
      var objectArrayB = [];
      var objectContainer = [];

      // split each pair of coordinates into their own arrays
      for (var i = 0; i < data.length; i++) {
        // should remove anything between h or v and l instead?
        data[i] = data[i].split(/[LlHhVv]/);
        coordsArray[i] = [];

        for (var j = 0; j < data[i].length; j++) {
          coordsArray[i].push(data[i][j].split(",").map(Number));
        }
      }

      // convert each pair of coordinates into an object of x and y
      for (var i = 0; i < coordsArray.length; i++) {
        objectArray[i] = [];

        for (var j = 0; j < coordsArray[i].length; j++) {
          objectArray[i].push({
            x: coordsArray[i][j][0],
            y: coordsArray[i][j][1]
          });
        }

        // split each array of coordinates in half
        var halfway = Math.floor(objectArray[i].length / 2);

        objectArrayB[i] = JSON.parse(JSON.stringify(objectArray[i]));;
        objectArrayA[i] = objectArrayB[i].splice(0, halfway);
      }

      objectContainer = [objectArrayA, objectArrayB];

      return objectContainer;
    }

    // convert the coordinates back into a string for the path
    function coordsToPath(objectContainer) {
      var objectArray = [];
      var coordsArray = [];
      var data;

      // recombine the two objectArrays
      for (var i = 0; i < objectContainer[0].length; i++) {
        objectArray[i] = objectContainer[0][i].concat(objectContainer[1][i])
      }

      for (var i = 0; i < objectArray.length; i++) {
        coordsArray[i] = [];

        // take the X and Y values from the objectArray and strip the unwanted information
        for (var j = 0; j < objectArray[i].length; j++) {
          if (j == 0) {
            // add 'M' in front of the first entry
            coordsArray[i].push("M" + Object.values(objectArray[i][j]));
          } else if (j == objectArray[i].length - 1) {
            // add 'z' to the end of the last entry
            coordsArray[i].push("l" + Object.values(objectArray[i][j]) + "z");
          } else {
            // add 'l' in front of each coordinate pair
            coordsArray[i].push("l" + Object.values(objectArray[i][j]));
          }
        }

        coordsArray[i] = coordsArray[i].toString();
      }

      // put everything back into a single valid SVG path string
      data = coordsArray.join("");

      return data;
    }

    // -- simplify.js -- //

    /*
     (c) 2017, Vladimir Agafonkin
     Simplify.js, a high-performance JS polyline simplification library
     mourner.github.io/simplify-js
    */

    (function() {
      'use strict';

      // to suit your point format, run search/replace for '.x' and '.y';
      // for 3D version, see 3d branch (configurability would draw significant performance overhead)

      // square distance between 2 points
      function getSqDist(p1, p2) {

        var dx = p1.x - p2.x,
          dy = p1.y - p2.y;

        return dx * dx + dy * dy;
      }

      // square distance from a point to a segment
      function getSqSegDist(p, p1, p2) {

        var x = p1.x,
          y = p1.y,
          dx = p2.x - x,
          dy = p2.y - y;

        if (dx !== 0 || dy !== 0) {

          var t = ((p.x - x) * dx + (p.y - y) * dy) / (dx * dx + dy * dy);

          if (t > 1) {
            x = p2.x;
            y = p2.y;

          } else if (t > 0) {
            x += dx * t;
            y += dy * t;
          }
        }

        dx = p.x - x;
        dy = p.y - y;

        return dx * dx + dy * dy;
      }
      // rest of the code doesn't care about point format

      // basic distance-based simplification
      function simplifyRadialDist(points, sqTolerance) {

        var prevPoint = points[0],
          newPoints = [prevPoint],
          point;

        for (var i = 1, len = points.length; i < len; i++) {
          point = points[i];

          if (getSqDist(point, prevPoint) > sqTolerance) {
            newPoints.push(point);
            prevPoint = point;
          }
        }

        if (prevPoint !== point) newPoints.push(point);

        return newPoints;
      }

      function simplifyDPStep(points, first, last, sqTolerance, simplified) {
        var maxSqDist = sqTolerance,
          index;

        for (var i = first + 1; i < last; i++) {
          var sqDist = getSqSegDist(points[i], points[first], points[last]);

          if (sqDist > maxSqDist) {
            index = i;
            maxSqDist = sqDist;
          }
        }

        if (maxSqDist > sqTolerance) {
          if (index - first > 1) simplifyDPStep(points, first, index, sqTolerance, simplified);
          simplified.push(points[index]);
          if (last - index > 1) simplifyDPStep(points, index, last, sqTolerance, simplified);
        }
      }

      // simplification using Ramer-Douglas-Peucker algorithm
      function simplifyDouglasPeucker(points, sqTolerance) {
        var last = points.length - 1;

        var simplified = [points[0]];
        simplifyDPStep(points, 0, last, sqTolerance, simplified);
        simplified.push(points[last]);

        return simplified;
      }

      // both algorithms combined for awesome performance
      function simplify(points, tolerance, highestQuality) {

        if (points.length <= 2) return points;

        var sqTolerance = tolerance !== undefined ? tolerance * tolerance : 1;

        points = highestQuality ? points : simplifyRadialDist(points, sqTolerance);
        points = simplifyDouglasPeucker(points, sqTolerance);

        return points;
      }

      // export as AMD module / Node module / browser or worker variable
      if (typeof define === 'function' && define.amd) define(function() {
        return simplify;
      });
      else if (typeof module !== 'undefined') {
        module.exports = simplify;
        module.exports.default = simplify;
      } else if (typeof self !== 'undefined') self.simplify = simplify;
      else window.simplify = simplify;

    })();

    // -- end simplify.js -- //

    coords = pathToCoords($("#OriginalJP-01").attr("d"));

    for (var i = 0; i < coords.length; i++) {
      newCoords[i] = [];
      for (var j = 0; j < coords[i].length; j++) {
        newCoords[i][j] = simplify(coords[i][j], 1);
      }
    }

    newPath = coordsToPath(newCoords);
    $("#JP-01").attr("d", newPath);
});

$("#simplify-2").on("click", function(){
    let d = $("#OriginalJP-01").attr("d");
    let coordsArray = [];
    let data = d.match(/(?<=m).*?(?=z)/igs);
    // split each pair of coordinates into the array as an object {x, y}
    for (var i = 0; i < data.length; i++) {
        let ca = coordsArray[i] = [];
        // split data[i] into each coordinate text
        let matches = data[i].match(/((\w?-?\d+(\.\d+)?)(,-?\d+(\.\d+)?)?)/g);
        for(let j=0;j<matches.length;j++){
            let x, y,
                text = matches[j],
                // split with comma and convert it to a number
                temp = text.split(",").map(v=>+v.replace(/^[^\-\d]/g,""));
            switch(text[0]){
                default:
                case "L": // absolute
                    x = temp[0];
                    y = temp[1];
                break;

                case "l": // relative
                    x = ca[j-1].x + temp[0];
                    y = ca[j-1].y + temp[1];
                break;

                case "V": // absolute
                    x = ca[j-1].x;
                    y = temp[0];
                break;

                case "v": // relative
                    x = ca[j-1].x;
                    y = ca[j-1].y + temp[0];
                break;

                case "H": // absolute
                    x = temp[0];
                    y = ca[j-1].y;
                break;

                case "h": // relative
                    x = ca[j-1].x + temp[0];
                    y = ca[j-1].y;
                break;
            }
            x = +x.toFixed(2);
            y = +y.toFixed(2);
            ca.push({x, y});
        }
    }

    let mArray = [];
    // calculate the slopes
    for(let i=0;i<coordsArray.length;i++){
        mArray[i] = [];
        for(let j=0;j<coordsArray[i].length-1;j++){
            let {x, y} = coordsArray[i][j], // current point's x and y
                {x: nx, y: ny} = coordsArray[i][j+1], // next point's x and y
                dy = (ny - y);

            if(dy === 0) // to check if the denominator is legal or not
                // in your case, it would not enter here
                mArray[i].push(Infinity);
            else
                mArray[i].push((nx - x) / dy);
        }
    }
    let abandonFactor = +$("#abandonFactor").val();
    let newCoordsArray = [];
    for(let i=0;i<mArray.length;i++){
        let na = newCoordsArray[i] = [];
        // calculate the abandonRate base on the amount of the original points
        let abandonRate = coordsArray[i].length * abandonFactor;
        for(let j=0;j<mArray[i].length-1;j++){
            let m = mArray[i][j], // this slope
                nm = mArray[i][j+1]; // next slope
            let diffRate = Math.abs((m - nm) / m); // calculate the changes of the slope

            // check if the diffRate is greater than abandonRate
            // or the sign of m not equals the sign of nm
            // you can try out removing the "sign check part" and see what would happen ;)
            if(diffRate >= abandonRate || (Math.sign(m) !== Math.sign(nm))){
                na.push(coordsArray[i][j]);
            }
        }
    }
    
    let newPath = [];
    // create new path
    for(let i=0;i<newCoordsArray.length;i++){
        let temp = [];
        for(let j=0;j<newCoordsArray[i].length;j++){
            let {x, y} = newCoordsArray[i][j];
            let p = `${x},${y}`;
            temp.push(p);
        }
        newPath.push("M" + temp.join("L") + "z");
    }

    $("#JP-01").attr("d", newPath.join(""));
}).click();

$("#abandonFactor").on("change", function(){
    $("#abandonFactor_text").text(`Abandon factor: ${this.value}`);
    $("#simplify-2").click();
});

div {
  width: 50%;
}

.original {
  float: left;
}

.simplified {
  float: right;
}

.map {
  box-sizing: border-box;
  width: 100%;
  padding: 0.5rem;
  text-shadow: 1px 1px white;
  cursor: grab;
}

.land {
  fill: lightgreen;
  fill-opacity: 1;
  stroke: white;
  stroke-opacity: 1;
  stroke-width: 0.5;
  cursor: pointer;
}

<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.3.1/jquery.min.js"></script>
<div class="original">
  <svg id="OriginalMap" viewBox="324.55999755859375 0 126.44989013671875 111.65999603271484" class="map" xmlns="http://www.w3.org/2000/svg" xmlns:amcharts="http://amcharts.com/ammap">
    <g>
      <path id="OriginalJP-01" title="Hokkaido" class="land" d="
      M344.04,71.29l2.71,-2.13l0.04,-0.59l-1.96,-3.17l-1.38,-0.99l-0.7,-1.16l0.68,-2.54l-0.27,-0.48l1.64,0.11l0.6,-0.42l0.21,-0.54l0.53,-0.21l2.75,2.66l1.93,0.87l1.13,1.28l2.48,-0.47l0.17,-0.42l1.02,-0.32l0.72,0.02l-0.14,1.17l3.04,1.39l2.2,-1.22l1.97,-2.15l0.99,-1.6l0.1,-2.35l-1.38,-2.76l0.54,-1.94L363,51.89l-0.45,-2.27l1.02,-2.1l1.47,-0.89l0.76,-0.05l2.03,-1.32l0.93,-1.89l0.41,-1.95l-0.35,-7.86l0.5,-0.32l1.64,-3.44l0.21,-2.86l0.38,-0.79l0.13,-1.6l-0.3,-3.27l-0.77,-3.84l-3.04,-7.32l-0.31,-1.16l0.07,-0.99l0.86,-1.27l0.79,-1.95l-0.41,-1.4l0.15,-1.28l0.75,0.77l0.13,0.52l0.39,0.16l1.76,-0.28l1.35,-0.94l0.55,-1.99L374.52,0l0.47,0.33l0.56,1.29l0.59,0.34l0.63,1.47l2.32,1.7l2.21,3.12l4.95,5.56l3.91,7.23l2.58,2.55l2.44,3.1l5.58,4.4l1.57,0.89l0.33,0.95l1.26,0.96l3.7,1.94l3.24,1.28l5.88,1.69l2.79,0.53l0.44,-0.31l0.29,0.77l-0.06,1.28l0.87,1.55l0.58,0.48l3.21,1.01l3.41,0.21l2.57,-0.32l2.28,-1.99l1.54,-1.92l2.18,-2.04l1.83,-1.26l0.66,-1.45l1.1,-1.16l0.78,-1.38l0.46,0.03l0.45,2.23l-1.21,2.49l-0.91,0.92l-0.6,2.4l-1.73,2.13l-0.94,2.12l0.1,0.83L436.06,48l0.22,1.06l1.35,2.58l1.49,1.97l1.52,5.23l1.49,1.96l-1.16,-0.53l-0.19,-0.53l-1.14,-0.22l-0.24,0.37l0.21,1.26l0.86,-0.67l0.47,0.4l-0.29,0.55l0.37,0.39l0.4,-0.28l2.55,0.62l2.09,-1.7l0.32,-0.6l1.11,-0.71l0.24,-0.5l3.28,0.2l-0.19,0.5l-1.17,0.91l-1.73,0.31l-1.87,1.03l-0.8,2.93l-0.77,-0.36l-1.24,-0.05l-2.71,0.51l-1.51,0.9l-1.26,-0.21l-0.62,0.6l-0.14,1.15l-1.6,2.15l-1.02,0.49l-1.9,-0.1l-0.9,-0.79l0.03,-0.53l0.33,-0.31l-0.55,-0.37l-0.73,0.1l-1.19,1.73l-0.02,0.41l1.15,1.13l-2.01,-0.12l-1.15,-0.35l-3.58,-0.02l-0.69,-0.15l-1.58,-1.27l-3.06,0.54l-2.43,1.18l-3.4,2.53l-5.27,5.27l-4.08,5.8l-1.53,3.31l-0.28,1.67l0.55,1.44l-0.82,3.88l-0.91,1.53l0,1.61l-3.7,-3.72l-4.85,-2.02l-8.09,-4.45l-2.38,-1.67l-1.84,-2.05l-3.21,-0.94l-2.21,-2.05l-1.82,-1.2l-1.83,-0.53l-2.38,-0.04l-3.17,1.04l-2.08,1.29l-2.68,2.28l-1.59,0.89l-2.12,2.45l-0.34,0.75l-1.07,-0.4l-0.33,-0.55l0.38,-0.29l0.59,0.64l0.12,-0.81l-1.35,-0.41l-0.87,-2.37l-0.79,-0.4l-1.07,-1.12l-0.12,-0.58l-1.27,-1.23l-1.24,-0.09l-1.25,0.53l-0.97,-0.59l-1.21,0.03l-1.68,1.81l-1.44,2.75l-0.71,2.55l0.28,1.94l2.32,1.2l2.74,2.35l0.75,0.14l1.37,-0.53l2.04,0.31l1.23,2.21l1.63,1.22l1.08,1.88l3.15,1.36l0.55,0.89l0.79,0.59l-0.61,0.61l-0.95,0.01l-1.1,1.3l-1.66,0.66l-0.86,-0.79l-2.78,-0.91l-0.93,0.16l-0.28,0.62l-0.41,0.1l-0.18,-0.61l0.68,-0.45l-0.2,-0.67l-0.59,-0.37l-0.86,0.08l-0.41,0.33l-0.43,1.68l-1.44,1.06l-1.29,0.1l-0.35,0.33l-0.31,3.94l-0.4,0.48l-0.94,0.03l-1.96,0.87l-0.9,1.89l-0.39,0.32l-1.02,-0.8l-1.14,0.22l-0.9,-0.71l-1.08,-2.72l-0.09,-0.86l0.41,-1.77l1.35,-3.03v-1.05l0.77,0.08l0.29,-0.59l0.31,-2.7l-0.4,-1.98l-1.9,-2.94l-0.67,-0.36l-1.3,-0.12L334.29,91l-0.85,-0.88l-1.14,-0.41l-0.39,-0.73l-0.19,-1.39l0.31,-1.12l0.94,-1.03l0.33,-0.95l0.03,-2.65l-0.49,-2.23l0.92,-1.45l1.12,-0.62l2.28,-0.06l0.61,-0.91l1.39,-0.73l0.85,-1.92l0.82,0.57l0.56,0.97l0.89,-0.23l0.09,-1.39l0.82,-0.84L344.04,71.29z
      M358.76,9.86l-0.09,-1.23l1.28,-1.25l2.07,1.21l0.51,1.81l-1.81,1.49l-1.37,-1.07L358.76,9.86z
      M326.88,91.03l-0.29,2.22l-0.39,0.63l-0.65,0.23l-0.02,0.36l-0.61,-0.54l0.06,-1.71l-0.42,-1.11l0.74,-1.09l1.91,-0.38l0.46,-0.52l0.03,0.64L326.88,91.03z
      M357.23,4.25l-0.26,2.59l-0.39,0.13L355.7,4l0.22,-1.31l-0.61,-0.34l0.09,-0.73l0.65,0.85l0.66,-0.15l-0.02,-0.59L357.03,2l0.35,0.78L357.23,4.25z"/>
    </g>
  </svg> Original
</div>

<div class="simplified">
  <svg id="Map" viewBox="324.55999755859375 0 126.44989013671875 111.65999603271484" class="map" xmlns="http://www.w3.org/2000/svg" xmlns:amcharts="http://amcharts.com/ammap">
    <g>
      <path id="JP-01" title="Hokkaido" class="land" d=""/>
    </g>
  </svg> Simplified
  <button id="simplify-1">Your method</button>
  <button id="simplify-2">New method</button>
  <input type="range" min="0.0001" max="0.1" value="0.01" step="0.0001" class="slider" id="abandonFactor">
  <div id="abandonFactor_text">Abandon factor: 0.01</div>
</div>