import java.applet.*;
import java.awt.*;
import java.util.*;

/** Class for representing, embedding and drawing polygon triangulation.
*/

public class PolygonTri {
 
  final int RADIUS = 3; /* radius of circles used for vertices */

  private Polygon poly;  // the polygon in screen space
  private Vector edges;  // triangulation edges interior to polygon
  private Point2d[] points;  // polygon vertices in world space
  private double wxmin;  // min x of window in world space
  private double wymin;  // min y of window in world space
  private double scale;  // scale factor to transform from window to viewport
  private Dimension size; // size of the canvas for drawing (the viewport)
  private Graphics g; // Graphics object for the canvas
  private boolean showCircum; /* should we draw the circumcircles?*/
  private boolean showAngles; /* should we give the angle values*/
  private boolean showVertexLabels; /* should we show vertex labels?*/
  private boolean showDiagonals; /* should we show diagonals?*/
  private boolean showVertices; /* should we show mark vertices?*/
  private int n; /*number of vertices */
  private TreePoly tree;  // tree representation of the triangulated polygon
  TextField bracketsField; // bracket version of polygon displayed here

  //constructor needs to know the number of vertices and where to display
  // the bracket version of the polygon
  public PolygonTri (int n, TextField bracketsField) {
    edges = new Vector(n-1);
    setNoVertices(n);
    this.bracketsField = bracketsField;
  }

  // set the number of vertices and lay the vertices out on the unit circle
  public void setNoVertices(int n) {
    clear();
    if (n != this.n) {
      points = new Point2d[n];
      this.n = n;
      for (int i = 0; i < n; i++){
	double theta = 2*Math.PI*i/n;
	points[i] = (new Point2d(Math.cos(theta), Math.sin(theta)));
      }
    }
    if (size != null) {
      fit();
    }
  }

  // remove all diagonals
  public void clear() {
    edges.removeAllElements();
    tree = null;
  }

  public void setShowCircum(boolean showCircum) {
    this.showCircum = showCircum;
  }

  public void setShowAngles(boolean showAngles) {
    this.showAngles = showAngles;
  }

  public void setShowVertexLabels(boolean showVertexLabels) {
    this.showVertexLabels = showVertexLabels;
  }

  public void setShowDiagonals(boolean showDiagonals) {
    this.showDiagonals = showDiagonals;
  }

  public void setShowVertices(boolean showVertices) {
    this.showVertices = showVertices;
  }

  // set the dimensions of the drawing area
  public void setSize(Dimension size) {
    if (this.size == null ||
	size.width != this.size.width ||
	size.height != this.size.height ) {
      this.size = size;
      fit();
    }
  }

  // centre window on (x,y)
  public void centreView(int x, int y) {
    wxmin += (x-size.width/2)/scale;
    wymin += (y-size.height/2)/scale;
    calcPoly();
  }
  
  // zoom in by a factor 2
  public void zoomIn(int x, int y) {
    scale *= 2;
    centreView(2*x,2*y);
  }
  
  // zoom out by a factor 2
  public void zoomOut(int x, int y) {
    scale /= 2;
    centreView(x/2,y/2);
  }

  public void paint(Graphics g) {
    this.g = g;
    for (int i = 0; i < poly.npoints; i++) {
      if (showVertices) {
	g.drawRect(poly.xpoints[i]-RADIUS, poly.ypoints[i]-RADIUS,
		   2*RADIUS, 2*RADIUS);
      }
      if (showVertexLabels) {
	g.drawString(Integer.toString(i),poly.xpoints[i]+RADIUS+3,poly.ypoints[i]+RADIUS);
      }
    }
    g.drawPolygon(poly);
    int last = poly.npoints - 1;
    g.drawLine(poly.xpoints[last],poly.ypoints[last],
	       poly.xpoints[0],poly.ypoints[0]);

    if (showDiagonals) {
      for (int i = 0; i < edges.size(); i++){
	Edge e = (Edge) edges.elementAt(i);
	g.drawLine(poly.xpoints[e.fst],poly.ypoints[e.fst],
		   poly.xpoints[e.snd],poly.ypoints[e.snd]);
      }
    }

    if (showCircum) {
      paintCircum(n-1,0,tree);
    }

    if (showAngles) {
      paintAngles(n-1,0,tree);
    }
  }

  // returns index of polygon vertex near (x,y)
  public int pick(int x, int y) {
    int selection = -1;
    int mind = Integer.MAX_VALUE;
    for (int i = 0; i < poly.npoints; i++) {
      int d = sqr(poly.xpoints[i]-x) + sqr(poly.ypoints[i]-y);
      if (d < mind) {
	mind = d;
	selection = i;
      }
    }
    return (mind < sqr(2*RADIUS) ? selection : -1 );
  }

  // returns position (in screen space) of vertex i
  public Point getPoint(int index) {
    return new Point(poly.xpoints[index], poly.ypoints[index]);
  }

  // add an edge connecting fst and snd and delete any edges that it crosses
  public void addEdgeDeleteCross(int fst, int snd) {
    for (int i = edges.size() - 1; i >= 0; i--) {
      Edge e = (Edge) edges.elementAt(i);
      // remove crossing edges
      // edges cross if exactly one of fst and snd are between e.fst and e.snd
      if (e.fst < fst && fst < e.snd && (snd < e.fst || snd > e.snd) ||
	  e.fst < snd && snd < e.snd && (fst < e.fst || fst > e.snd)) {
	edges.removeElementAt(i);
	//System.out.println(e.fst+" "+e.snd);
      }
    }    
    tree = null;
    addEdge(fst,snd);
  }

  // add an edge connecting fst and snd assuming there are no intersecting
  // edges
  public void addEdge(int fst, int snd) {
    if (Math.abs(fst-snd) > 1 && Math.abs(fst-snd) < poly.npoints - 1) {
      edges.addElement(new Edge(Math.min(fst,snd), Math.max(fst,snd)));
      if (edges.size()==poly.npoints-3){
	realize();
      }
    }
  }

  //-----end of public methods-----------------------------

  // map vertices of polygon to screen space
  private void calcPoly() {
    poly = new Polygon();
    for (int i = 0; i < points.length; i++){
      Point p = toPoint(points[i]);
      poly.addPoint(p.x,p.y);
    }
  }

  // calculate window so that polygon fills canvas
  private void fit() {
    Point2d first = points[0];
    double xmax = first.x;
    double ymax = first.y;
    double xmin = first.x;
    double ymin = first.y;
    for (int i = 1; i < points.length; i++){
      Point2d p = points[i];
      if (p.x > xmax) {
	xmax = p.x;
      } else if (p.x < xmin) {
	xmin = p.x;
      }
      if (p.y > ymax) {
	ymax = p.y;
      } else if (p.y < ymin) {
	ymin = p.y;
      }
    }
    double xscale = (size.width-2*RADIUS) / (xmax - xmin);
    double yscale = (size.height-2*RADIUS) / (ymax - ymin);
    scale = Math.min(xscale,yscale);
    wxmin = xmin - RADIUS/scale;
    wymin = ymin - RADIUS/scale;
    calcPoly();
  }

  // window -> viewport mapping
  private Point toPoint(Point2d p) {
    return new Point((int)Math.round((p.x-wxmin)*scale),
		    (int) Math.round( (p.y-wymin)*scale));
  }

  // paint circumcircles of all triangles
  private void paintCircum(int a, int b, TreePoly tree) {
    if (tree != null) {
      Point2d centre2d = points[a].circleCentre(points[b],points[tree.c]);
      Point centre = toPoint(centre2d);
      int radius = (int)Math.round(centre2d.subtract(points[a]).length()*scale);
      g.drawOval(centre.x-radius,centre.y-radius,2*radius,2*radius);
      paintCircum(a,tree.c,tree.right);
      paintCircum(tree.c,b,tree.left);
    }
  }
  
  /* paint all the angle values stored in the tree */
  private void paintAngles(int a, int b, TreePoly tree) {
    if (tree != null) {
      int anglesum = tree.Aa+tree.Ba+tree.Ca;
      paintAngle(a,b,tree.c,tree.Ba,anglesum);
      paintAngle(b,tree.c,a,tree.Ca,anglesum);
      paintAngle(tree.c,a,b,tree.Aa,anglesum);
      paintAngles(a,tree.c,tree.right);
      paintAngles(tree.c,b,tree.left);
    }
  }

  /* paint one angle */
  /* We use a few heuristics to place the angle label in a pleasing place */
  private void paintAngle(int a, int b, int c, int angle, int anglesum) {
    String s = Integer.toString(angle);
    FontMetrics fm = g.getFontMetrics();
    int w = fm.stringWidth(s);
    int h = fm.getAscent();
    Point2d ab = points[a].subtract(points[b]);
    Point2d cb = points[c].subtract(points[b]);
    // direction of the centre of label from b
    Point2d d = ab.normalize().add(cb.normalize()).normalize();
    // distance of centre of label from from b
    double dist = Math.min(ab.add(cb).length()/4, //not more than halfway across
    		   Math.min(ab.length()/2,
    		   Math.min(cb.length()/2,
			   h*(0.5+3*(1-angle/(double)anglesum))/scale)));
          //the label for large angles must be close to the vertex,
          // for small angles it must be far
    Point p = toPoint(points[b].add(d.scale(dist)));
    g.drawString(s,p.x-w/2,p.y+h/2);
  }

  

  // square of an int
  static int sqr(int x) {
    return x*x;
  }
    

  // compute vertex positions to realize the triangulation stored in edges
  // takes time O(n) except for initial sorting of edges
  private void realize() {

    // first calculate angle adjacencies
    SortableVector s = new SortableVector();
    for (int i = edges.size() - 1; i >= 0; i--) {
      Edge e = (Edge) edges.elementAt(i);
      s.addElement(e);
      s.addElement(new Edge(e.snd,e.fst));
    }
    for (int i = 0; i < poly.npoints; i++) {
      s.addElement(new Edge(i,(i+1)%poly.npoints));
    }
    int[] ind = s.isort();

    int[] adj = new int[s.size()];
    for (int i = 0; i < s.size()-1; ++i){
      adj[ind[i]] = ind[i+1];
    }
    adj[ind[s.size()-1]] = ind[0];

    int[] next = new int[s.size()];
    for (int i = 0; i < s.size(); ++i){
      int opp = (i < 2*edges.size()) ? i^1 : i;
      next[i] = adj[opp];
      Edge e = (Edge) s.elementAt(i);
    }

    int[] prev = new int[s.size()];
    for (int i = 0; i < s.size(); ++i){
      prev[i] = next[next[i]];
    }

    for (int i = 2*edges.size(); i < s.size(); ++i){
      adj[i] = -1;
    }

    
    // initialize all angles to 0
    int[] a = new int[s.size()];
    for (int i = 0; i < s.size(); ++i){
      a[i] = 0;
    }

    // now calculate angles
    // you need to read my journal paper to understand how this part works
    int i = 0;
    a[i] = a[next[i]] = a[prev[i]] = 1;
    int sum = 3;
    for (int j = 0; j < 2; ++j) {
      do {
	Edge e = (Edge) s.elementAt(i);
	if (adj[i] == -1) {
	  i = next[i];
	} else {
	  i = adj[i];
	  if (a[i] == 0) {
	    int z = a[next[adj[prev[i]]]];
	    a[prev[i]] = a[i] = z + 1;
	    a[next[i]] = sum - z -1;
	    sum = sum + z + 1;
	  } else {
	    a[next[i]] = sum - a[i] - a[prev[i]];
	  }
	}
      } while (i != 0);
    }

    // calculate positions of vertices using the angles we computed
    i = 0;  //this is the edge (n-1)0
    do {
      if (adj[i] == -1) {
	i = next[i];
      } else {
	i = adj[i];
 	Edge e = (Edge) s.elementAt(i);
	Edge f = (Edge) s.elementAt(next[i]);
	Point2d A = points[e.fst];
	double Ca = a[next[i]]*Math.PI/sum;
	Point2d B = points[f.snd];
	double Aa = a[i]*Math.PI/sum;
	double Ba = a[prev[i]]*Math.PI/sum;
	Point2d delta = A.subtract(B);
	double BC = delta.length() * Math.sin(Aa) / Math.sin(Ca);
	double BCang = delta.angle() + Ba;
	Point2d C = B.add(Point2d.fromPolar(BC,BCang));
	points[e.snd] = C;
     }
    } while (i != 0);
    fit();

    // there is a one-to-one correspondence between triangulated polygons,
    // binary trees, and balanced strings of brackets
    // I convert the triangulated polygon to a binary tree
    tree = TreePoly.makeTree(next[s.size()-1],s,adj,next,a);
    // and then to a balanced bracket string
    bracketsField.setText(tree.toBrackets());
  }
  
}

/* the tree representation of the triangulated polygon */
/* the base of the whole polygon is (n-1)0.  We don't store this */
/* base - it is implicit */
class TreePoly { /* assume base of this polygon is ab. Then: */
  int c;  /* the triangle with base ab is abc */
  TreePoly left;  /* this triangle splits poly into left poly with base ac*/
  TreePoly right;  /* and right poly with base cb*/
  int Aa;			/* angle at a */
  int Ba;			/* angle at b */
  int Ca;			/* angle at c */

  TreePoly(int c, int Aa, int Ba, int Ca, TreePoly left, TreePoly right) {
    this.c = c;
    this.Aa = Aa;
    this.Ba = Ba;
    this.Ca = Ca;
    this.left = left;
    this.right = right;
  }

  static TreePoly makeTree(int i, Vector s, int[] adj, int[] next, int[] a) {
    if (i == -1) {
      return null;
    } else {
      int c = ((Edge) s.elementAt(i)).snd;
      return new TreePoly(c, a[next[next[i]]],a[i],a[next[i]],
			  makeTree(adj[i],s,adj,next,a),
			  makeTree(adj[next[i]],s,adj,next,a));
    }
  }

  public String toString() {
    return ("("+left+c+right+")");
  }
    
  public String toBrackets() {
    return("("+(left==null?"":left.toBrackets())+
	   ")"+(right==null?"":right.toBrackets()));
  }
}