// SGraph.java
// by Brian Goldsmith and Alexander Smith
// Adapted from DirectedGraph.java
// Copyright (C) 2000 Linyuan Lu
// Code based on David Binger's Graph.java 
// Copyright (C) 1997 David Binger

import java.io.*;
import java.awt.*;

public class SGraph extends Selectable
{
  //original graph vertices, edges, and faces  
  public List vertices = new List();
  public List edges = new List();
  public List faces = null;
  public double[] r = null;
  public double[] R = null;
  public int[][] connections = null;
  //public double[] s = null;
  //public double[][] AnglesInFaces = null;
  double AvgR = 0, AvgR2 = 0; //AvgR2 = (AvgR)^2
  int greatestVert = -1;
  double greatestDegree = 0;
  boolean positiond = false;
  List backVertices = new List();
  List frontVertices = new List();

  //dual graph vertices, edges and an external face
  public List dualVertices = new List();
  public List dualEdges = new List();
  public Face externalFace;
  public Image dualImg = null;
  private Dimension dualImageSize = new Dimension(0,0);
  private double sumOfAngles; //ok
  private List tempVertices; //ok
  private int quad1=5, quad2=10, quad3=10, quad4=5;
  Vertex highestY=null;
  Vertex lowestY=null;
  Vertex highestX=null;
  Vertex lowestX=null;
  private double Re = .2, re = .001;
 
  public SGraph() { /* blank constructor */ }
  
  public void reset()
  // resets the drawing of the graph
  {
    faces = new List();
    sumOfAngles = 0;
    tempVertices = null;      
    quad1=5;
    quad2=10;
    quad3=10;
    quad4=5;
    highestY=null;
    lowestY=null;
    highestX=null;
    lowestX=null;

  }
  
  public int getE()
  // returns the number of edges in the graph
  {
	int sum=0;
	int n=vertices.length;
	Object a[]=vertices.elements;
	for(int i=0;i<n;i++){
	    sum += ((Vertex) a[i]).inDegree();
	}
	return sum;
  }

  public final Vertex vertex(int n)
  /* return vertex [n] */
  {
    return ((Vertex)(vertices.elements[n]));
  }
  
  public final int vertexPosition(Vertex v)
  // returns index n of given vertex
  // found at vertices.elements[n]
  {
    int n = -1;
    for(n=0;n< vertices.length; n++){ 
      if(v.Compare((Vertex)vertices.elements[n])) return n;
    }
    return -1;
  }

  public final Edge edge(int n)
  /* return edge [n] */
  {
    return ((Edge)(edges.elements[n]));
  }

  public final Vertex addVertex(Vertex v)
  /* addVertex ( v ) */
  {
    vertices.push(v);
    return v;
  }

  public final Vertex addVertex()
  /* add blank vertex */
  {
    Vertex v = new Vertex();
    vertices.push(v);
    return v;

  }

  public final Vertex addVertex(int x,int y)
  /* addVertex with coordinates (x,y) */
  {
    Vertex v = new Vertex(x,y);
    vertices.push(v);
    return v;
  }

  public final void delEdge(Edge e) {
    e.start.delOutEdge(e);
    e.end.delInEdge(e);
    edges.delete(e);
  }

  public final void delVertex(Vertex v) {
     int n = v.inedges.length;
    Object a[] = v.inedges.elements;
    for (int j=0;j<n;j++) {
      Edge e = (Edge)a[j];
      edges.delete(e);
      e.start.delOutEdge(e);
    }
    n = v.outedges.length;
    Object b[] = v.outedges.elements;
    for (int j=0;j<n;j++) {
      Edge e = (Edge)b[j];
      edges.delete(e);
      e.end.delInEdge(e);
    }
    
    vertices.delete(v);
  }
  
  public final Edge addEdge(Vertex a, Vertex b) {
    Edge e = new Edge(a,b);
    int n=edges.length;
    Object x[]=edges.elements;
    for(int i=0;i<n;i++){
	if(e.start.equals(((Edge)x[i]).start)&&
	   e.end.equals(((Edge)x[i]).end)){
	    ((Edge)x[i]).multi+=e.multi; 
	    a.addOutEdge(e); 
	    b.addInEdge(e);
	    return ((Edge)x[i]);
	}
    }
     edges.push(e);
     a.addOutEdge(e); 
     b.addInEdge(e);
      return e;
  }

  public final Edge addEdge(int a,int b) {
    Vertex v1 = (Vertex)vertices.elements[a];
    Vertex v2 = (Vertex)vertices.elements[b];
    Edge edge = addEdge(v1,v2);    
    return edge;
  }    

  public String toString() {
    String s = "(graph\n";
    s += vertices.toString() +"\n";
    s += edges.toString();
    s = s +"\n)";
    return s;
  }
  
  public final void paint(Graphics g) {
    if(positiond)
        uberPaint(g);
    else {
      int n = edges.length;
      Object x[] = edges.elements;
      int j;

      for (j=0;j<n;j++)
        ((Edge)x[j]).paint(g);
      n = vertices.length;
      x = vertices.elements;
      for (j=0;j<n;j++)
        ((Vertex)x[j]).paint(g);
      for (j=0;j<n;j++)
        ((Vertex)x[j]).paintLabel(g);
      n = edges.length;
      x = edges.elements;
      for (j=0;j<n;j++)
        ((Edge)x[j]).paintLabel(g);
    }
  }

  // Move vertices and edges.
  public final void moveRelative(double x,double y) {
    int n = edges.length;
    Object a[] = edges.elements;
    int j;
    for (j=0;j<n;j++)
      ((Edge)a[j]).moveRelative(x,y);
    n = vertices.length;
    a = vertices.elements;
    for (j=0;j<n;j++)
      ((Vertex)a[j]).moveRelative(x,y);
  }

  //checking if two edges are crossing
    public boolean isCrossing(Edge e1, Edge e2){
        if(e1.start==e2.start
           || e1.start==e2.end
           || e1.end==e2.start
           || e1.end==e2.end) return false;

        double s,t; //the affine coordinates respect to e1=AB and e2=CD.
        double e1x=e1.start.position.x - e1.end.position.x; // e1x is x coodinates of A-B.
        double e1y=e1.start.position.y - e1.end.position.y; // e1y is y coodinates of A-B.
        double e2x=e2.start.position.x - e2.end.position.x; // e2x is x coodinates of C-D.
        double e2y=e2.start.position.y - e2.end.position.y; // e2y is y coodinates of C-D.

        double dbx=e2.end.position.x-e1.end.position.x; // dbx is x coodinates of D-B.
        double dby=e2.end.position.y-e1.end.position.y; // dby is y coodinates of D-B.

        double determint=e1x * e2y - e1y * e2x;
        if(determint <0.001 && determint >0.001)
            return false; // e1 and e2 are parallel.
        s = (dbx * e2y -dby * e2x)/determint;
        t = (dbx * e1y -dby * e1x)/determint;
        if(0<s && s<1 && 0<t && t<1) return true;
        else return false;
    }


  /***********************************************************/
  /* addFaceIntoList:                                        */   
  /*        This function will add a face into a list of     */
  /*        faces if the face doesn't exist                  */
  /***********************************************************/
  private final void addFaceIntoList(Face f)
  {
        Face thisFace;
        if (faces.length == 0)
            faces.push(f);
        else
        {
            for (int i=0; i < faces.length; i++)
            {
                thisFace = (Face)(faces.elements[i]);
                //face already exist in the list
                if (thisFace.Compare(f))
                    return;
                //add new list
            }
            faces.push(f);
        }
  }

  public Vertex findMidPoint (Vertex v2, Vertex v3,Edge e1)
  {
        Vertex v1, v;        
        double x,y;
        //determine vertex 1
        if (v2.Compare(e1.start))
            v1 = e1.end;
        else   
            v1 = e1.start;
        
        x = (v1.position.x + v2.position.x + v3.position.x) / 3;
        y = (v1.position.y + v2.position.y + v3.position.y) / 3;
        
        v = new Vertex(0,0);
        v.position.x = x;
        v.position.y = y;
        
        return v;
  }

  public Face findFace(Vertex origin, Edge currentEdge, Vertex currentVertex)
  {
        //find the angle for the given edge
        double angle = currentEdge.angle(currentVertex);
        Face f;
        Vertex newEndPoint, midPoint=null;
        Edge e, edgeWithLargestAngle = null, rightNearestEdge = null;
                //Note: the rightNearestEdge is the edge to the right of the current edge,
                //      clockwise direction.

        //the currentVertex contains a list of outedges
        for (int i=0; i < currentVertex.myedges.length; i++)
        {
            //find the edge that has the angle smaller than the angle of the 
            //given edge
            e = (Edge)(currentVertex.myedges.elements[i]);
            if (!((e.start.Compare(currentEdge.start) && e.end.Compare(currentEdge.end)) ||
                (e.start.Compare(currentEdge.end) && e.end.Compare(currentEdge.start)) ||
                (e.end.Compare(currentEdge.start) && e.start.Compare(currentEdge.end))))
            {    
                if (angle > e.angle(currentVertex))
                {
                    if (rightNearestEdge == null)
                        rightNearestEdge = e;
                    else
                    {
                        //find the edge that has the largest angle than other edges
                        //which have the angle less than the angle of the current edge
                        if (rightNearestEdge.angle(currentVertex) < e.angle(currentVertex))
                            rightNearestEdge = e;
                    }
                }
                //find the edge that has the largest angle
                else
                {
                    if (edgeWithLargestAngle == null)
                        edgeWithLargestAngle = e;
                    else
                    {
                        if (edgeWithLargestAngle.angle(currentVertex) < e.angle(currentVertex))
                            edgeWithLargestAngle = e;
                    }
                }
            }
        }

        //if e equals null then we will use the edge that has largest angle;
        //otherwise use the edge that is nearest to the current edge
        if (rightNearestEdge != null)
            e = rightNearestEdge;
        else
            e = edgeWithLargestAngle;

        if (e == null) return null;
        
        //compute the new endpoint
        if (currentVertex.Compare(e.start))
            newEndPoint = e.end;
        else
            newEndPoint = e.start;
            
        //compute the angle between the given edge and the right nearest edge
        //add the angle into the total angle of a face
        if (rightNearestEdge == null)
            sumOfAngles = sumOfAngles + (angle + (360 - edgeWithLargestAngle.angle(currentVertex)));
        else
            sumOfAngles = sumOfAngles + (angle - rightNearestEdge.angle(currentVertex));

        //check to see if the currentVertex equals to the origin, if it is 
        //then the face is completed
        if (newEndPoint.Compare(origin))
        {            
            tempVertices.push(currentVertex);
            midPoint = findMidPoint(currentVertex,newEndPoint,currentEdge);
            //add the sum of angle into the face
            f = new Face(tempVertices,sumOfAngles,midPoint);
            //reset the sum of angle
            sumOfAngles = 0;
            return f;
        }
        else
        {
            //add the current vertex into a list of vertices which are used to
            //determine the face
            tempVertices.push(currentVertex);
            return findFace(origin,e,newEndPoint);
        }
  }
    
  /***********************************************************/
  /* computeFaces:                                           */   
  /*        Determine all the faces for the given graph      */
  /***********************************************************/
  public final void computeFaces()
  {
        Vertex v,endVertex;
        Edge e;
        Face newFace = null;
        
        //clear out the old list of faces
        faces = new List();
        //For each vertex, find all the faces
        for (int i=0; i < vertices.length; i++)
        {
            v = (Vertex)(vertices.elements[i]);
            //For each vertex, there are outedges connected to the vertex    
            for (int j=0; j < v.myedges.length; j++)
            {
                e = (Edge)(v.myedges.elements[j]);
                tempVertices = new List();
                //first point of the face
                tempVertices.push(v);

                //determine the end point of the edge
                if (v.Compare(e.start))
                    endVertex = e.end;
                else
                    endVertex = e.start;

                //find new face 
                newFace = findFace(v,e,endVertex);    

                //add new face into the list of faces
                if (newFace != null)
                    addFaceIntoList(newFace);                
            }
        }
        
  }

  public void initAvgR(){
        //declare variables
	int i = 0, n = vertices.length;
	double r2 = 0, x = 0, x2 = 0, totalR = 0;
        double d = 0;
	Vertex v = null;
        
        // initialize arrays for r & R and sum of all phi for vert n,
        // and storing angles in each face, to help with visualization
        r = new double [n];
	R = new double [n];
	//s = new double [n];
	//AnglesInFaces = new double[faces.length][3];
        connections = new int [n][];
	// go through vertices and get degrees
	// set weight and get radius
	// also get the total radius for the avg 

	for(i=0; i < n; i++){
	  // set the vertex
	  v = ((Vertex)vertices.elements[i]);
          //initialize connections[i] for each vertex
          connections[i] = connectArr(v);
          //get degrees
          d = (double)v.getDegree();
          if(d < 5) {
            r[i] = .5;
          }
          else r[i] = d/10; 
          // get the radius Rv
          r2 = r[i] * r[i];
          x2 = 1/(8*(1 - Math.cos((2*Math.PI)/d)));
          R[i] = Math.sqrt(x2*r2/(r2 - x2));
          // add total radius, to computer average radius
	  totalR += R[i];
	  //check if this vertex has greatest degree
	  if(d > greatestDegree) {
	    greatestDegree = d;
	    greatestVert = i;
	  }
        }
        
        // store that average radius
        AvgR = (totalR / n);
        //do one step, without r[i] adjusting, to init total Phi for all vert
	step(1, true);
  }

  public void step(int c, boolean start)
  {
	int count = 0;
        for(count=0; count < c; count++)
          checkR();
  }
  
  public int infStep()
  {
 	boolean flag = true;
	int i = 0, count = 0, n = vertices.length;
	double t = 0;
        
	// step i
	while(flag){
            count++;
            checkR();
            flag = false;
            for(i=0; i<n; i++) {
                t = R[i] - AvgR;
                if((t > .0001)||(t < -.0001))
                    flag = true;
            }
        }
	return count; //returns # of iterations
  }
  
  public void checkR() {
      //recalculate R[i], adjust if necessary
      double totalR = 0, d = 0, rv2 = 0, t = 0;
      int n = vertices.length, i = 0;
      Vertex v = null;
      
      for(i=0; i < n; i++){
	r[i] += .1 *(R[i] - AvgR);
        //get current vertex to get its degrees to calculate the new Rv
        v = ((Vertex)vertices.elements[i]);
        //get degrees
        d = (double)v.getDegree();
        rv2 = r[i] * r[i]; //store (rv)^2
        t = 1/(8*(1 - Math.cos((2*Math.PI)/d))); //t = x2 in algorithm
        R[i] = Math.sqrt(t*rv2/(rv2 - t));
        //add to totalR to recalc the avgR
        totalR += R[i];
      }
      //recalc AvgR;
      AvgR = (totalR / n);
  }
  
  public double getAvgR() { return AvgR;}
  
  /*
   * sets tArea to info of graph formatted like how a read-in file would look:
   * - # of vertices
   * - list of connections for each vertex
   * - vertices in each face
   */
   public void writeInfo(boolean initd)
  {
    int i = 0, j = 0, d = 0, p = 0;
    Edge e = null;
    Vertex v = null;
    Face f = null;
    String output = vertices.length + " Vertices\n";
    output += "Vert " + greatestVert + " has greatest degree of "
		+ greatestDegree +"\n";
    // list all connections for each vertex
    output += "-- Listing Edges for each Vertex --\n";
    for(i = 0; i < vertices.length; i++) {
      output += i + " @ " + vertex(i).position.toString()+" :";
      for(j = 0; j < connections[i].length; j++)
        output += " " + connections[i][j];
      output += "\n";
    }
    if(initd) { //only list face stuff if graph has been initialized
      output += "-- Listing Vertices for each Face --\n";
      for (i = 0; i < faces.length; i++) { //for each face
        f = (Face)faces.elements[i];
        output += i + " :";
        for (j = 0; j < f.faceVertices.length; j++) { //for each vertex in face
          output += " " + vertexPosition((Vertex)(f.faceVertices.elements[j]));
        }
        output += "\n";
      }
    }
    else {
      output += "** Graph must be Initialized to show Face info **\n";
    }
    
    GraphApplet.tArea.setText(output);
  }
  
  public void writeSteiny(String in)
  {
    int i = 0;
    double Ri = 0, ri = 0, fi = 0;
    String output = in +"\nAvgR = " + AvgR+ "\n";
    
    for(i = 0; i < vertices.length; i++) {
      Ri = R[i];
      ri = r[i];

      output += "V[" +i+ "] : Rv=" +Ri+ "  rv=" +ri+ "\n";
    }
    GraphApplet.tArea.setText(output);
  }

  public void writeCoord()
  {
    String output = "";
    Vertex v = (Vertex)vertices.elements[greatestVert];
    output += "Greatest Vert : V[" + greatestVert +"] at "
      +v.position.toString()+" connected to :"+connectString(v)+"\n";
    cStep0();
    output += "After cStep0 :\n"+coordsInString();
    cStep1(greatestVert);
    output += "After cStep1 around greatestVert V["+greatestVert+"] :\n";
    output += coordsInString();
    cStepI(greatestVert);
    output += "After cStepI then :\n";
    for(int i=0; i< vertices.length; i++) {
      v = vertex(i);
      output += "V["+i+"] theta = "+v.theta+"\n";
    }
    output += "...which might make the coordinates at :\n" + coordsInString();
    GraphApplet.tArea.setText(output);
    doIt();
  }
  public String coordsInString()
  {
    String output = "";
    Vertex v;
    
    diskX = xCenter - (int)(AvgR*Scale);
    diskY = yCenter - (int)(AvgR*Scale);
    diskD = (int)(2*AvgR*Scale);
    
    for(int i=0; i< vertices.length; i++) {
	v = vertex(i);
        if(blocked(v))
          output += "*HIDDEN* ";

	output += "V["+i+"] @ ( "+v.x+" , "+v.y+" , "+v.z+" )\n";
    }
    return output;
  }
  public String connectString(Vertex v)
  {
    String output = "";
    int[] arr = connectArr(v);
    for(int i=0; i<arr.length; i++)
	output += " " + arr[i];

    return output;
  }
  public int[] connectArr(Vertex v)
  {
    int n = v.getDegree();
    int[] output = new int[n];
    int i=0,j=0,p=0;
    double[] ang = new double[n];
    double a=0;
    Edge e;
    for(i=0; i < v.outDegree(); i++) { //for each edge w/ e.start = v
      e = v.outEdge(i);
      p = vertexPosition(e.end);
      output[i] = p;
      ang[i] = e.angle(e.end);
    }

    for(j = 0; j < v.inDegree(); j++) { //for each edge w/ e.start = v
      e = v.inEdge(j);
      p = vertexPosition(e.start);
      output[j + i] = p;
      ang[j + i] = e.angle(e.start);
    }
    /* so output has connected vertices[0 ... n], ang has angles from v to them
     * so we want to bubblesort output[] based on ang[] (i think) */
    for(i=n; i >= 0; i--) {
      for(j=0; j < i-1; j++) {				
        if(ang[j] > ang[j+1]) {
	  p = output[j];
	  output[j] = output[j+1];
	  output[j+1] = p;
          a = ang[j];
	  ang[j] = ang[j+1];
	  ang[j+1] = a;
        }
      }
    }
    return output;
  }  
  public void cStep0()
  {
    int n = vertices.length;
    AvgR2 = AvgR * AvgR;
    Vertex v;
    double d = 0;
    for(int i=0; i<n; i++) { //send each pt to (0,0,di)
	d = Math.sqrt(AvgR2 + r[i]*r[i]);
	((Vertex)(vertices.elements[i])).z = d;
    }
  }
  public void cStep1(int v0pos)
  {
    Vertex v0 = vertex(v0pos);
    int[] vArr = connections[v0pos]; //vArr set with vertices connected to v0
    double r0 = r[v0pos], d0 = v0.z, di=0, zi=0; 
    
    for(int i=0; i<vArr.length; i++) { //send each other pt to (xi,0,zi)
	di = ((Vertex)(vertices.elements[vArr[i]])).z;
	zi = (AvgR2 - (r0 * r[vArr[i]]))/d0;
	((Vertex)(vertices.elements[vArr[i]])).z = zi;
	((Vertex)(vertices.elements[vArr[i]])).x = Math.sqrt(di*di - zi*zi);
    }
  }
  public void cStepI(int v0pos)
  {
    Vertex vC = vertex(v0pos), vP;
    vC.placed = true;
    int[] vArr = connections[v0pos]; //vArr set with vertices connected to v0
    if(vArr.length > 1) {
      double T=0,zD=0, tC=0, xC=0, zC=0, tP=0, xP=0, zP=0, rSum = 0;
      int c=0, p=0;
      for(int i=1; i<vArr.length; i++) {
        c = vArr[i];
        vC = (Vertex)(vertices.elements[c]);
        p = vArr[i-1];
        vP = (Vertex)(vertices.elements[p]);
	xC = vC.x;
	zC = vC.z;
	tP = vP.theta;
	xP = (vP.x)/Math.cos(tP);
	zP = vP.z;
	zD = zC - zP;
        rSum = r[c] + r[p];
	T = (zD*zD + xC*xC + xP*xP - rSum*rSum)/(2*xC*xP);
        tC = tP + Math.acos(T);
	vC.theta = tC;
	vC.x = xC * Math.cos(tC);
	vC.y = xC * Math.sin(tC);
        vC.placed = true;
      }
    }
    ((Vertex)(vertices.elements[vArr[0]])).placed = true;
  }

  public void doIt()
  {
    double Y = 0, Z = 0;
    Vertex v = null;
    for(int i=0; i < vertices.length; i++) {
        v = (Vertex)vertices.elements[i];
        Y = v.y;
	Z = v.z;
	v.position.x = Scale*Y + xCenter;
	v.position.y = -1*Scale*Z + yCenter;
    }
    positiond = true;
  }
  public void spin()
  {
    //rotate each point by spinAmount around z-axis
    Vertex v = null;
    double oldX = 0, oldY = 0, oldTheta = 0;
    for(int i=0; i < vertices.length; i++) {
      v = (Vertex)vertices.elements[i];
      oldTheta = v.theta;
      oldX = v.x/Math.cos(oldTheta);
      oldY = v.y/Math.sin(oldTheta);
      v.theta = oldTheta + spinAmount;
      v.x = oldX * Math.cos(v.theta);
      v.y = oldX * Math.sin(v.theta);
    }
    doIt();
  }
  public void zoom(boolean in)
  {
    if(in)
      Scale = (int)(Scale * zoomAmount);
    else
      Scale = (int)(Scale / zoomAmount);
      
    doIt();
  }
  public boolean blocked(Vertex v) {
    double X = v.position.x, Y = v.position.y;
    return ((X > diskX)&&(X < (diskX + diskD))&&(Y > diskY)&&(Y < (diskY + diskD))&&(v.x <= 0));
  }
  
  public final void uberPaint(Graphics g) {
    
    diskX = xCenter - (int)(AvgR*Scale);
    diskY = yCenter - (int)(AvgR*Scale);
    diskD = (int)(2*AvgR*Scale);
    
    int n = edges.length;
    Object x[] = edges.elements;
    Vertex v = null;
    Edge e = null;
    int i=0, j=0;

      /* for (j=0;j<n;j++)
        ((Edge)x[j]).paint(g); */
    n = vertices.length;
    x = vertices.elements;
    for (j=0;j<n;j++) {
      v = (Vertex)x[j];
      if(blocked(v))
        for(i=0; i<v.myedges.length; i++) {
          e = (Edge)v.myedges.elements[i];
          //if(e.alreadyDrawn == false) {
            e.paint(g);
            e.alreadyDrawn = true;
          //}
        }
    }
    g.setColor(Color.cyan);
    g.fillOval(diskX, diskY, diskD, diskD);
    
    for (j=0;j<n;j++) {
      v = (Vertex)x[j];
      if(!blocked(v)) {
        v.paint(g);
      }
    }
    //paint the rest of the edges
    n = edges.length;
    x = edges.elements;
    for (j=0;j<n;j++) {
      e = (Edge)x[j];
      if(e.alreadyDrawn == false)
        e.paint(g);
        
      //reset all alreadyDrawn fields
      e.alreadyDrawn = false;
    }
  }
  
  public static final int xCenter = 305;
  public static final int yCenter = 250; //180;
  public static int Scale = 100;
  public static final double spinAmount = .4;
  public static double zoomAmount = 1.2;
  public static int diskX = 0, diskY=0, diskD=0; //coordinates of corner of sphere, and its diameter
  /* so after avgRadius() is run, we have :
   * FOR VERTICES: 
   *   # of vertices = vertices.length
   *   all vertices in order in vertices.elements[i], 0 <= i < vertices.length
   *   for vertex i, r[i] is correct, and | s[i] - 2PI | <= .0001
   * FOR FACES:
   *   # of faces = faces.length
   *   all faces in order in faces.elements[i], 0 <= i < faces.length
   *   for face i, AnglesInFaces[i][0,1,2] = angles t for three vertices on the face
   */
}