/*
 * As described in "Shape: Talking about Seeing and Doing"
 * by George Stiny, 2006
 *
 * pages 334-340
 *
 * With a non-uniform picking of edge split location (biased towards the center).
 * Avoid long regions by placing a maximum ratio on the edge lengths in a region.
 * Picking which region to split proportional to area.
 *
 * Press spacebar to restart, any other key to pause/unpause.
 *
 * While running, the applet picks a random node and attempts to split it.
 * (larger shards are more likely to be picked)
 *
 *  Triangles -> Triangle + Quad
 *  Quad -> Quad + Quad
 *  Quad -> Triangle + Pentagon
 *  Pentagon -> Quad + Pentagon
 *
 */


class Shard {
  List<PVector> verts = new ArrayList<PVector>();
  float area;
}

float AREA_THRESHOLD = 1000;
float EDGE_RATIO_THRESHOLD = 4;

Shard root;
List<Shard> shards = new ArrayList<Shard>();
boolean paused = false;

void draw() {
  smooth();
  background(0);
  fill(235,210,0);
  stroke(255);
  strokeWeight(4);
  for(Shard sh : shards) {
    draw(sh);
  }
  if(!paused) step();
}

void draw(Shard sh) {
  beginShape();
  for(PVector p : sh.verts) {
    vertex(p.x, p.y);
  }
  endShape(CLOSE); 
}

/*
  This is where the good stuff happens.
  Try to split the i-th shard into two pieces.
*/
void expand(int i) {
  Shard sh = shards.get(i);
  List<PVector> verts = sh.verts;
  int len = verts.size();
  // pick how many vertices a cut will span
  int span = 1; // for triangles, always 1
  if(len == 4) {
    if(random(0, 1.) < 0.5) span = 2; // for quads, equal probability
  } else if(len == 5) {
    span = 2; // for pentagons, always 2
  }
  // pick which edge to split
  int splitL = (int)random(0, len);
  // the second edge to split is defined as an offset given by the span
  int splitR = (splitL+span)%len;
  // pick locations along these edges to split, biased towards the center
  PVector Lv = lerp(verts.get(splitL), verts.get((splitL+1)%len), randomSplit());
  PVector Rv = lerp(verts.get(splitR), verts.get((splitR+1)%len), randomSplit());
  
  // build R region
  Shard R = new Shard();
  R.verts.add(Lv);
  int v = splitL;
  while(v != splitR) {
    v = (v+1)%len;
    R.verts.add(verts.get(v));
  }
  R.verts.add(Rv);
  R.area = area(R);
  float areaL = sh.area-R.area;
  // check if the resulting regions will have acceptable areas
  // quit if not
  if(R.area < AREA_THRESHOLD || areaL < AREA_THRESHOLD || maxEdgeRatio(R) > EDGE_RATIO_THRESHOLD) return;
  // otherwise, build L region too
  Shard L = new Shard();
  L.verts.add(Rv);
  v = splitR;
  while(v != splitL) {
    v = (v+1)%len;
    L.verts.add(verts.get(v));
  }
  L.verts.add(Lv);
  L.area = area(L);
  if(maxEdgeRatio(L) > EDGE_RATIO_THRESHOLD) return; // reject too long regions
  // finally, add the new regions to the shards array
  shards.set(i, L); // overwrite
  shards.add(R); // new
}

void keyPressed() {
  if(key == ' ') {
    dataSetup();
  } else {
    paused = !paused;
  }
}

void step() {
  float[] CDF = new float[shards.size()];
  float prev = 0;
  for(int i = 0; i < CDF.length; i++) {
    prev = CDF[i] = prev+shards.get(i).area; 
  }
  float totalArea = CDF[CDF.length-1];
  int i = Arrays.binarySearch(CDF, random(0, totalArea));
  if(i < 0) { // if the exact value wasn't found, almost always true
    i = -i-1; // transform so that we split the region with that area
  }
  expand(i);
}

PVector lerp(PVector A, PVector B, float t) { // ignore z
  return new PVector(lerp(A.x,B.x,t),lerp(A.y,B.y,t),0);
}

float area(Shard sh) {
  float area = 0;
  for(int i = sh.verts.size()-1, j = 0; j < sh.verts.size(); i = j, j++) {
    PVector a = sh.verts.get(i), b = sh.verts.get(j);
    area += (a.x+b.x)*(a.y-b.y);
  }
  return abs(area)/2;
}

float maxEdgeRatio_weak(Shard sh) {
  float max = 0, min = Float.MAX_VALUE;
  for(int i = sh.verts.size()-1, j = 0; j < sh.verts.size(); i = j, j++) {
    PVector a = sh.verts.get(i), b = sh.verts.get(j);
    float len = a.dist(b);
    if(len > max) max = len;
    if(len < min) min = len;
  }
  return max/min;
}

float maxEdgeRatio(Shard sh) {
  float max = 0, min = Float.MAX_VALUE;
  for(int i = 0; i < sh.verts.size(); i++) {
    for(int j = i+1; j < sh.verts.size(); j++) {
      float len = sqdist(sh.verts.get(i),sh.verts.get(j));
      if(len > max) max = len;
    }
  }
  for(int i = sh.verts.size()-1, j = 0; j < sh.verts.size(); i = j, j++) {
    PVector a = sh.verts.get(i), b = sh.verts.get(j);
    float len = sqdist(sh.verts.get(i),sh.verts.get(j));
    if(len < min) min = len;
  }
  return sqrt(max)/sqrt(min);
}

float sqdist(PVector A, PVector B) {
  return sq(A.x-B.x)+sq(A.y-B.y);
}


float randomSplit() {
  return 0.5 + random(-1,1)*random(-1,1)/2;
}

void setup() {
  size(640, 480);
  dataSetup();
}

void dataSetup() {
  root = new Shard();
  root.verts.add(new PVector(0, 0, 0));
  root.verts.add(new PVector(width-1, 0, 0));
  root.verts.add(new PVector(width-1, height-1, 0));
  root.verts.add(new PVector(0, height-1, 0));
  root.area = area(root);
  shards.clear();
  shards.add(root);
}