HalfEdge.pde

public class HalfEdge {
  private HalfEdge previous;
  private HalfEdge next;
  private HalfEdge twin;
  private Point origin;
  private boolean counted;
  private Face incidentFace;
  
  // MAKE SURE ALL HALF EDGES ARE INITIALIZED TO FALSE
  
  public void Remove() {
    Point p = getOrigin();
    Point q = twin.getOrigin();
    int state = -1;
    if ((p.count() == 1) && (q.count() == 1)) {
      // STRUCTURE IS DISSAPREAING WHAT SHOULD I DO
      // MAKE FACE LOSE CORRESPONDING INNER COMPONENT
      p.setRef(null);
      q.setRef(null);
      state = 0;
      //console.log("CLASS0");
    } else if (p.count() == 1) {
      p.setRef(null);
      q.setRef(twin.getAnotherLeaving());
      this.getnext().setprevious(twin.getprevious());
      twin.getprevious().setnext(this.getnext());
      // NOTHING SPECIAL MUST BE DONE
      // Make Sure face is not represented by dissapearing edge
      state = 1;
      //console.log("CLASS1A");
    } else if (q.count() == 1) {
      p.setRef(this.getAnotherLeaving());
      q.setRef(null);
      this.getprevious().setnext(twin.getnext());
      twin.getnext().setprevious(this.getprevious());
      // NOTHING SPECIAL MUST BE DONE
      // Make sure face is not represented by dissapearing edge
      state = 1;
      //console.log("CLASS1B");
    } else {
      int expected = p.count() - 2;
      p.setRef(this.getAnotherLeaving());
      q.setRef(twin.getAnotherLeaving());
      this.getnext().setprevious(twin.getprevious());
      twin.getprevious().setnext(this.getnext());
      this.getprevious().setnext(twin.getnext());
      twin.getnext().setprevious(this.getprevious());
      //console.log("CLASS23");
      if (p.count() == expected) {
        // was not broken faces merge!
        // 
        state = 2;
      } else {
        // structure broken
        // face has 1 more inner component reference
        state = 3;
      }
    }
  }
  
  public boolean isEventuallyNext(HalfEdge h) {
    if (this == h) { return true; }
    HalfEdge temp = this.getnext(); 
    while (temp != this) {
      if (temp == h) { return true; }
      temp = temp.getnext();
    }
    return false;
  }
  
  public HalfEdge(){}
  public HalfEdge(Point p, Point q) {
    // SETS THE TWIN
    settwin(new HalfEdge());
    twin.settwin(this);
    // SETS THE ORIGIN
    setOrigin(p);
    twin.setOrigin(q);
    // SETS THE COUNTED
    setCounted(false);
    twin.setCounted(false);
    int state = -1;
    if ((p.count() == 0) && (q.count() == 0)) {
      // this new structure was created not connected to anything
      // add to a connected componet of some face
      // watchout inside a face!!!!!
      state = 0;
    }
    else if ((p.count() == 0) || (q.count() == 0)) {
      // this means that this edge was addeded such that only one point is already a connected graph 
      // easy fix
      // nothing needs to be done?
      state = 1;
    }
    else { 
      // this means both things are connected graph if here that means
      // risk of new face or connected two unconnected components;
      state = -1;
      // we don't know state yet :(
    }
    int expected = p.count() + q.count() + 2;
    connect();
    twin.connect();
    if (state == -1) {
      if (p.count() == expected) {
        // two disconnected graphs are now one!
        // remove a reference an inner component of a face 
        state = 2;
      } else {
        // a face is divided in 2.
        state = 3;
      }
    } 
  }
  public void makeVertexReference() {
    origin.setRef(this);
  }
  
  
  public int connect() {
    ArrayList<HalfEdge> others = origin.getEntering();
    int result = -1;
    if (others == null) { 
      this.setprevious(gettwin());
      gettwin().setnext(this);
      // update vertex
      makeVertexReference();
      result = 0;
    }
    else if (others.size() == 1) {
      HalfEdge other = others.get(0);
      this.setprevious(other);
      other.setnext(this);
      gettwin().setnext(other.gettwin());
      other.gettwin().setprevious(gettwin());
      result = 1;
    }
    else if (others.size() > 1) {
      result = complex(this, others); 
    }
    return result;
  }
 
 
  public int complex (HalfEdge self, ArrayList<HalfEdge> entering) {
    Point parent = self.getOrigin();
    Point child = self.gettwin().getOrigin();
    Point p1;
    Point p2;
    int num = entering.size();
    int[] chart = new int[num];
    for (int i = 0; i < num; i++) {
      p1 = entering.get(i).getOrigin();
      p2 = entering.get((i+1)%num).getOrigin();
      if (CompGeo.immediateCCW(parent, child, p1, p2) == 1) { chart[i]++; } 
      else { chart[(i+1)%num]++; }
    }
    int Loser = 0;
    int Winner = 0;
    for (int i = 0; i < num; i++) {
      if (chart[i] == 0) { Loser = i; }
      if (chart[i] == 2) { Winner = i; }
    }
    self.setprevious(entering.get(Winner));
    entering.get(Winner).setnext(self);
    self.gettwin().setnext(entering.get(Loser).gettwin());
    entering.get(Loser).gettwin().setprevious(self.gettwin());
    return 2;
  }
  
  
  
  
  public int countReset() {
    int c = count();
    reset();
    return c;
  }
  
  public int countOutside() {
    HalfEdge temp = this.getnext();
    int count = 1;
    while (temp != this) {
      count++;
      temp = temp.getnext();
    }
    return count;
  }
  
  public int count() {
    if (counted == false) {
      counted = true;
      return 1 + twin.count() + next.count() + previous.count();
    } else {
     return 0; 
    }
  }
  
  // This method resets all the counted references to false. This only works if they are ALL already false or ALL already true
  public void reset() {
   if (counted == true) {
      counted = false;
      next.reset();
      twin.reset();
      previous.reset();
   }
  }
  
  public ArrayList<Point> getAdjacentPoints() {
    ArrayList<Point> points = new ArrayList<Point>();
    HalfEdge temp = previous.gettwin();
    while (temp != this) {
      points.add(temp.gettwin().getOrigin());
      temp = temp.getprevious().gettwin();
    }
    points.add(this.getOrigin());
    return points;
  }
  
  public ArrayList<HalfEdge> getEntering() {
    ArrayList<HalfEdge> result = new ArrayList<HalfEdge>();
    HalfEdge temp = twin.getnext().gettwin();
    while (temp != twin) {
      result.add(temp);
      temp = temp.getnext().gettwin();
    }
    result.add(twin);
    return result;
  }
  
  public ArrayList<HalfEdge> getOtherLeaving() {
    ArrayList<HalfEdge> result = new ArrayList<HalfEdge>();
    HalfEdge temp = previous.gettwin();
    while (temp != this) {
       result.add(temp);
       temp = (temp.getprevious()).gettwin();
    }
    return result;
  }
  public HalfEdge getAnotherLeaving() {
    if (this != getprevious().gettwin()) {
      return getprevious().gettwin();
    } else {
      return null; 
    }
  }
  
  public HalfEdge findStart(float x, float y, float distance, Point farAway) {
   HalfEdge temp = findHalfEdgeSelected(x,y,distance, farAway);
   reset();
   return temp; 
  }
  
  public HalfEdge findHalfEdgeSelected(float x, float y, float distance, Point farAway) {
    if (this.isSelected(x,y,distance, farAway) == true) { return this; }
    if (counted == false) {
      counted = true;
      HalfEdge temp = twin.findHalfEdgeSelected(x,y,distance,farAway);
      if (temp != null) { return temp; }
      temp = next.findHalfEdgeSelected(x,y,distance,farAway);
      if (temp != null) { return temp; }
      temp = previous.findHalfEdgeSelected(x,y,distance,farAway);
      if (temp != null) { return temp; }
    }
    return null;
  }
  
  public boolean isSelected(float x, float y, float distance, Point farAway) {
    Point p1 = new Point(origin.getX(), origin.getY());
    Point p3 = new Point(twin.getOrigin().getX(), twin.getOrigin().getY());
    float midx = (p1.getX() + p3.getX())/2;
    float midy = (p1.getY() + p3.getY())/2;
    float dx = p1.getX() - p3.getX();
    float dy = p1.getY() - p3.getY();
    float ndx = -dy;
    float ndy = dx;
    float notScaled = sqrt(ndx*ndx + ndy*ndy);
    float scale = notScaled/distance;
    if (scale > 1) {
      ndx = ndx/scale;
      ndy = ndy/scale;
    }
    Point p2 = new Point(midx + ndx, midy + ndy);
    Point p4 = new Point(midx - ndx, midy - ndy);
    HalfEdge h1 = new HalfEdge(p1, p2);
    HalfEdge h2 = new HalfEdge(p2, p3);
    HalfEdge h3 = new HalfEdge(p3, p4);
    HalfEdge h4 = new HalfEdge(p4, p1);
    return CompGeo.inside(h1, new Point(x, y), farAway); 
  }
  
  public ArrayList<HalfEdge> getAllLeaving() {
    ArrayList<HalfEdge> others = getOtherLeaving();
    others.add(this);
    return others;
  }
  public void printFace() {
    HalfEdge temp = next;
    //System.out.println("PrintFaceBegin");
    //System.out.println(origin + " " + twin.getOrigin());
    while (temp != this) {
      //System.out.println(temp.getOrigin() + " " + temp.gettwin().getOrigin());
      temp = temp.getnext();
    }
    //System.out.println();
  }
  
  private boolean isReachable(HalfEdge h) {
    if (this == h) { return true; }
    if (counted == false) {
      counted = true;
      return (twin.isReachable(h) || next.isReachable(h) || previous.isReachable(h));
    }
    return false;
  }
  
  public boolean intersectsStructure(Point p, Point q) {
    boolean out = intersectsEventually(p, q);
    reset();
    return out;
  }
  
  private boolean intersectsEventually(Point p, Point q) {
    boolean shared = false;
    if (this.getOrigin() == p) { shared = true; }
    if (this.getOrigin() == q) { shared = true; }
    if (this.gettwin().getOrigin() == p) { shared = true; }
    if (this.gettwin().getOrigin() == q) { shared  = true; }
    if (shared == false) {
      if (CompGeo.intersect(p, q, this.getOrigin(), this.gettwin().getOrigin()) == 1) {
        return true; 
      }
    }
    if (counted == false) {
       counted = true;
       return (twin.intersectsEventually(p, q) || next.intersectsEventually(p,q) || previous.intersectsEventually(p,q));
    }
    return false;
  }
  
  private boolean isReachableNext(HalfEdge h) {
    if (this == h) { return true; }
    if (counted == false) {
      counted = true;
      return next.isReachableNext(h);
    }
    return false;
  }
  
  public boolean canReach(HalfEdge h) {
    boolean out = isReachable(h);
    reset();
    return out;
  }
  public boolean canReachNext(HalfEdge h) {
    boolean out = isReachableNext(h);
    reset();
    return out;
  }
  
  
  // may not want getters, but for now they are here.
  public void setprevious(HalfEdge p) {
    previous = p;
  }
  public void setnext(HalfEdge n) {
    next = n;
  }
  public void settwin(HalfEdge t) {
    twin = t;
  }
  public void setOrigin(Point v) {
     origin = v;
  }
  public void setCounted(boolean b) {
    counted = b;
  }
  public boolean getCounted() {
    return counted; 
  }
  
  public String toString() {
    return "Origin: " + origin.toString() + "\nDestination: " + twin.getOrigin().toString(); 
  }
  
  
  public ArrayList<Point> getPointsNext() {
    ArrayList<Point> points = new ArrayList<Point>();
    points.add(this.getOrigin());
    HalfEdge temp = this.getnext();
    while (temp != this) {
      points.add(temp.getOrigin());
      temp = temp.getnext();
    }
    return points;
  }
  
  public HalfEdge gettwin() {
    return twin;
  } 
  public HalfEdge getnext(){
    return next;
  }
  public HalfEdge getprevious(){
    return previous;
  }
  public Point getOrigin() {
     return origin; 
  }
  public Face getIncidentFace() {
    return incidentFace;
  }
  public void setIncidentFace(Face f) {
    incidentFace = f;
  }
  
  
  
  public void printRNext() {
    //System.out.println("  " + origin);
    HalfEdge temp = next;
    while (temp != this) {
      //System.out.println("  " + temp.getOrigin());
      temp = temp.getnext();
    }
  }
  
}