let hull = []

​

let size = 600

​

function setup() {

  createCanvas(size, size);

  for (var i = 0; i < 50; i++) {

    points.push(createVector(

      20 + (Math.random() * (size - 40)),

      20 + (Math.random() * (size - 40)),

    ));

  }

  hull = convex_hull(points, true);

}

​

function convex_hull(vertexs, clockwise) {

  let sorted = vertexs.sort((a, b) => a.x - b.x);

  let left_most = sorted[0];

  let current = sorted[0];

  let result = [];

  next = sorted[1];

  var i = 0;

  while (true) {

    for (var p of sorted) {

      let current_next = next.copy().sub(current);

      let current_p = p.copy().sub(current);

      let cross = current_next.cross(current_p);

      if (clockwise) {

        cross.z = -cross.z;

      }

      if (cross.z > 0) {

        next = p;

      }

    }

    result.push(next);

    if (next.x == left_most.x && next.y == left_most.y) {

      console.log("convex hull found, points = " + result.length);

      break;

    }

    current = next;

    next = left_most;

    if (i > 100) {

      console.log("Stuck, hull size = " + result.length);

    }

    i++;

  }

  return result;

}

function draw() {

  background(220);

  for (var p of points) {

    stroke('purple');

    strokeWeight(10);

    point(p.x, p.y);

  }

  for (let i = 0; i < hull.length; i++) {

    stroke('green');

    strokeWeight(1 + i * 0.3);

    let a = hull[i];

    let b = hull[(i + 1) % hull.length];

    line(a.x, a.y, b.x, b.y);

    stroke('red');

    strokeWeight(10);

    point(a.x, a.y);

  }

}