import java.awt.*;
import java.awt.event.*;
import java.lang.*;
import java.util.*;  
public class Voronoi{
   
  Vector Edges;    
  Vector DTris;     
  Vedge target;
  int del[] = new int[3];
  public Voronoi(int size){
    DTris = new Vector(size);
    Edges = new Vector(3*size);
    del[0] = 1; 
    del[1] = 2; 
    del[2] = 0;
  }
  private void Insert(DoubleVector dv){
    int tn = 2;
    InsertionP ds = new InsertionP(dv.x,dv.y);
    target = (Vedge)Edges.elementAt(0);
    if(target.Region(ds) == -1){ 
      if(target.einv != null)
	tn = Search(target.einv,ds);
    }else{
      tn = Search(target,ds);
    }
    ReConstructDT(target,ds,tn);
  }
  public void setP(Vector inp){
    int numberp = inp.size();
    double maxvalue;
    int i=0;
    DoubleVector ddv =  ((DoubleVector)(inp.elementAt(0)));
    if(Math.abs(ddv.x)>Math.abs(ddv.y)){
      maxvalue = Math.abs(ddv.x);
    }else{
      maxvalue = Math.abs(ddv.y);
    }
    for(i=1;i<numberp;i++){
      ddv = ((DoubleVector)(inp.elementAt(i)));
        if(Math.abs(ddv.x)>Math.abs(ddv.y)){
	  if(maxvalue<Math.abs(ddv.x)){
	     maxvalue = Math.abs(ddv.x);
	  }
	}else{
	  if(maxvalue<Math.abs(ddv.y)){
	    maxvalue = Math.abs(ddv.y);
	  }
	}
    }
    this.Init(new DoubleVector(3.0*maxvalue,0.0),
	      new DoubleVector(0.0,3.0*maxvalue),
	      new DoubleVector(-3.0*maxvalue,-3.0*maxvalue));
    for(i=0;i<numberp;i++){
      ddv = ((DoubleVector)(inp.elementAt(i)));
      this.Insert(new DoubleVector(ddv.x,ddv.y));
    }
  }
  private void Init(DoubleVector dv1,DoubleVector dv2,DoubleVector dv3){
    int tn;
    InsertionP p[] = new InsertionP[3];
    p[0] = new InsertionP(dv1.x,dv1.y);
    p[1] = new InsertionP(dv2.x,dv2.y);
    p[2] = new InsertionP(dv3.x,dv3.y);
    
    Vedge e[] = new Vedge[3];
    e[0] = new Vedge(p[0],p[1]);      
    int check = e[0].Region(p[2]);
    if(check == 0){
      /* degenerate case 1 */
      System.out.println("degenerate case !");
      return; 
    }else if(check == -1){
      /* reverse direction */
      p[0] = new InsertionP(dv2.x,dv2.y);
      p[1] = new InsertionP(dv1.x,dv1.y);
      e[0].Update(p[0],p[1]);
    }
    /* make directed edge around triangle */ 
    for(tn = 1;tn < 3;tn++)
      e[tn] = new Vedge(p[tn],p[del[tn]]);
    for(tn = 0;tn < 3;tn++)
      e[tn].hnext = e[del[tn]];
    DTris.addElement(new Dtriangle(Edges,e));
  }
  public void Clear(){
    Edges.removeAllElements();
    DTris.removeAllElements();
  }

  
  private int Search(Vedge de, InsertionP ds){
    int region1,region2;
    Vedge de1,de2;
    de1 = null;
    if((region1 = enext(de).Region(ds)) == -1){ 
      /* reverse direction */
      if(enext(de).einv != null){
	return Search(enext(de).einv,ds);
      }else{ 
	target = de; 
	return -1;
      }
    }
    if(region1 == 0)de1 = enext(de);
    de2 = enext(de);
    if((region2 = enext(de2).Region(ds)) == -1){ 
      if(enext(de2).einv != null){
	return Search(enext(de2).einv,ds);
      }else{ 
	target = enext(de2);
	return -1;
      }
    }
    if(region2 == 0) de1 = enext(de2);
    if(de.Region(ds) == 0)de1 = de;
    if(de1 != null){
      target = de1;
      if(enext(de1).Region(ds) == 0){
	target = enext(de1);
	return 0;
      }
      if(enext(enext(de1)).Region(ds) == 0) return 0;
      return 1;
    }
    target = de2;
    return 2;
  }

  private void EdgeFlip(Vedge de){
    Vedge e[] = new Vedge[6];
    e[0] = de;
    e[1] = de.einv;
    if((e[1] == null)||(e[1].tri == null))return;
    e[2] = enext(e[0]);
    e[3] = enext(e[2]);
    e[4] = enext(e[1]);
    e[5] = enext(e[4]);
    if((e[0].tri.inCircumCircle(e[4].p2))||
       (e[1].tri.inCircumCircle(e[2].p2))){
      e[0].Update(e[4].p2,e[2].p2);
      e[1].Update(e[2].p2,e[4].p2);
      e[0].setInverse(e[1]);
      e[3].tri.Update(e[3],e[4],e[0]);
      e[5].tri.Update(e[5],e[2],e[1]);
      e[2].setp1edge();
      e[4].setp1edge();
      EdgeFlip(e[2]);
      EdgeFlip(e[4]);
      EdgeFlip(e[3]);
      EdgeFlip(e[5]);
    }
  }
  public int getNumberofEdge(){
    return Edges.size();
  }
  public DoubleVector getStartPoint(int i){
    double dx = ((((Vedge)Edges.elementAt(i)).tri).circum.x);
    double dy = ((((Vedge)Edges.elementAt(i)).tri).circum.y);
    return new DoubleVector(dx,dy);
  }
  public DoubleVector getEndPoint(int i){
    double dx,dy;
    Vedge e = (Vedge)Edges.elementAt(i);
    Vedge ie = e.einv;
    if(ie == null || ie.tri == null){
      dx = (e.tri).circum.x-(e.p2).y+(e.p1).y;
      dy = (e.tri).circum.y-(e.p1).x+(e.p2).x;
    }else{
      dx = (ie.tri).circum.x;
      dy = (ie.tri).circum.y;
    }
    return new DoubleVector(dx,dy);
  }
  private Vedge enext(Vedge dv){
    return (dv.enext);
  }
  private Vedge hnext(Vedge dv){
    return (dv.hnext);
  }
  private void ReConstructDT(Vedge de, InsertionP ds, int type){
    Vedge e[] = new Vedge[6];
    InsertionP p[] = new InsertionP[4];
    Vedge e2[] = new Vedge[4];
    int tn = 0; 
    e[0] = de;
    for(tn=1;tn<3;tn++)
      e[tn] = enext(e[(tn-1)]);
    for(tn=0;tn<3;tn++)
      p[tn] = e[tn].p1;
    if(type == 2) {
      for(tn=0;tn<3;tn++)
	e2[tn] = new Vedge(p[tn],ds);
      de.tri.RemoveEdges(Edges);
      DTris.removeElement(de.tri);
      for(tn=0;tn<3;tn++)
	DTris.addElement(new Dtriangle(Edges,e[tn],e2[del[tn]],
				     e2[tn].getReverse()));
      for(tn=0;tn<3;tn++)
	EdgeFlip(e[tn]);
    }else{
      e[3] = e[0].einv;
      if((e[3] == null)||(e[3].tri == null)){
	e2[2] = new Vedge(p[2],ds); e2[1] = new Vedge(ds,p[1]); 
	e2[0] = new Vedge(p[0],ds); e2[3] = e2[2].getReverse();
	e2[0].setp1edge();
	e[0].getHead().hnext = e2[0];
	e2[0].hnext = e2[1];
	e2[1].hnext = hnext(e[0]);
	DTris.removeElement(e[0].tri);   
	Edges.removeElement(e[0]);
	 for(tn=0;tn<4;tn++)
	   Edges.addElement(e2[tn]);
	 DTris.addElement(new Dtriangle(e[1],e2[2],e2[1]));
	 DTris.addElement(new Dtriangle(e[2],e2[0],e2[3]));
	 EdgeFlip(e[1]);  
	 EdgeFlip(e[2]);
	 EdgeFlip(e2[2]);
      }else{
	e[4] = enext(e[3]);
	e[5] = enext(e[4]);
	p[3] = e[5].p1;
	 for(tn=0;tn<4;tn++)
	   e2[tn] = new Vedge(p[tn],ds);
	DTris.removeElement(de.tri);
	de.tri.RemoveEdges(Edges);
	DTris.removeElement(e[3].tri);
	e[3].tri.RemoveEdges(Edges);
	e[4].setp1edge();   
	e[1].setp1edge();
	DTris.addElement(new Dtriangle(Edges,e[1],e2[2],
				      e2[1].getReverse()));
	DTris.addElement(new Dtriangle(Edges,e[2],e2[0],
				      e2[2].getReverse()));
	DTris.addElement(new Dtriangle(Edges,e[4],e2[3],
				      e2[0].getReverse()));
	DTris.addElement(new Dtriangle(Edges,e[5],e2[1],
				      e2[3].getReverse()));
	 for(tn=1;tn<6;tn++)
	   if(tn!=3)EdgeFlip(e[tn]);   
	 for(tn=0;tn<4;tn++)
	   EdgeFlip(e2[tn]);
      }
    }
  } 
  
}