Get n line representative points

simplify.js

/* DOCUMENT INFORMATION
	- Author:   Dominik Maszczyk
	- Email:    [email protected]
	- Created:  2019-09-10
	- Adapted from: https://bost.ocks.org/mike/simplify/
*/

const simplify = function(
  points,
  { accessor_x = d => d.x, accessor_y = d => d.y, number_of_samples = 100 } = {}
) {
  function compare(a, b) {
    return a[1].area - b[1].area;
  }

  function area(t) {
    return Math.abs(
      (accessor_x(t[0]) - accessor_x(t[2])) *
        (accessor_y(t[1]) - accessor_y(t[0])) -
        (accessor_x(t[0]) - accessor_x(t[1])) *
          (accessor_y(t[2]) - accessor_y(t[0]))
    );
  }

  function minHeap() {
    var heap = {},
      array = [];

    heap.push = function() {
      for (var i = 0, n = arguments.length; i < n; ++i) {
        var object = arguments[i];
        up((object.index = array.push(object) - 1));
      }
      return array.length;
    };

    heap.pop = function() {
      var removed = array[0],
        object = array.pop();
      if (array.length) {
        array[(object.index = 0)] = object;
        down(0);
      }
      return removed;
    };

    heap.remove = function(removed) {
      var i = removed.index,
        object = array.pop();
      if (i !== array.length) {
        array[(object.index = i)] = object;
        (compare(object, removed) < 0 ? up : down)(i);
      }
      return i;
    };

    function up(i) {
      var object = array[i];
      while (i > 0) {
        var up = ((i + 1) >> 1) - 1,
          parent = array[up];
        if (compare(object, parent) >= 0) break;
        array[(parent.index = i)] = parent;
        array[(object.index = i = up)] = object;
      }
    }

    function down(i) {
      var object = array[i];
      while (true) {
        var right = (i + 1) << 1,
          left = right - 1,
          down = i,
          child = array[down];
        if (left < array.length && compare(array[left], child) < 0)
          child = array[(down = left)];
        if (right < array.length && compare(array[right], child) < 0)
          child = array[(down = right)];
        if (down === i) break;
        array[(child.index = i)] = child;
        array[(object.index = i = down)] = object;
      }
    }

    return heap;
  }

  var heap = minHeap(),
    maxArea = 0,
    triangle;

  var triangles = [];

  for (var i = 1, n = points.length - 1; i < n; ++i) {
    triangle = points.slice(i - 1, i + 2);
    if ((triangle[1].area = area(triangle))) {
      triangles.push(triangle);
      heap.push(triangle);
    }
  }

  for (var i = 0, n = triangles.length; i < n; ++i) {
    triangle = triangles[i];
    triangle.previous = triangles[i - 1];
    triangle.next = triangles[i + 1];
  }

  while ((triangle = heap.pop())) {
    // If the area of the current point is less than that of the previous point
    // to be eliminated, use the latter’s area instead. This ensures that the
    // current point cannot be eliminated without eliminating previously-
    // eliminated points.
    if (triangle[1].area < maxArea) triangle[1].area = maxArea;
    else maxArea = triangle[1].area;

    if (triangle.previous) {
      triangle.previous.next = triangle.next;
      triangle.previous[2] = triangle[2];
      update(triangle.previous);
    } else {
      triangle[0].area = triangle[1].area;
    }

    if (triangle.next) {
      triangle.next.previous = triangle.previous;
      triangle.next[0] = triangle[0];
      update(triangle.next);
    } else {
      triangle[2].area = triangle[1].area;
    }
  }

  function update(triangle) {
    heap.remove(triangle);
    triangle[1].area = area(triangle);
    heap.push(triangle);
  }

  return points.sort((a, b) => b.area - a.area).slice(0, number_of_samples);
};

var r = simplify(points);
console.log(points.length, r.length);

r.forEach(p => {
  var div = document.createElement("div");
  div.style.position = "absolute";
  div.style.left = p.x+"px";
  div.style.top = p.y+"px";
  div.innerHTML = "O";
  document.body.appendChild(div);
});

https://codepen.io/Skitionek/pen/KKPoZgx