var gifts = []; // the points to wrap

var pWrap = null; // the first point of the wrap

var wrapIndex = -1; // the index in gifts of the pWrap point

var wrap = []; // the wrap

var pTry = null; // used when searching for the lowest point.

var pSelect = null; // used when showing the points order and when building the wrap.

var pBeforeLast = null; // == wrap[wrap.length-2]. Used when building the wrap

var pLast = null; // == wrap[wrap.length-1]. Used when building the wrap

​

function setup() {

  createCanvas(400, 400);

  frameRate(2);

}

​

// Uncomment the statement "yield 1" to show looking for the lowest point.

// Uncommment the statement "yield 3" to show the result of the sort

function* GrahamScan(nbrOfPoints) {

  // Generate the gifts

  for (let i = 0; i < nbrOfPoints; i++) {

    let p = createVector(random(350), random(350));

    gifts.push(p);

  }

  yield 0; // show the gifts

  // Search for the lowest gift (min(y)). This becomes the first point of the wrapper.

  wrapIndex = 0;

  pWrap = gifts[wrapIndex];

  for (let i = 1; i < gifts.length; i++) {

    pTry = gifts[i];

// Uncomment the next statement to show looking for the lowest point.

//    yield 1 // show looking for the lowest gift

    if (pTry.y < pWrap.y || (pTry.y == pWrap.y && pTry.x < pWrap.x)) {

      pWrap = pTry;

      wrapIndex = i;

    }

  } // pWrap is the lowest. wrapIndex is its index in gifts.

  // sorting the points on the angle of the vector pWrap -> point.

  var points = gifts.slice(); // copy

  points.splice(wrapIndex, 1); // remove the first wrap-point pWrap

  points = points.sort((a, b) => {

    // There is no need to calculate the angles. This should be sufficient,... I hope. 

    // Sofar no problems found.

    let h1 = p5.Vector.sub(a, pWrap);

    let h2 = p5.Vector.sub(b, pWrap);

    let t = h2.x*h1.y - h1.x*h2.y

    if (t == 0)

      t = Math.sign(p5.Vector.sub(b, pWrap).magSq() - p5.Vector.sub(a, pWrap).magSq());

    return t;

  });

  // loop through the points to show the order.

  for (var i=0;i<points.length;i++) {

    pSelect = points[i];

// Uncomment the next statement to show the result of the sort.

//    yield 3 // show the line from pWrap to pSelect

  }

  // the search for the wrapper

  wrap.push(pWrap); // the first wrap point

  while (points.length > 0) { // as long as their are points to consider

    pSelect = points.shift(); // in angle order

    while (wrap.length > 1) { // there must be at least 2 entries in wrap

      pBeforeLast = wrap[wrap.length - 2];

      pLast = wrap[wrap.length - 1];

      let p1 = p5.Vector.sub(pLast, pBeforeLast);

      let p2 = p5.Vector.sub(pSelect, pLast);

      let cross = p5.Vector.cross(p1, p2);

      yield 4; // show the angle to check.

      if (cross.z < 0) {

        wrap.pop(); // angle is not acceptable: remove pLast from wrap

      } else break; // angle is acceptable.

    }

    wrap.push(pSelect);

  } // while points.length>0

  wrap.push(pWrap); // finish off  by closing the wrapper

}

​

function TextState(t) {

  push();

  translate(0,400);

  scale(1,-1);

  fill(0);

  strokeWeight(1);

  stroke(0);

  text(t,100,30);

  pop();  

}

​

function draw() {

  scale(1, -1);

  translate(0, -400);

  background(220);

  var result = gs.next();

  var value = result.value;

  if (result.done) value = 5;

  if (value==0) TextState("Graham's scan");

  // Show all the gifts. 

  if (value >= 0) {

    fill(color(0,0,0));

    noStroke();

    for (var i = 0; i < gifts.length; i++) {

      var p = gifts[i];

      circle(p.x, p.y, 5);

    }

  } // value >= 0

  // show looking for the lowest point.

  if (value == 1) {

    TextState("Graham's scan: Look for the lowest point");

    // check pTry against the lowest sofar (pWrap; see under value>=1)

    fill(color(0, 255, 0));

    circle(pTry.x, pTry.y, 10);

  } // values == 1

  if (value == 3) {

    // show the result of the sort

    TextState("Graham's scan: Result of the sort");

    fill(color(0, 0, 255));

    strokeWeight(3);

    stroke(color(0,0,255)); // wrap (sofar)

    line(pWrap.x, pWrap.y, pSelect.x, pSelect.y);

    circle(pSelect.x, pSelect.y, 15);

  } // value == 3

  if (value >= 1) {

    // the lowest point (pWrap) and (part of) the wrapping. (wrap)

    fill(color(255, 0, 0));

    circle(pWrap.x, pWrap.y, 10);

    if (wrap.length > 1) {

      strokeWeight(3);

      stroke(color(0,255,0)); // wrap (sofar)

      noFill();

      beginShape();

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

        let pnt = wrap[i];

        vertex(pnt.x, pnt.y);

      }

      endShape();

      noStroke();

    }

  } // value >= 1

  // Show the last 2 lines that possibly make up the wrapping.

  // The other parts of the wrapping are shown under value>=1 

  if (value == 4) {

    TextState("Graham's scan: Make the wrapping");

    stroke(color(0, 0, 255));

    strokeWeight(3);

    line(pBeforeLast.x, pBeforeLast.y, pLast.x, pLast.y);

    //stroke(color(255, 0, 0));

    line(pLast.x, pLast.y, pSelect.x, pSelect.y);

  } // value == 4;

​

  if (value == 5) {

    TextState("Graham's scan: the result");

    noLoop();

  }

}

​

​