vector[] points;
vector[] b,j,f; //bspline, jarek, fourpoint
int draggedPoint = None;
int currentDepth;
int shapeIndex = 0;
String[] shapes = {"L.txt", "square.txt", "circle.txt"};
static int None = -1;
static int SELECT_THRESHOLD = 7;
boolean TOGGLE_C, TOGGLE_B, TOGGLE_J, TOGGLE_F;

void setup() {
  size(400,400);
  points = new vector[3];
  
  points[0] = new vector(100, 100, 0);
  points[1] = new vector(200, 300, 0);
  points[2] = new vector(300, 200, 0);
  TOGGLE_C = TOGGLE_B = TOGGLE_J = TOGGLE_F = true;
  currentDepth = 3;
  generatePoints(currentDepth);
  ellipseMode(CENTER_DIAMETER);
}

void generatePoints(int depth) {
  b = points;
  j = points;
  f = points;
  currentDepth = depth; //
  genPoints(depth); // The recursive call
}

void genPoints(int depth) {
  if(depth <= 0) return;
  vector[] bsplineOffset = new vector[b.length];
  vector[] jarekOffset = new vector[j.length];
  vector[] fourOffset = new vector[f.length];
  
  // Generate the displacements
  // Though this generates the same values for the first iteration,
  // Thereafter, the control polygon is different, thus displacements are too 
  int i2,i3;
  for(int i = 0; i < b.length; i++) {
    i2 = (i+1)%b.length;  // next
    i3 = (i+b.length-1)%b.length;  // last
    bsplineOffset[i] = b[i].multiply(-0.25).add(b[i2].multiply(0.125)).add(b[i3].multiply(0.125));
    jarekOffset[i] = j[i].multiply(-0.125).add(j[i2].multiply(0.0625)).add(j[i3].multiply(0.0625));
    fourOffset[i] = f[i].multiply(0.25).add(f[i2].multiply(-0.125)).add(f[i3].multiply(-0.125));
  }
  
  vector[] bnew = new vector[b.length*2];
  vector[] jnew = new vector[b.length*2];
  vector[] fnew = new vector[b.length*2];
  
  //old verticies
  for(int i = 0; i < bnew.length; i+=2) {
    i2 = i/2; //old
    bnew[i] = b[i2].add(bsplineOffset[i2]);
    jnew[i] = j[i2].add(jarekOffset[i2]);
    fnew[i] = f[i2];
  }

  //new edges
  for(int i = 1; i < bnew.length; i+=2) {
    i2 = (i-1)/2;  // last
    i3 = (i2+1)%b.length;  // next
    bnew[i] = (b[i2].add(b[i3])).multiply(0.5);
    jnew[i] = (j[i2].add(j[i3])).multiply(0.5).add(jarekOffset[i2].add(jarekOffset[i3]).multiply(-0.5));
    fnew[i] = (f[i2].add(f[i3])).multiply(0.5).add(fourOffset[i2].add(fourOffset[i3]).multiply(0.5));
  }
  
  b = bnew;
  j = jnew;
  f = fnew;
  
  genPoints(depth-1);
}


// Return the index of the closest edge to a point
// This index will also be the index of the first vertex of this edge
int getClosestEdgeIndex(vector point_) {
  int minIndex = -1, j;
  float minDist = Float.MAX_VALUE, distance, t;
  vector seg;
  for(int i = 0; i < points.length; i++) {
    j = (i+1)%points.length;
    seg = points[j].subtract(points[i]);
    t = seg.dot(point_.subtract(points[i]))/seg.dot(seg);
    if(t < 0) {
      distance = point_.subtract(points[i]).length();
    } else if(t > 1) {
      distance = point_.subtract(points[j]).length();
    } else {
      //distance = (points[j].subtract(points[i]).cross(points[j].subtract(point_)).length())
      //         / (points[j].subtract(points[i]).length());
      distance = point_.subtract(points[i].add(seg.multiply(t))).length();
    }
    if(distance < minDist) {
      minDist = distance;
      minIndex = i;
    }
  }
  return minIndex;
}

// Add a new point at x,y
// Use getClosetEdgeIndex to find where to put in sequence
// Then expand the array and copy over verticies
// Finally return the index of the new vertex
int addPoint(float x, float y) {
  int preindex = getClosestEdgeIndex(new vector(x,y,0.0));
  
  vector preVert, newVert, postVert;
  preVert = points[preindex];
  postVert = points[(preindex+1)%points.length];
  newVert = new vector(x,y,0.0);
  
  //copy first half
  vector[] newpoints = new vector[points.length+1];
  for(int i = 0; i <= preindex; i++) {
    newpoints[i] = points[i];
  }
  
  newpoints[preindex+1] = newVert;
  
  //copy second half
  for(int i = preindex+2; i < newpoints.length; i++) {
    newpoints[i] = points[i-1];
  }
  
  points = newpoints;
  return preindex+1; //index of new vertex
}

int addEndPoint(int x, int y) {
  vector[] newPoints = new vector[points.length + 1];
  
  for(int i = 0; i < points.length; i++) {
    newPoints[i] = points[i];
  }
  newPoints[points.length] = new vector(x, y, 0.0);
  
  points = newPoints; 
  return points.length-1;
}

void mouseDragged() {
  if(draggedPoint != None) {
    points[draggedPoint].x += mouseX-pmouseX;
    points[draggedPoint].y += mouseY-pmouseY;
    generatePoints(currentDepth);
  }
}

void mousePressed() {
  if(draggedPoint == None) {
    float minDistance = SELECT_THRESHOLD;
    int minIndex = None;
    float temp;
    
    for(int i = 0; i < points.length; i++) {
      temp = dist(points[i].x, points[i].y, mouseX, mouseY);
      if(temp < minDistance) {
        minDistance = temp;
        minIndex = i;
      }
    }
    draggedPoint = minIndex;
  } 
  
  if(draggedPoint == None) {
    draggedPoint = addPoint(mouseX, mouseY);
    //draggedPoint = addEndPoint(mouseX, mouseY);
    generatePoints(currentDepth);
  }
}

void mouseMoved() {
  
}

void mouseReleased() {
  draggedPoint = None;
}

void loop() {
  background(255);
  
  //Control Polygon
  if(TOGGLE_C) {
    stroke(0);
    strokeWeight(2.0);
    drawLoop(points);
    strokeWeight(1.0);
  }
  
  //Bspline
  if(TOGGLE_B) {
    stroke(255, 0 ,0);
   drawLoop(b);
  }
  
  //Jarek
  if(TOGGLE_J) {
    stroke(0, 255, 0);
    drawLoop(j);
  }
  
  //Four points
  if(TOGGLE_F) {
    stroke(0, 0, 255);
    drawLoop(f);
  }

  //Control points
  fill(255, 128, 0);
  noStroke();
  for(int i = 0; i < points.length; i++) {
    if(points[i] != null) {
      ellipse(points[i].x, points[i].y, 6.0, 6.0);
    }
   }
}

void drawLoop(vector[] points) {
  if(points.length == 0) return;
  beginShape(LINE_STRIP);
  for(int i = 0; i < points.length; i++) {
    if(points[i] != null)
      vertex(points[i].x, points[i].y);
  }
  vertex(points[0].x, points[0].y);
  endShape();
}

void loadShape(String fileName) {
   String lines[] = loadStrings(fileName); 
   int vertices = Integer.parseInt(lines[0]);
   vector[] newpoints = new vector[vertices];
   
   println("there are " + lines.length + " lines and " + vertices + " vertices"); 
   for (int i = 1; i <= vertices; i++) {
     String currentPoint[] = splitStrings(lines[i]);
     print(i + ". ");
     int x = Integer.parseInt(currentPoint[0]);
     int y = Integer.parseInt(currentPoint[1]);
     println(x + " " + y);
     newpoints[i - 1] = new vector(x, y, 0.0);
   }
   points = newpoints;
   generatePoints(currentDepth);
} 

void saveShape(String fileName) {
   String[] lines = new String[points.length + 1];
   lines[0] = Integer.toString(points.length);

  for(int i = 0; i < points.length; i++) {
    lines[i + 1] = Integer.toString((int) points[i].x) + " " + Integer.toString((int) points[i].y);
  }
  
  saveStrings(fileName, lines);
} 

void keyPressed() {
  if(key == '1') {
    generatePoints(1);
  } else if(key == '2') {
    generatePoints(2);
  } else if(key == '3') {
    generatePoints(3);
  } else if(key == '4') {
    generatePoints(4);
  } else if(key == '5') {
    generatePoints(5);
  } else if(key == ' ') {
    setup();
  } else if(key == 'c') {
    TOGGLE_C = !TOGGLE_C;
  } else if(key == 'b') {
    TOGGLE_B = !TOGGLE_B;
  } else if(key == 'j') {
    TOGGLE_J = !TOGGLE_J;
  } else if(key == 'f') {
    TOGGLE_F = !TOGGLE_F;
  } else if(key == 'o') {
    loadShape(shapes[shapeIndex]);
    shapeIndex = (shapeIndex+1)%shapes.length;
  } else if(key == 's') {
    saveShape("output.txt");
  }
}

//vector class by Mark Luffel
//Written for another project
class vector {
  float x,y,z;
 
  vector(float _x, float _y, float _z) {
    x = _x; y = _y; z = _z;
  }
  
  //Check if vectors are of the same length
  boolean equals(vector that) {
    return this.x == that.x && this.y == that.y && this.z == that.z;
  }
  
  //public String toString() {
  //  return "<"+x+", "+y+", "+z+">";
  //}
  
  //Make the vector length one
  vector normalize() {
    float len = length();
    if(len != 0.0f) {
      len = 1/len;
      return new vector(x*len,
                        y*len,
                        z*len);
    } else {
      return new vector(0.0f, 0.0f, 1.0f);
    }
  }
  
  //Return the length of the vector
  float length() {
    return (float)Math.sqrt(x*x+y*y+z*z);
  }

  //Return the vector resized by a scalar
  vector multiply(float scalar) {
    return new vector(this.x*scalar, this.y*scalar, this.z*scalar);
  }

  //Return the sum of the two vectors
  vector add(vector that) {
    return new vector(this.x+that.x, this.y+that.y, this.z+that.z);
  }

  //Return the difference between the two vectors
  vector subtract(vector that) {
    return new vector(this.x-that.x, this.y-that.y, this.z-that.z);
  }
  
    //Return the dot product of two vectors
  float dot(vector that) {
    return this.x*that.x + this.y*that.y + this.z*that.z;
  }

  //Return the cross product of two vectors
  vector cross(vector that) {
    return new vector(this.y*that.z - this.z*that.y,
    this.z*that.x - this.x*that.z,
    this.x*that.y - this.y*that.x);
  }
  
  //Rotate the vector about a given vector, and angle
  vector rotate(vector axis, float angle) {
    float costheta = (float)Math.cos(angle);
    float cosminus = 1.0f-costheta;
    float sintheta = (float)Math.sin(angle);

    return new vector(
         (axis.x*axis.x*cosminus+costheta)*x + (axis.x*axis.y*cosminus-axis.z*sintheta)*y
           + (axis.x*axis.z*cosminus + axis.y*sintheta)*z,
    
         (axis.x*axis.y*cosminus+axis.z*sintheta)*x + (axis.y*axis.y*cosminus+costheta)*y
           + (axis.y*axis.z*cosminus - axis.x*sintheta)*z, 
    
         (axis.x*axis.z*cosminus-axis.y*sintheta)*x + (axis.y*axis.z*cosminus+axis.x*sintheta)*y
           + (axis.z*axis.z*cosminus + costheta)*z   
      );
  }
  
  //Rotate this vector to the given one by the given amount
  vector rotateToBy(vector to, float amount) {
    float angle = (float)Math.acos((float)this.dot(to));
    vector axis = this.cross(to);
    return this.rotate(axis, angle*amount);
  }
}