Ramer–Douglas–Peucker Algorithm

.block

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

Calc.pde

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

static final PVector[] reducePolygon(final PVector[] dots, final int newSize) {
  if (newSize < 2)  throw new Error(ERRORS[0]);

  PVector[] reduced;
  int ep = 0;

  do {
    reduced = shortDistRDP(dots, ep++);
    if (DEBUG)  println("Step: " + (ep - 1) + "\t\tSize: " + reduced.length);
  } while (reduced.length > newSize);

  return reduced;
}

static final PVector[] shortDistRDP(final PVector[] dots, final float epsilon) {
  if (dots == null || dots.length < 2)  throw new Error(ERRORS[1]);
  if (epsilon < 0)  throw new Error(ERRORS[2]);

  if (dots.length == 2)  return (PVector[]) expand(dots, dots.length);

  final int last = dots.length - 1;
  final PVector head = dots[0], tail = dots[last];

  float maxDistSq = 0;
  int idx = -1;

  for (int i = 1; i < last; ++i) {
    final float currDistSq = dotLineSq(dots[i], head, tail);

    if (currDistSq > maxDistSq) {
      maxDistSq = currDistSq;
      idx = i;
    }
  }

  if (sqrt(maxDistSq) > epsilon) {
    final PVector[]
      recurResL = shortDistRDP((PVector[]) subset(dots, 0, idx + 1), epsilon), 
      recurResR = shortDistRDP((PVector[]) subset(dots, idx), epsilon);

    return (PVector[]) concat(shorten(recurResL), recurResR);
  }

  return new PVector[] { head, tail };
}

static final float dotLineSq(final PVector p, final PVector v, final PVector w) {
  final float lineLen = vec2dDistSq(v, w);
  if (lineLen == 0)  return vec2dDistSq(p, v);

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

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

  final PVector z = v.get();
  z.add(t * lineX, t * lineY, 0);

  return vec2dDistSq(p, z);
}

static final float vec2dDistSq(final PVector a, final PVector b) {
  return sq(a.x - b.x) + sq(a.y - b.y);
}

Data.pde

static final String FILENAME = "xy.csv", DELIM = ",";

PVector[] loadCoordsXYAsPVectorsArray() {
  final String[] lines = loadStrings(FILENAME);
  final PVector[] vecs = new PVector[lines.length];

  for (int i = 0; i < lines.length; ++i) {
    final PVector v = vecs[i] = new PVector();
    v.set(float(lines[i].split(DELIM)));
  }

  return vecs;
}

index.html

<script defer src=https://Unpkg.com/processing-js></script>
<canvas data-processing-sources="RamerDouglasPeucker.pde Calc.pde Data.pde"></canvas>

RamerDouglasPeucker.pde

/**
 * Ramer-Douglas-Peucker Algorithm (v1.2.3)
 * GoToLoop & JeffThompson (2019/Aug/26)
 *
 * https://Discourse.Processing.org/t/reducing-points-in-polygon/13590/2
 *
 * https://en.Wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm
 * https://Karthaus.nl/rdp/js/rdp2.js
 *
 * https://Bl.ocks.org/GoToLoop/a5db257be4d7756a00220a3e97066dd5
 * https://www.OpenProcessing.org/sketch/747172
 */

static final int QTY = 12, DIAM = 15, BOLD = 2;
static final color BG = -1, FG = 0x64000000, STROKE = #0096FF;

static final boolean DEBUG = true;

PVector[] coords, reduced;

void setup() {
  size(800, 600);
  smooth();
  noLoop();
  strokeWeight(BOLD);

  coords = loadCoordsXYAsPVectorsArray();
  if (DEBUG)  println("Polygon's original size: " + coords.length);

  reduced = reducePolygon(coords, QTY);
  if (DEBUG)  println("Polygon's final size: " + reduced.length + "\n");

  if (DEBUG) {
    final int len = reduced.length, digits = max(0, str(len - 1).length());
    for (int i = 0; i < len; println(nf(i, digits) + ": " + reduced[i++]));
  }
}

void draw() {
  background(BG);
  drawPoints(coords);

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

void drawPoints(final PVector[] dots) {
  if (dots == null)  return;

  noFill();
  stroke(STROKE);

  beginShape();
  for (final PVector v : dots)  vertex(v.x, v.y);
  endShape(CLOSE);

  fill(FG);
  noStroke();

  for (final PVector v : dots)  ellipse(v.x, v.y, DIAM, DIAM);
}

xy.csv