Polygon Simplification

Reduce number of vertices in a polygon without altering the fundamental shape too much.

by wio_dude

HTML

<canvas width="500" height="300" id="c"></canvas>
<br/>
<textarea id="t" rows="5" cols="70" readonly></textarea>
<br/>
<input type="range" id="r" min="0" max="10" value="1" step="0.01">

CSS

canvas {
  border: 1px solid blue;
}

JavaScript

const DRAW_COLOR = 'black';

const canvas = document.getElementById('c');
const textarea = document.getElementById('t');
const reductionCount = document.getElementById('r');
const context = canvas.getContext('2d');

let polygon = [];
let rPolygon = [];
let down = false;
let shiftUp = false;


// Geometry functions
function isEqual(p1, p2) {
	return p1[0] === p2[0] && p1[1] === p2[1];
}

function doubleWedge(v1, v2) {
	return v1[0] * v2[1] - v1[1] * v2[0];
}

function pSub(p1, p2) {
	return [p1[0] - p2[0], p1[1] - p2[1]];
}

function triangleDoubleWedge(p1, p2, p3) {
	return doubleWedge(pSub(p2, p1), pSub(p3, p2));
}

function isCollinear(p1, p2, p3) {
  return triangleDoubleWedge(p1, p2, p3) === 0;
}

function polygonDoubleWedgeWeights(polygon) {
	if (polygon.length < 3) {
  	return [];
  }
  const weights = [];
  let n = polygon.length - 1;
  weights.push(triangleDoubleWedge(polygon[n], polygon[0], polygon[1]));
	for (let i = 1; i < n; i++) {
  	weights.push(triangleDoubleWedge(polygon[i - 1], polygon[i], polygon[i + 1]));
  }
  weights.push(triangleDoubleWedge(polygon[n - 1], polygon[n], polygon[0]));
  return weights;
}

function addPointReduced(polygon, point) {
    const lastIndex = polygon.length - 1;
    const lastPoint = polygon[lastIndex];
    if (isEqual(lastPoint, point)) {
    	return;
    }
    if (polygon.length >= 2) {
    	const penultPoint = polygon[lastIndex - 1];
      if (isCollinear(penultPoint, lastPoint, point)) {
        polygon.pop();
        if (isEqual(penultPoint, point)) {
        	return;
        }
      }
    }
    polygon.push(point);
}

function reduceDuplicates(polygon) {
	let reduced = [];
  let lastIndex = 0;
  reduced.push(polygon[lastIndex]);
  let nextIndex = lastIndex + 1;
  while (nextIndex < polygon.length) {
    while (isEqual(polygon[lastIndex], polygon[nextIndex])) {
      nextIndex += 1;
    }
    lastIndex = nextIndex;
    reduced.push(polygon[lastIndex]);
    nextIndex = nextIndex += 1;
  }
  return...