GoSubRoutine · May 28, 2020 10:01
diff --git a/.block b/.block
 height: 600
 scrolling: no
 border: yes
 license: cc-by-4.0
diff --git a/calc.mjs b/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;
 }
diff --git a/data.mjs b/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 };
 }
diff --git a/index.html b/index.html
 <script defer src=https://cdn.JsDelivr.net/npm/p5></script>
 <script type=module src=sketch.mjs></script>
diff --git a/sketch.mjs b/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);
 }
diff --git a/xy.csv b/xy.csv
	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 + tlineX, y: v.y + tlineY });
	}

	export function dotDistSq(a, b) {
	return (a.x - b.x)2 + (a.y - b.y)2;
	}
	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 };
	}
	<script defer src=https://cdn.JsDelivr.net/npm/p5></script>
	<script type=module src=sketch.mjs></script>
	/**
	* 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);
	}
	337	333
	337	342
	333	390
	332	391
	328	406
	328	407
	328	408
	314	445
	314	446
	291	494
	291	495
	289	499
	276	525
	272	531
	271	532
	266	539
	261	543
	259	545
	257	547
	256	548
	253	549
	252	550
	247	551
	234	552
	222	552
	221	551
	219	550
	219	550
	159	443
	154	433
	151	424
	150	422
	139	392
	135	380
	134	378
	124	326
	122	313
	118	283
	118	270
	118	258
	119	245
	121	227
	126	193
	129	182
	132	173
	133	171
	154	134
	208	41
	220	41
	220	42
	277	127
	286	142
	304	174
	319	211
	320	213
	320	214
	330	243
	330	245
	330	246
	334	260
	334	262
	337	299