let orig = [];

let dir = 1;

​

let triangles = [];

let indices = [];

​

function setup() {

  createCanvas(400, 400);

  polygon = generatePolygon(9);

  orig = polygon.slice();

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

    indices.push(i);

  }

}

​

function generatePolygon(n){

  let vertList = [];

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

    vertList.push(createVector(random()*width,random()*height));

  }

  if(selfIntersecting(vertList)){

    vertList = generatePolygon(n);

  }

  return vertList;

}

​

function selfIntersecting(vertList){

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

    for(let j=0;j<vertList.length;j++){

      //check intersection j, j+1 with i, i+1

      if(i==j || abs(i-j)==1 || abs(i-j)==vertList.length-1){

        continue

      }

      if(checkIntersect(

          vertList[i].x,

          vertList[i].y, 

          vertList[(i+1)%vertList.length].x,

          vertList[(i+1)%vertList.length].y,

          vertList[j].x,

          vertList[j].y,

          vertList[(j+1)%vertList.length].x,

          vertList[(j+1)%vertList.length].y)){

        return true

      }

    }

  }

  return false

}

function checkIntersect(x1,y1,x2,y2,x3,y3,x4,y4){

      let t = ((x1-x3)*(y3-y4)-(y1-y3)*(x3-x4))/ 

              ((x1-x2)*(y3-y4)-(y1-y2)*(x3-x4));

      let u = ((x1-x3)*(y1-y2)-(y1-y3)*(x1-x2))/ 

              ((x1-x2)*(y3-y4)-(y1-y2)*(x3-x4));

      return( t<=1 && t>=0 && u<=1 && u>=0);

}

​

function draw() {

  background(220);

  noFill();

  stroke(0);

  beginShape();

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

    vertex(orig[i].x,orig[i].y);

  }

  endShape(CLOSE);

  if(polygon.length>2){

    stroke(0)

​

    fill(255)

    beginShape();

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

      vertex(polygon[i].x,polygon[i].y);

    }

    endShape(CLOSE);

    stroke(255,0,0);

    line(polygon[0].x,polygon[0].y,polygon[1].x,polygon[1].y);

    stroke(0,255,0);

    line(polygon[1].x,polygon[1].y,polygon[2].x,polygon[2].y);

  }

  else{

    noStroke();

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

      fill(random()*255)

      beginShape();

      vertex(orig[triangles[i][0]].x, orig[triangles[i][0]].y);

      vertex(orig[triangles[i][1]].x, orig[triangles[i][1]].y);

      vertex(orig[triangles[i][2]].x, orig[triangles[i][2]].y);

      endShape(CLOSE);

    }

    noFill();

    stroke(255,255,0);

    beginShape();

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

      vertex(orig[i].x,orig[i].y);

    }

    endShape(CLOSE);

  }

  fill(0);

  noStroke();

  text('red is the first line, green the second.',0,10);

  text('click right if the polygon is drawn clockwise and left if it is counterclockwise',0,20);

}

​

function mouseClicked(){

  if(mouseX>width/2){

    dir = -1;

  }

  else{

    dir=1;

  }

  if(polygon.length>2){

    earClipper();

  }

}

​

​

function earClipper(){

  // 0 -> 1 angle, 1->2 angle

  for(let i=0; i<polygon.length-2;i++){

      let angle = p5.Vector.angleBetween(

        p5.Vector.sub(polygon[(i+1)%polygon.length],polygon[i]), 

        p5.Vector.sub(polygon[(i+2)%polygon.length],polygon[(i+1)%polygon.length]));

    if(angle * dir < 0.0){

      let found = false;

      for(let j=0;j<polygon.length;j++){

        if(i==j || (i+2)%polygon.length==j || (j+1)%polygon.length==i || (i+2)%polygon.length==(j+1)%polygon.length){

          continue;

        }

        if(checkIntersect(

            polygon[i].x,

            polygon[i].y, 

            polygon[(i+2)%polygon.length].x,

            polygon[(i+2)%polygon.length].y,

            polygon[j].x,

            polygon[j].y,

            polygon[(j+1)%polygon.length].x,

            polygon[(j+1)%polygon.length].y)){

          found = true;

        }

      }

      if(found){

        continue;

      }

      //bounding box check. not very elegant.

      if(polygon.length>3){

        let xmin = min(polygon[i].x,polygon[(i+2)%polygon.length].x, polygon[(i+1)%polygon.length].x);

        let xmax = max(polygon[i].x,polygon[(i+2)%polygon.length].x, polygon[(i+1)%polygon.length].x);

        let ymin = min(polygon[i].y,polygon[(i+2)%polygon.length].y, polygon[(i+1)%polygon.length].y);

        let ymax = max(polygon[i].y,polygon[(i+2)%polygon.length].y, polygon[(i+1)%polygon.length].y);

​

        for (let j=0;j<polygon.length;j++){

          if(polygon[j].x < xmin ||polygon[j].x > xmax ||polygon[j].y < ymin ||polygon[j].y > ymax){

            found = true;

          }

        }

        if(!found){

          continue;

        }

      }

      //we have an ear hehe

      triangles.push([indices[(i  )%polygon.length],

                      indices[(i+1)%polygon.length],

                      indices[(i+2)%polygon.length]])

      indices.splice((i+1)%polygon.length,1)

      polygon.splice((i+1)%polygon.length,1)

      break;

    }

  } 

}