drawing.pde

import papaya.*;


final int DRAW_NORMAL=1;
final int DRAW_DRAG=2;
final int DRAW_ANIMATION=3;
final int Vertex_Rad=8;
final int Width=600;
final int Height=600;
final int Margin=10;
ArrayList<Gui_element> gui=new ArrayList();
Gui_element gui_current=null;
Vertex drag_start;
Graph G=new Graph();
Button draw_button=new Button(500, 450, 80, 40, color(150), "Tutte Draw", new TutteDrawEvent());
float[][] orig,targ;
int animation_start_time=0;
final int animation_duration=1000;
void setup() {
  size(600, 600);
  background(255);
  draw_button.disable=false;
  gui.add(draw_button);
  gui.add(new Button(500, 500, 80, 40, color(150), "Initial Graph", new InitialGraphEvent()));
  gui.add(new Button(500, 550, 80, 40, color(150), "Reset", new ResetEvent()));
}
int draw_state=DRAW_NORMAL;

void draw() {
  background(255);
  if(draw_state==DRAW_ANIMATION){
    if(millis()-animation_start_time>animation_duration){
      for(int i=0;i<G.V.size();++i){
        G.V.get(i).x=(int)targ[i][0];
        G.V.get(i).y=(int)targ[i][1];
      }
      draw_state=DRAW_NORMAL;
    }else{
      for(int i=0;i<G.V.size();++i){
        G.V.get(i).x=(int)((targ[i][0]-orig[i][0])*(millis()-animation_start_time)/animation_duration+orig[i][0]);
        G.V.get(i).y=(int)((targ[i][1]-orig[i][1])*(millis()-animation_start_time)/animation_duration+orig[i][1]);
      }
    }
  }
  for (Gui_element i : gui) {
    i.draw();
  }
  if (draw_state==DRAW_DRAG) {
    strokeWeight(2);
    stroke(0, 0, 255);
    line(drag_start.x, drag_start.y, mouseX, mouseY);

    //println("DRAW_DRAG:",drag_start.x,",",drag_start.y,",",mouseX,",",mouseY);
    //Draw the dragged line;
  }
}

void mouseMoved() {
  gui_current=null;
  for (Gui_element i : gui) {
    i.mouseMoved();
  }
}
void mouseDragged() {
  mouseMoved();
  if (draw_state!=DRAW_DRAG) {//start dragging
    if (gui_current!=null&&gui_current instanceof Vertex) {
      drag_start=(Vertex)gui_current;
      draw_state=DRAW_DRAG;
    }
  }
}
void mousePressed() {
  if (gui_current==null) {
    Vertex v=new Vertex(mouseX, mouseY);
    G.V.add(v);
    gui.add(v);
    //draw_button.disable=!G.ValidGraph();
  } else {
    gui_current.mousePressed();
  }
}

void mouseReleased() {
  if (draw_state==DRAW_DRAG) {
    draw_state=DRAW_NORMAL;
    if (gui_current!=null&&(gui_current instanceof Vertex)) {
      if (G.ValidNewEdge(drag_start, (Vertex)gui_current)) {
        Edge e=new Edge(drag_start, (Vertex)gui_current);
        G.E.add(e);
        gui.add(e);
        //draw_button.disable=!G.ValidGraph();
        println("Valid");
      } else {
        println("Invalid");
      }
    }
  }
}

class InitialGraphEvent implements ButtonEvent {
  void onclick() {
    if (G.V.size()<=3) throw new RuntimeException("Requires at least 4 points"); 
    for (int i=0; i<G.V.size (); i++) {
      do {
        stroke(0, 0, 255);
        strokeWeight(2);
        int l= int(random(G.V.size()));
        println(l);
        //add the drawn edge to the graph 
        if (G.ValidNewEdge(G.V.get(i), G.V.get(l))) {   //have to check the whether the randomly selected vertex has three edges????
          Edge e=new Edge(G.V.get(i), G.V.get(l));
          G.E.add(e);
          gui.add(e);
        }
      }while (G.check3edges_per_vertex (G.V.get (i)));
      //draw_button.disable=!G.ValidGraph();
    }
  }
}
class ResetEvent implements ButtonEvent {
  void onclick() {
    G.E.clear();
    G.V.clear();
    gui.clear();
    setup();
  }
}

class TutteDrawEvent implements ButtonEvent {
  void onclick() {
    int l=G.V.size();
    
    ArrayList<Vertex> face=FindFace();
    print("0");
    for(Vertex v:face){
      print(" -",G.V.indexOf(v));
    }
    println();
    int a=0;
    for(Vertex v:face){
      ++a;
      int b=G.V.indexOf(v);
      if(a!=b){
        Vertex t=G.V.get(a);
        G.V.set(a,G.V.get(b));
        G.V.set(b,t);
      }
    }
    //Matrix L
    float[][] L=new float[l][l];
    for(int i=0;i<l;++i){
      for(int j=0;j<l;++j){//L[i][j]=...
        if(i==j){
          L[i][j]=G.V.get(i).E.size();
        }else{
          L[i][j]=0;
          for(Edge k:G.V.get(i).E){
            if(k.v1==G.V.get(j)||k.v2==G.V.get(j)){
              L[i][j]=-1;break;
            }
          }
        }
      }
    }
    int n=face.size()+1;
    float[][] L1=new float[n][n];
    float[][] L2=new float[l-n][l-n];
    float[][] B=new float[l-n][n];
    for(int i=0;i<n;++i){
      for(int j=0;j<n;++j){
        L1[i][j]=L[i][j];
      }
    }
    for(int i=0;i<l-n;++i){
      for(int j=0;j<l-n;++j){
        L2[i][j]=L[i+n][j+n];
      }
    }
    for(int i=0;i<l-n;++i){
      for(int j=0;j<n;++j){
        B[i][j]=L[i+n][j];
      }
    }
    
    float[][] P1=new float[n][2];
    for(int i=0;i<n;++i){
      P1[i][0]=sin(i*PI*2/n)*(Height/2-Margin)+Width/2;
      P1[i][1]=Height/2-cos(i*PI*2/n)*(Height/2-Margin);
      println(P1[i][0], " " ,P1[i][1]);
    }
    Mat.print(L2,2);
    float[][] invL2= Mat.inverse(L2);
    float[][] nagP2=Mat.multiply(Mat.multiply(invL2,B),P1);
    orig=new float[l][2];
    targ=new float[l][2];
    for(int i=0;i<n;++i){
      orig[i][0]=G.V.get(i).x;
      orig[i][1]=G.V.get(i).y;
      targ[i][0]=(int)P1[i][0];
      targ[i][1]=(int)P1[i][1];
    }
    for(int i=n;i<l;++i){
      orig[i][0]=G.V.get(i).x;
      orig[i][1]=G.V.get(i).y;
      targ[i][0]=(int)-nagP2[i-n][0];
      targ[i][1]=(int)-nagP2[i-n][1];
    }
    animation_start_time=millis();
    draw_state=DRAW_ANIMATION;
  }
  ArrayList<Vertex> FindFaceDFSID(Vertex vs,Vertex vc,int n){//Vsource, Vcurrent, depth
    if(n==1){//edge of the search
      for(Edge e:vc.E){
        if(!e.searched){
          if((e.v1==vc&&e.v2==vs)||(e.v1==vs&&e.v2==vc)){//find loop
            println("found!");
            return new ArrayList();
          }
        }  
      }
      return null;
    }else{
      for(Edge e:vc.E){
        if(!e.searched){
          e.searched=true;
          Vertex nvc;
          if(e.v1==vc){
            nvc=e.v2;
          }else{
            nvc=e.v1;
          }
          ArrayList<Vertex> rt=FindFaceDFSID(vs,nvc,n-1);
          if(rt!=null){
            rt.add(nvc);
            return rt;
          }
          e.searched=false;
        }  
      }
    }
    return null;
  }
  ArrayList<Vertex> FindFace(){
    for(Edge e:G.E){
      e.searched=false;
    }
    for(int i=3;i<=G.E.size();++i){
      ArrayList rt=FindFaceDFSID(G.V.get(0), G.V.get(0), i);
      if(rt!=null)return rt;
    }
    return null;
  }
}