// Phyllotaxy Tiles
// - Jim Bumgardner

int m = 500;     // number of circles
int sz = 590-8;    // width of screen
float radBig = sz/2;
float areaBig = PI*radBig*radBig;
float areaSmall = areaBig/m;
float radSmall = sqrt(areaSmall/PI);

int  py,px;

static final int kMaxEdges  = 30;

int limit=4;

class Edge {
  Vertex p1,p2;
  int idx;
  Edge(Vertex p1, Vertex p2, int n)
  {
    this.p1 = p1;
    this.p2 = p2;
    this.idx = n;
  }
  
  Vertex getOtherPoint(Vertex a)
  {
    if (p1 == a)
      return p2;
    else if (p2 == a)
      return p1;
    else
      return null;
  }
}

class Vertex {
  float  x,y;  // All we really care about for making maze...
  int    idx;
  int    nbrEdges;
  Edge[]  edges;
  float[]  edgeAngles;
  Vertex(float x, float y, int n)
  {
    this.x = x;
    this.y = y;
    this.idx = n;
    this.edges = new Edge[kMaxEdges];
    this.edgeAngles = new float[kMaxEdges];
    this.nbrEdges= 0;
  }

  Vertex getEdgeTarget(Edge e)
  {
    if (e.p1 == this)
      return e.p2;
    else if (e.p2 == this)
      return e.p1;
    else
      return null;
  }

  
   void addEdge(Edge edge)
  {
    this.edges[this.nbrEdges] = edge;
    Vertex p2 = edge.getOtherPoint(this);
    
    edgeAngles[this.nbrEdges] = (float) (Math.atan2(p2.y - this.y, 
                                                    p2.x - this.x));
    this.nbrEdges++;
    // println("Adding edge " + this.nbrEdges + " (" + edge.idx + ") to point " + this.idx);
  }
  
  void sortEdges()
  {
    for (int i = 1; i < nbrEdges; ++i)
    {
      float t = edgeAngles[i];
      Edge te = edges[i];
      int j;
      for (j = i-1; j >= 0 && edgeAngles[j] > t; --j)
      {
        edgeAngles[j+1] = edgeAngles[j];
        edges[j+1] = edges[j];
      }
      edgeAngles[j+1] = t;
      edges[j+1] = te;
    }
  }
  
  boolean sharesEdge(Vertex b)
  {
    for (int j = 0; j < nbrEdges; ++j) {
      if (edges[j].p1 == b || edges[j].p2 == b)
        return true;
    }
    return false;
  }

  Vertex getSharedPoint(Vertex partner, Vertex exclude)
  {
    // for each edge
    for (int j = 0; j < nbrEdges; ++j) 
    {
      // if the other point in the edge shares an edge with partner, and is not exclude
      Vertex d = getEdgeTarget(edges[j]);
      if (d != exclude && d.sharesEdge(partner))
      {
        return d;    // return the other point
      }
    }
    return null;
  }
}

class Poly {
  Vertex[]  vertices;  // could be edges or vertices
  
  Poly(Vertex a, Vertex b, Vertex c)
  {
    this.vertices = new Vertex[3];
    vertices[0] = a;
    vertices[1] = b;
    vertices[2] = c;
    fill(128+random(32),128+random(32),255);
    triangle(a.x,a.y,b.x,b.y,c.x,c.y);
  }

  Poly(Vertex a, Vertex b, Vertex c, Vertex d)
  {
    this.vertices = new Vertex[4];
    vertices[0] = a;
    vertices[1] = b;
    vertices[2] = c;
    vertices[3] = d;
    fill(255,128+random(32),128+random(32));
    quad(a.x,a.y,b.x,b.y,c.x,c.y,d.x,d.y);
  }
}

Vertex[] pts = new Vertex[m];
Edge[] edgeList = new Edge[m*20];
Poly[] polyList = new Poly[m*2];
int gNbrEdges;
int gNbrPolys;

void setup()
{
  size(sz,sz);
  smooth();
  println("radBig: " + radBig);
  println("areaBig: " + areaBig);
  println("areaSmall: " + areaSmall);
  println("radSmall: " + radSmall);

  makeSpiral(limit,false);
}

boolean hasEdge(Vertex a, Vertex b)
{
  for (int i = 0; i < gNbrEdges; ++i)
  {
    if (edgeList[i].p1 == a && edgeList[i].p2 == b)
      return true;
    else if (edgeList[i].p1 == b && edgeList[i].p2 == a)
      return true;
  }
  return false;
}

boolean hasPoly(Vertex a, Vertex b, Vertex c)
{
  for (int p = 0; p < gNbrPolys; ++p)
  {
    int matchFlags = 0;
    Poly pp = polyList[p];
    Vertex[] vv = pp.vertices;
    for (int v = 0; v < vv.length; ++v)
    {
      if (vv[v] == a)
        matchFlags |= 1;
      else if (vv[v] == b)
        matchFlags |= 2;
      else if (vv[v] == c)
        matchFlags |= 4;
      if (matchFlags == 7)
        return true;
    }
  }
  return false;
}

void makeSpiral(int limit, boolean makePolys)
{
  background(0);
  float cx = sz/2;
  float phi = (sqrt(5)+1)/2 - 1; // golden ratio
  float ga = phi*2*PI;           // golden angle
  float cumArea = 0;

  ellipseMode(CENTER_RADIUS);
  noStroke();

  for (int i = 0; i < m; ++i)
  {
    cumArea += areaSmall;
    float cumRad = sqrt(cumArea/PI);
    float a = i*ga;
    float d = (float) Math.log(1+i*(Math.E-1)/m);
    float x = sz/2 + sin(a)*cumRad;
    float y = sz/2 + cos(a)*cumRad;
    fill(64+random(64));
    ellipse(x,y,radSmall,radSmall);
    pts[i] = new Vertex(x,y, i);
  }
  // println("Final Rad: " + sqrt(cumArea/PI));
  py = 0;
  px = 0;
  
  
  stroke(255);
  strokeWeight(.5);

  edgeList = new Edge[m*limit];
  polyList = new Poly[m*2];
  gNbrEdges = 0;
  gNbrPolys = 0;
  for (int i = 0; i < m; ++i) 
  {
    Vertex a = pts[i];
    float x1 = pts[i].x;
    float y1 = pts[i].y;
    int[] c = findNClosest(x1,y1,limit+1);
    for (int j = 1; j <= limit; ++j) 
    {
      Vertex b = pts[c[j]];
      float dx = b.x - a.x;
      float dy = b.y - a.y;
      float dst = sqrt(dx*dx+dy*dy);
      if (!hasEdge(a,b) && dst < radSmall*2.5)
      {
        float x2 = b.x;
        float y2 =b.y;
        line(x1,y1,x2,y2);
        edgeList[gNbrEdges] = new Edge(a, b, gNbrEdges);
        gNbrEdges++;
      }
    }
  }
  println(gNbrEdges + " edges");
  stroke(255,0,0);
  int nbrTris=0;
  int nbrQuads=0;
  int aEdges = 0;
  if (makePolys) 
  {
    // collect and sort edges
    int maxEdges = 0;
    for (int i = 0; i < m; ++i)
    {
      Vertex pp = pts[i];
      int en = 0;
      for(int j =0 ; j < gNbrEdges; ++j) {
        if (edgeList[j].p1 == pp|| edgeList[j].p2 == pp) {
          line(edgeList[j].p1.x,edgeList[j].p1.y,
               edgeList[j].p2.x,edgeList[j].p2.y);
          pp.addEdge(edgeList[j]);
          aEdges++;
          en++;
        }
      }
      if (en > maxEdges)  maxEdges = en;
      // Sort Edges by angle of ray
      pp.sortEdges();
    }
    println("Max Edges touching a vertex: " + maxEdges);
    println("Attached Edges: " + aEdges);
    noStroke();
    // for each point A
    for (int i = 0; i < m; ++i)
    {
      // for each edge on vertex
      Vertex pA = pts[i];
      for (int j = 0; j < pA.nbrEdges; ++j)
      {
        // form angle with next clockwise edge, points B,C
        Vertex pB = pA.edges[j].getOtherPoint(pA);
        Vertex pC = pA.edges[(j+1)%pA.nbrEdges].getOtherPoint(pA);
        // if 3 pts are not contained within an existing poly
        if (!hasPoly(pA,pB,pC))
        {
          // check if an edge connects B,C, if so make a triangle
          if (pB.sharesEdge(pC))
          {
            // Make Triangle poly from pA,pB,pC
            polyList[gNbrPolys++] = new Poly(pA,pB,pC);
            ++nbrTris;
          }
          else {
             Vertex pD = pB.getSharedPoint(pC,pA);            
            // otherwise, check if B,C have another point D (besides A) in common,
            if (pD != null) {
              polyList[gNbrPolys++] = new Poly(pB,pA,pC,pD);
              ++nbrQuads;
            }
            else {
              // color bad angles..
              // fill(255,0,255);
              // triangle(pA.x,pA.y, pB.x, pB.y, pC.x, pC.y);
            }
            // if so, make a quad A,B,D,C
          }
        }
        else {
              // fill(255,255,0);
              // triangle(pA.x,pA.y, pB.x, pB.y, pC.x, pC.y);
        }
      }
    }
    println("#Tris: " + nbrTris + ", #Quads: " + nbrQuads + ", total: " + (nbrTris+nbrQuads));    
  }
  
}

int[] findTwoClosest(int px, int py)
{
  int c2=0,c1=1;
  float  d1=100000, d2=100000;
  for (int i = 0; i < m; ++i) 
  {
    float dx = pts[i].x - px;
    float dy = pts[i].y - py;
    float dst = dx*dx+dy*dy;
    if (dst < d1) {
      d2 = d1;
      c2 = c1;
      d1 = dst;
      c1 = i;      
    }
    else if (dst < d2) {
      d2 = dst;
      c2 = i;
    }
  }
  // println("Closest: " + c1 + ", " + c2);
  int[] retVal = {c1,c2};
  return retVal;
}


int[] findNClosest(float px, float py, int n)
{
  int[] c = new int[n];
  float[] d = new float[n];
  for (int i = 0; i < n; ++i)
  {
    c[i] = i;
    d[i] = 10000000;
  }

  for (int i = 0; i < m; ++i) 
  {
    float dx = pts[i].x - px;
    float dy = pts[i].y - py;
    float dst = dx*dx+dy*dy;
    for (int j = 0; j < n; ++j)
    {
      if (dst < d[j]) {
        for (int k = n-1; k > j; --k) {
          d[k] = d[k-1];
          c[k] = c[k-1];
        }
       d[j] = dst;
       c[j] = i;
       break;
      }
    }
  }
  return c;
}

void draw()
{
  if (mousePressed)
  {
    makeSpiral(limit, mousePressed);
  }
/*
 for (int px = 0; px < sz; ++px) {
    int[] closest = findTwoClosest(px,py);
    float dx = pts[closest[0]].x - px;
    float dy = pts[closest[0]].y - py;
    float  dst1 = dx*dx+dy*dy;
    float dx2 = pts[closest[1]].x - px;
    float dy2 = pts[closest[1]].y - py;
    float  dst2 = dx2*dx2+dy2*dy2;
    float cdst = Math.abs(dst2 - dst1);
    fill( cdst > 100? 255 : cdst*255/100);  
    rect(px,py,1,1);
    // println(dst1 + ", " + dst2);
  }
  ++py;
  if (py >= sz)
    py = 0;
*/
}