Ramer–Douglas–Peucker Algorithm

.block

height: 600
scrolling: no
border: yes
license: cc-by-4.0

calc.mjs

const ERRORS = [
  "Polygon's newSize parameter can't be less than 2!",
  "Parameter dots[] must contain at least 2 { x, y } objects!",
  "Parameter epsilon can't be a negative value!"
];

export default function reducePolygon(dots, newSize, debug=true) {
  if (newSize < 2)  throw RangeError(ERRORS[0]);

  let reduced, ep = 0;

  do {
    reduced = shortDistRDP(dots, ep++);
    debug && console.log(`Step: ${ep - 1}\t\tSize: ${reduced.length}`);
  } while (reduced.length > newSize);

  return reduced;
}

export function shortDistRDP(dots, epsilon) {
  if (!dots || dots.length < 2)  throw RangeError(ERRORS[1]);
  if (epsilon < 0)  throw RangeError(ERRORS[2]);

  if (dots.length === 2)  return dots.slice();

  const last = dots.length - 1, head = dots[0], tail = dots[last];
  let maxDistSq = 0, idx = -1;

  for (let i = 1; i < last; ++i) {
    const currDistSq = dotToLineDistSq(dots[i], head, tail);
    if (currDistSq > maxDistSq)  maxDistSq = currDistSq, idx = i;
  }

  if (Math.sqrt(maxDistSq) > epsilon) {
    const recurResL = shortDistRDP(dots.slice(0, idx + 1), epsilon),
          recurResR = shortDistRDP(dots.slice(idx), epsilon);

    --recurResL.length;
    Array.prototype.push.apply(recurResL, recurResR);

    return recurResL;
  }

  return [ head, tail ];
}

export function dotToLineDistSq(p, v, w) {
  const lineLen = dotDistSq(v, w);
  if (!lineLen)  return dotDistSq(p, v);

  const lineX = w.x - v.x, lineY = w.y - v.y,
        t = ((p.x - v.x)*lineX + (p.y - v.y)*lineY) / lineLen;

  if (t < 0)  return dotDistSq(p, v);
  if (t > 1)  return dotDistSq(p, w);

  return dotDistSq(p, { x: v.x + t*lineX, y: v.y + t*lineY });
}

export function dotDistSq(a, b) {
  return (a.x - b.x)**2 + (a.y - b.y)**2;
}

data.mjs

export default function mapXYTableToXYArray(t, asVectors=false) {
  return t.getArray().map(asVectors && xyArrToVecMap || xyArrToXYObjMap);
}

function xyArrToVecMap([ x, y ]) {
  return p5.instance && createVector(+x, +y) || new p5.Vector(+x, +y);
}

function xyArrToXYObjMap([ x, y ]) {
  return { x: +x, y: +y };
}

index.html

<script defer src=https://cdn.JsDelivr.net/npm/p5></script>
<script type=module src=sketch.mjs></script>

sketch.mjs

/**
 * Ramer-Douglas-Peucker Algorithm (v1.2.5)
 * GoToLoop & JeffThompson (2019/Aug/28)
 *
 * https://Discourse.Processing.org/t/reducing-points-in-polygon/13590/6
 *
 * https://en.Wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm
 * https://Karthaus.nl/rdp/js/rdp2.js
 *
 * https://Bl.ocks.org/GoSubRoutine/da4939559d8b786df13f5694ea2edd30
 */

import reducePolygon from './calc.mjs';
import mapXYTableToXYArray from './data.mjs';

const QTY = 12, DIAM = 15, BOLD = 2,
      BG = 0xff, FG = [ 0, 0x64 ], STROKE = [ 0, 0x96, 0xff ],
      DEBUG = true, GET_VECTORS = false, FILENAME = 'xy.csv';

let table, coords, reduced,
    bg, fg, trace;

window.preload = function () {
  table = loadTable(FILENAME);
};

window.setup = function () {
  createCanvas(800, 600);
  strokeWeight(BOLD).noLoop();

  bg = color(BG), fg = color(FG), trace = color(STROKE);

  coords = mapXYTableToXYArray(table, GET_VECTORS);
  DEBUG && print("Polygon's original size: " + coords.length);

  reduced = reducePolygon(coords, QTY, DEBUG);
  if (DEBUG) {
    print("Polygon's final size: " + reduced.length + "\n\n");
    console.table(reduced);
  }
};

window.draw = function () {
  background(bg);
  drawPoints(coords);

  translate(width >> 1, 0);
  drawPoints(reduced);
};

function drawPoints(dots) {
  if (!dots)  return;

  noFill().stroke(trace).beginShape();
  for (const { x, y } of dots)  vertex(x, y);
  endShape(CLOSE);

  fill(fg).noStroke();
  for (const { x, y } of dots)  circle(x, y, DIAM);
}

xy.csv