// https://thecodingtrain.com/CodingChallenges/148-gift-wrapping.html

// https://youtu.be/YNyULRrydVI

// https://editor.p5js.org/codingtrain/sketches/IVE9CxBOF

​

// Gift Wrapping Algorithm

​

const points = [];

const hull = [];

​

let leftMost;

let currentVertex;

let index;

let nextIndex = -1;

let nextVertex;

const totalPoints = 30;

const w = 30;

​

function setup() {

  createCanvas(1280, 720);

  let bufferx = 200;

  let buffery = 100;

  const middle = createVector(width/ 2, height / 2);

  let attemps = 0;

  while (points.length < totalPoints && attemps++ < 10000) {

    let candidate = createVector(

      random(bufferx, width - bufferx),

      random(buffery, height - buffery)

    );

    if (p5.Vector.dist(candidate, middle) > 700) {

      continue;

    }

    let valid = true;

    for (let p of points) {

      if (p != candidate && p5.Vector.dist(candidate, p) < 100) {

        valid = false;

      }

    }

    if (valid) {

      points.push(candidate);

    }

  }

  points.sort((a, b) => a.x - b.x);

  leftMost = points[0];

  currentVertex = leftMost;

  hull.push(currentVertex);

  nextVertex = points[1];

  index = 2;

​

  strokeJoin(ROUND);

}

​

function draw() {

  background(112, 50, 126);

​

  stroke(45, 197, 244);

  fill(11, 106, 136);

  beginShape();

  for (let p of hull) {

    vertex(p.x, p.y);

  }

  endShape(CLOSE);

​

  stroke(255);

  strokeWeight(w);

  for (let p of points) {

    point(p.x, p.y);

  }

​

  //   stroke(0, 255, 0);

  //   strokeWeight(w);

  //   point(leftMost.x, leftMost.y);

​

  //   stroke(200, 0, 255);

  //   strokeWeight(w);

  //   point(currentVertex.x, currentVertex.y);

​

  //   stroke(0, 255, 0);

  //   strokeWeight(w);

  //   line(currentVertex.x, currentVertex.y, nextVertex.x, nextVertex.y);

​

  let checking = points[index];

  // stroke(255);

  // line(currentVertex.x, currentVertex.y, checking.x, checking.y);

​

  const a = p5.Vector.sub(nextVertex, currentVertex);

  const b = p5.Vector.sub(checking, currentVertex);

  const cross = a.cross(b);

​

  if (cross.z < 0) {

    nextVertex = checking;

    nextIndex = index;

  }

​

  index = index + 1;

  if (index == points.length) {

    if (nextVertex == leftMost) {

      console.log("done");

      noLoop();

    } else {

      hull.push(nextVertex);

      currentVertex = nextVertex;

      index = 0;

      //points.splice(nextIndex, 1);

      nextVertex = leftMost;

    }

  }

}

​