import java.math.*;

public class DiscMath {

  public static void DiscRep(DirectedGraph graph)
  {
    double N = 2;
    double errMargin = 0.01;
    double adjustment = 0.0;
    VertexContainer vcontainer = new VertexContainer();

    for (int i=0; i<graph.vertices.length; i++) {
      SumOfAnglesAroundVertex(((DirectedVertex)(graph.vertices.elements[i])));
      ((DirectedVertex)(graph.vertices.elements[i])).errMargin =
          ((DirectedVertex)(graph.vertices.elements[i])).theta - 2*Math.PI;
    }

    while (NeedsRadiusAdj(graph, vcontainer, errMargin)) {
      adjustment = (vcontainer.getVertex()).errMargin / N;
      AdjRadius(vcontainer.getVertex(), adjustment, errMargin);
    }
  }

  public static void AdjRadius(DirectedVertex vertex, double adjustment, double errMargin)
  {
    DirectedVertex adjVertex;

        if (!vertex.isOutsideVertex)
          vertex.radius += adjustment;
        for (int i=0; i<vertex.orderedEdges.length; i++) {
          adjVertex = GetOtherVertex(vertex, (DirectedEdge)(vertex.orderedEdges.elements[i]));
          if (!adjVertex.isOutsideVertex)
            adjVertex.radius += adjustment * -1 / (vertex.orderedEdges.length - 1);
        }
        vertex.theta = SumOfAnglesAroundVertex(vertex);
        System.out.println("err margin before " + vertex.errMargin);
        vertex.errMargin = vertex.theta - 2*Math.PI;
        System.out.println("err margin after " + vertex.errMargin);
  }

  public static boolean NeedsRadiusAdj(DirectedGraph graph, VertexContainer vcontainer, double errMargin)
  {
    boolean needsAdj = false;
    DirectedVertex vertex, adjVertex = null;
    double maxErrMargin = 0.0;

    for (int i=0; i<graph.vertices.length; i++) {
      vertex = (DirectedVertex)(graph.vertices.elements[i]);
      if (vertex.isOutsideVertex)
        continue;
      if ( Math.abs(vertex.errMargin) > errMargin &&
          Math.abs(vertex.errMargin) > maxErrMargin) {
        needsAdj = true;
        adjVertex = vertex;
        maxErrMargin = Math.abs(vertex.errMargin);
      }
    }
    vcontainer.setVertex(adjVertex);
    return needsAdj;
  }

  public static void CreateDiscRepresentation(DirectedGraphCanvas canvas)
  {
    //List faces;
    DirectedVertex outsideVertex1 = null, outsideVertex2 = null, outsideVertex3 = null;
    VertexContainer vertexContainer = new VertexContainer();
    List nondiscVerticies = new List();
    int i = 0, discsCreated = 0;


    outsideVertex1 = (DirectedVertex)(canvas.graph.vertices.elements[0]);
    if ( outsideVertex1.Compare(((DirectedEdge)(outsideVertex1.orderedEdges.elements[0])).start) )
      outsideVertex2 = ((DirectedEdge)(outsideVertex1.orderedEdges.elements[0])).end;
    else
      outsideVertex2 = ((DirectedEdge)(outsideVertex1.orderedEdges.elements[0])).start;
    if ( outsideVertex1.Compare(((DirectedEdge)(outsideVertex1.orderedEdges.elements[1])).start) )
      outsideVertex3 = ((DirectedEdge)(outsideVertex1.orderedEdges.elements[1])).end;
    else
      outsideVertex3 = ((DirectedEdge)(outsideVertex1.orderedEdges.elements[1])).start;

    outsideVertex1.isOutsideVertex = true;
    outsideVertex2.isOutsideVertex = true;
    outsideVertex3.isOutsideVertex = true;

    outsideVertex1.position.x = outsideVertex1.radius;
    outsideVertex1.position.y = 400 - outsideVertex1.radius;
    outsideVertex1.isDiscPos = true;
    outsideVertex2.position.x = outsideVertex1.position.x + outsideVertex1.radius + outsideVertex2.radius;
    outsideVertex2.position.y = outsideVertex1.position.y;
    outsideVertex2.isDiscPos = true;
    outsideVertex3.position.x = outsideVertex1.position.x + outsideVertex1.radius;
    outsideVertex3.position.y = outsideVertex1.position.y - Math.sqrt(Math.pow(2*outsideVertex1.radius,2) -
        Math.pow(outsideVertex1.radius,2));
    outsideVertex3.isDiscPos = true;

    canvas.graph.outsideVerticies.append(outsideVertex1);
    canvas.graph.outsideVerticies.append(outsideVertex2);
    canvas.graph.outsideVerticies.append(outsideVertex3);
    
    // create discs for the outer verticies
    canvas.graph.discs.append(new Disc(outsideVertex1.position.x, outsideVertex1.position.y, outsideVertex1.radius));
    canvas.graph.discs.append(new Disc(outsideVertex2.position.x, outsideVertex2.position.y, outsideVertex2.radius));
    canvas.graph.discs.append(new Disc(outsideVertex3.position.x, outsideVertex3.position.y, outsideVertex3.radius));
    discsCreated = 3;


    DiscRep(canvas.graph);

    for (i=0; i<canvas.graph.vertices.length; i++) {
      if ( !outsideVertex1.Compare((DirectedVertex)(canvas.graph.vertices.elements[i]))
          && !outsideVertex2.Compare((DirectedVertex)(canvas.graph.vertices.elements[i]))
          && !outsideVertex3.Compare((DirectedVertex)(canvas.graph.vertices.elements[i])) )
        nondiscVerticies.append(canvas.graph.vertices.elements[i]);
    }

    while (nondiscVerticies.length > 0) {
      i = 0;
      while ( !(CreateDisc(canvas.graph, (DirectedVertex)(nondiscVerticies.elements[i++]))) )
        ;//System.out.println(nondiscVerticies.elements[i-1]);
      nondiscVerticies.delete(i-1);
    }
    canvas.repaint();
  }

  public static boolean CreateDisc(DirectedGraph graph, DirectedVertex vertex)
  {
    DirectedVertex nextVertex1, nextVertex2, nextVertex3;
    int next1 = 0, next2 = 1;

    for (int i=0; i<vertex.orderedEdges.length; i++) {
      next1++;
      next2++;
      if (i == vertex.orderedEdges.length-2)
        next2 = 0;
      else if (i == vertex.orderedEdges.length-1)
        next1 = 0;

      nextVertex1 = GetOtherVertex(vertex, (DirectedEdge)(vertex.orderedEdges.elements[i]));
      nextVertex2 = GetOtherVertex(vertex, (DirectedEdge)(vertex.orderedEdges.elements[next1]));
      nextVertex3 = GetOtherVertex(vertex, (DirectedEdge)(vertex.orderedEdges.elements[next2]));

      if (nextVertex1.isDiscPos && nextVertex1.isOutsideVertex && nextVertex2.isDiscPos && nextVertex2.isOutsideVertex) {
        FindDiscPos2(graph, vertex, nextVertex1, nextVertex2);
        graph.discs.append(new Disc(vertex.position, vertex.radius));
        return true;
      }
      else if (nextVertex1.isDiscPos && nextVertex1.isOutsideVertex && nextVertex3.isDiscPos && nextVertex3.isOutsideVertex) {
        FindDiscPos2(graph, vertex, nextVertex1, nextVertex3);
        graph.discs.append(new Disc(vertex.position, vertex.radius));
        return true;
      }
      else if (nextVertex3.isDiscPos && nextVertex3.isOutsideVertex && nextVertex2.isDiscPos && nextVertex2.isOutsideVertex) {
        FindDiscPos2(graph, vertex, nextVertex3, nextVertex2);
        graph.discs.append(new Disc(vertex.position, vertex.radius));
        return true;
      }
      else if (i == vertex.orderedEdges.length-1) {
        FindDiscPos(vertex, nextVertex1, nextVertex2, nextVertex3);
        graph.discs.append(new Disc(vertex.position, vertex.radius));
        return true;
      }
    }
    return false;
  }

  public static DirectedVertex GetOtherVertex(DirectedVertex vertex, DirectedEdge edge)
  {
    if (vertex == null || edge == null) {
      System.out.println("DiscMath.GetOtherVertex: " + vertex + " " + edge);
      return null;
    }
    if ( vertex.Compare(edge.start) )
      return edge.end;
    else
      return edge.start;
  }

  public static Position IntersectingCirclesPoint1(double a, double b, double R, double c, double d, double r)
  {
    Position pos;
    double x = 0.0, y = 0.0;
    double val, val2, val3, val4;

    val = a*a*a*a + a*a*b*b - 2*a*a*a*c - b*b*c*c + 2*a*c*c*c - c*c*c*c - 2*a*a*b*d +
            2*b*c*c*d + a*a*d*d - c*c*d*d + a*a*r - 2*a*c*r + c*c*r - a*a*R +
            2*a*c*R - c*c*R;
    val2 = c*c*R + b*Math.sqrt((a - c)*(a - c)*
                (-1*(a*a*a*a) - 2*a*a*b*b - b*b*b*b + 4*a*a*a*c + 4*a*b*b*c - 6*a*a*c*c -
                  2*b*b*c*c + 4*a*c*c*c - c*c*c*c + 4*a*a*b*d + 4*b*b*b*d -
                  8*a*b*c*d + 4*b*c*c*d - 2*a*a*d*d - 6*b*b*d*d + 4*a*c*d*d -
                  2*c*c*d*d + 4*b*d*d*d - d*d*d*d + 2*a*a*r + 2*b*b*r - 4*a*c*r +
                  2*c*c*r - 4*b*d*r + 2*d*d*r - r*r + 2*a*a*R + 2*b*b*R -
                  4*a*c*R + 2*c*c*R - 4*b*d*R + 2*d*d*R + 2*r*R - R*R));
    val3 = d*Math.sqrt((a - c)*(a - c)*(-1*(a*a*a*a) - 2*a*a*b*b - b*b*b*b + 4*a*a*a*c + 4*a*b*b*c -
                  6*a*a*c*c - 2*b*b*c*c + 4*a*c*c*c - c*c*c*c + 4*a*a*b*d +
                  4*b*b*b*d - 8*a*b*c*d + 4*b*c*c*d - 2*a*a*d*d - 6*b*b*d*d +
                  4*a*c*d*d - 2*c*c*d*d + 4*b*d*d*d - d*d*d*d + 2*a*a*r + 2*b*b*r -
                  4*a*c*r + 2*c*c*r - 4*b*d*r + 2*d*d*r - r*r + 2*a*a*R +
                  2*b*b*R - 4*a*c*R + 2*c*c*R - 4*b*d*R + 2*d*d*R + 2*r*R - R*R
                  ));
    val4 = (2*(a - c)*(a*a + b*b - 2*a*c + c*c - 2*b*d + d*d));
    System.out.println("1: " + val + " " + val2 + " " + val3 + " " + val4);
    val += val2;
    val -= val3;
    val /= val4;
    System.out.println("val " + val);

    x = (a*a*a*a + a*a*b*b - 2*a*a*a*c - b*b*c*c + 2*a*c*c*c - c*c*c*c - 2*a*a*b*d +
            2*b*c*c*d + a*a*d*d - c*c*d*d + a*a*r - 2*a*c*r + c*c*r - a*a*R +
            2*a*c*R - c*c*R + b*Math.sqrt((a - c)*(a - c)*
                (-1*(a*a*a*a) - 2*a*a*b*b - b*b*b*b + 4*a*a*a*c + 4*a*b*b*c - 6*a*a*c*c -
                  2*b*b*c*c + 4*a*c*c*c - c*c*c*c + 4*a*a*b*d + 4*b*b*b*d -
                  8*a*b*c*d + 4*b*c*c*d - 2*a*a*d*d - 6*b*b*d*d + 4*a*c*d*d -
                  2*c*c*d*d + 4*b*d*d*d - d*d*d*d + 2*a*a*r + 2*b*b*r - 4*a*c*r +
                  2*c*c*r - 4*b*d*r + 2*d*d*r - r*r + 2*a*a*R + 2*b*b*R -
                  4*a*c*R + 2*c*c*R - 4*b*d*R + 2*d*d*R + 2*r*R - R*R)) -
            d*Math.sqrt((a - c)*(a - c)*(-1*(a*a*a*a) - 2*a*a*b*b - b*b*b*b + 4*a*a*a*c + 4*a*b*b*c -
                  6*a*a*c*c - 2*b*b*c*c + 4*a*c*c*c - c*c*c*c + 4*a*a*b*d +
                  4*b*b*b*d - 8*a*b*c*d + 4*b*c*c*d - 2*a*a*d*d - 6*b*b*d*d +
                  4*a*c*d*d - 2*c*c*d*d + 4*b*d*d*d - d*d*d*d + 2*a*a*r + 2*b*b*r -
                  4*a*c*r + 2*c*c*r - 4*b*d*r + 2*d*d*r - r*r + 2*a*a*R +
                  2*b*b*R - 4*a*c*R + 2*c*c*R - 4*b*d*R + 2*d*d*R + 2*r*R - R*R
                  )))/(2*(a - c)*(a*a + b*b - 2*a*c + c*c - 2*b*d + d*d));

    y = (a*a*b + b*b*b - 2*a*b*c + b*c*c + a*a*d - b*b*d - 2*a*c*d + c*c*d -
            b*d*d + d*d*d + b*r - d*r - b*R + d*R -
            Math.sqrt((a - c)*(a - c)*(-1*(a*a*a*a) - 2*a*a*b*b - b*b*b*b + 4*a*a*a*c + 4*a*b*b*c -
                 6*a*a*c*c - 2*b*b*c*c + 4*a*c*c*c - c*c*c*c + 4*a*a*b*d + 4*b*b*b*d - 
                 8*a*b*c*d + 4*b*c*c*d - 2*a*a*d*d - 6*b*b*d*d + 4*a*c*d*d - 
                 2*c*c*d*d + 4*b*d*d*d - d*d*d*d + 2*a*a*r + 2*b*b*r - 4*a*c*r + 
                 2*c*c*r - 4*b*d*r + 2*d*d*r - r*r + 2*a*a*R + 2*b*b*R - 
                 4*a*c*R + 2*c*c*R - 4*b*d*R + 2*d*d*R + 2*r*R - R*R)))/
          (2*(a*a + b*b - 2*a*c + c*c - 2*b*d + d*d));
    x = val;
    System.out.println("x " + x + ", y " + y);
    pos = new Position(x,y);
    return pos;
  }

  public static Position IntersectingCirclesPoint2(double a, double b, double R, double c, double d, double r)
  {
    Position pos = new Position(0.0, 0.0, 0.0);
    double val, val2, val3, val4;
    val = a*a*a*a + a*a*b*b - 2*a*a*a*c - b*b*c*c + 2*a*c*c*c - c*c*c*c - 2*a*a*b*d +
          2*b*c*c*d + a*a*d*d - c*c*d*d + a*a*r - 2*a*c*r + c*c*r - a*a*R +
          2*a*c*R - c*c*R;
    val2 = (a - c)*(a - c)*
                (-1*(a*a*a*a) - 2*a*a*b*b - b*b*b*b + 4*a*a*a*c + 4*a*b*b*c - 6*a*a*c*c -
                  2*b*b*c*c + 4*a*c*c*c - c*c*c*c + 4*a*a*b*d + 4*b*b*b*d -
                  8*a*b*c*d + 4*b*c*c*d - 2*a*a*d*d - 6*b*b*d*d + 4*a*c*d*d -
                  2*c*c*d*d + 4*b*d*d*d - d*d*d*d + 2*a*a*r + 2*b*b*r - 4*a*c*r +
                  2*c*c*r - 4*b*d*r + 2*d*d*r - r*r + 2*a*a*R + 2*b*b*R -
                  4*a*c*R + 2*c*c*R - 4*b*d*R + 2*d*d*R + 2*r*R - R*R);
    val3 = ((a - c)*(a - c)*(-1*(a*a*a*a) - 2*a*a*b*b - b*b*b*b + 4*a*a*a*c + 4*a*b*b*c -
                  6*a*a*c*c - 2*b*b*c*c + 4*a*c*c*c - c*c*c*c + 4*a*a*b*d + 4*b*b*b*d -
                  8*a*b*c*d + 4*b*c*c*d - 2*a*a*d*d - 6*b*b*d*d + 4*a*c*d*d -
                  2*c*c*d*d + 4*b*d*d*d - d*d*d*d + 2*a*a*r + 2*b*b*r - 4*a*c*r +
                  2*c*c*r - 4*b*d*r + 2*d*d*r - r*r + 2*a*a*R + 2*b*b*R -
                  4*a*c*R + 2*c*c*R - 4*b*d*R + 2*d*d*R + 2*r*R - R*R));
    val4 = (2*(a - c)*(a*a + b*b - 2*a*c + c*c - 2*b*d + d*d));

    System.out.println("2: " + val + " " + val2 + " " + val3 + " " + val4);
    val -= b*Math.sqrt(val2);
    val += d*Math.sqrt(val3);
    val /= val4;
    System.out.println(val + " " + val2 + " " + val3 + " " + val4);
    pos.x = (val - b*Math.sqrt(val2) +
            d*Math.sqrt(val3))/ val4;
    pos.x = val;
    pos.y = (a*a*b + b*b*b - 2*a*b*c + b*c*c + a*a*d - b*b*d - 2*a*c*d + c*c*d -            b*d*d + d*d*d + b*r - d*r - b*R + d*R +
            Math.sqrt((a - c)*(a - c)*(-1*(a*a*a*a) - 2*a*a*b*b - b*b*b*b + 4*a*a*a*c + 4*a*b*b*c - 6*a*a*c*c - 2*b*b*c*c + 4*a*c*c*c - c*c*c*c + 4*a*a*b*d + 4*b*b*b*d - 8*a*b*c*d + 4*b*c*c*d - 2*a*a*d*d - 6*b*b*d*d + 4*a*c*d*d - 2*c*c*d*d + 4*b*d*d*d - d*d*d*d + 2*a*a*r + 2*b*b*r - 4*a*c*r + 2*c*c*r - 4*b*d*r + 2*d*d*r - r*r + 2*a*a*R + 2*b*b*R - 4*a*c*R + 2*c*c*R - 4*b*d*R + 2*d*d*R + 2*r*R - R*R)))/ (2*(a*a + b*b - 2*a*c + c*c - 2*b*d + d*d));
    
    return pos;
  }


  public static void FindDiscPos(DirectedVertex vertex, DirectedVertex knownVertex1,
      DirectedVertex knownVertex2, DirectedVertex knownVertex3)
  {

    vertex.isDiscPos = true;
  }

  public static void FindDiscPos2(DirectedGraph graph, DirectedVertex vertex, DirectedVertex outsideVertex1,
      DirectedVertex outsideVertex2)
  {
    double theta = 0.0;
    double xlength = 0.0, ylength = 0.0;

    // lower two outside verticies
    if ( outsideVertex1.Compare((DirectedVertex)(graph.outsideVerticies.elements[0]))
          && outsideVertex2.Compare((DirectedVertex)(graph.outsideVerticies.elements[1])) ) {
      vertex.position.x = outsideVertex1.position.x + outsideVertex1.radius;
      vertex.position.y = outsideVertex1.position.y - Math.sqrt( Math.pow(vertex.radius+outsideVertex1.radius,2)
          - Math.pow(outsideVertex1.radius,2) );
      System.out.println("here lower 1");
    }
    else if ( outsideVertex2.Compare((DirectedVertex)(graph.outsideVerticies.elements[0]))
          && outsideVertex1.Compare((DirectedVertex)(graph.outsideVerticies.elements[1])) ) {
      vertex.position.x = outsideVertex2.position.x + outsideVertex2.radius;
      vertex.position.y = outsideVertex2.position.y - Math.sqrt( Math.pow(vertex.radius+outsideVertex2.radius,2)
          - Math.pow(outsideVertex2.radius,2) );
      System.out.println("here lower 2");
    }

    // left outside verticies
    if ( outsideVertex1.Compare((DirectedVertex)(graph.outsideVerticies.elements[0]))
          && outsideVertex2.Compare((DirectedVertex)(graph.outsideVerticies.elements[2])) ) {
      theta = Math.PI / 3 - arccos(outsideVertex2.radius + vertex.radius,
          outsideVertex1.radius + vertex.radius,
          outsideVertex1.radius + outsideVertex2.radius);
      xlength = (outsideVertex1.radius + vertex.radius) * Math.cos(theta);
      ylength = (outsideVertex1.radius + vertex.radius) * Math.sin(theta);
      vertex.position.x = outsideVertex1.position.x + xlength;
      vertex.position.y = outsideVertex1.position.y - ylength;
      System.out.println("here left 1");
    }
    else if ( outsideVertex2.Compare((DirectedVertex)(graph.outsideVerticies.elements[0]))
          && outsideVertex1.Compare((DirectedVertex)(graph.outsideVerticies.elements[2])) ) {
      theta = Math.PI / 3 - arccos(outsideVertex1.radius + vertex.radius,
          outsideVertex2.radius + vertex.radius,
          outsideVertex2.radius + outsideVertex1.radius);
      xlength = (outsideVertex2.radius + vertex.radius) * Math.cos(theta);
      ylength = (outsideVertex2.radius + vertex.radius) * Math.sin(theta);
      vertex.position.x = outsideVertex2.position.x + xlength;
      vertex.position.y = outsideVertex2.position.y - ylength;
      System.out.println("here left 2");
    }

    // right outside verticies
    if ( outsideVertex1.Compare((DirectedVertex)(graph.outsideVerticies.elements[1]))
          && outsideVertex2.Compare((DirectedVertex)(graph.outsideVerticies.elements[2])) ) {
      theta = Math.PI / 3 - arccos(outsideVertex2.radius + vertex.radius,
          outsideVertex1.radius + vertex.radius,
          outsideVertex1.radius + outsideVertex2.radius);
      xlength = (outsideVertex1.radius + vertex.radius) * Math.cos(theta);
      ylength = (outsideVertex1.radius + vertex.radius) * Math.sin(theta);
      vertex.position.x = outsideVertex1.position.x - xlength;
      vertex.position.y = outsideVertex1.position.y - ylength;
      System.out.println("here right 1");
    }
    else if ( outsideVertex2.Compare((DirectedVertex)(graph.outsideVerticies.elements[1]))
          && outsideVertex1.Compare((DirectedVertex)(graph.outsideVerticies.elements[2])) ) {
      theta = Math.PI / 3 - arccos(outsideVertex1.radius + vertex.radius,
          outsideVertex2.radius + vertex.radius,
          outsideVertex2.radius + outsideVertex1.radius);
      xlength = (outsideVertex2.radius + vertex.radius) * Math.cos(theta);
      ylength = (outsideVertex2.radius + vertex.radius) * Math.sin(theta);
      vertex.position.x = outsideVertex2.position.x - xlength;
      vertex.position.y = outsideVertex2.position.y - ylength;
      System.out.println("here right 2");
    }
    vertex.isDiscPos = true;
  }


  public static double SumOfAnglesAroundVertex(DirectedVertex  vertex)
  {
    DirectedVertex v1, v2;
    double sum = 0.0;

    for (int i=0, j=1; i<vertex.orderedEdges.length; i++, j++) {
      if (  vertex == ((DirectedEdge)(vertex.orderedEdges.elements[i])).start )
        v1 = ((DirectedEdge)(vertex.orderedEdges.elements[i])).end;
      else
        v1 = ((DirectedEdge)(vertex.orderedEdges.elements[i])).start;

      if (i == vertex.orderedEdges.length - 1)
        j = 0;
      if (  vertex == ((DirectedEdge)(vertex.orderedEdges.elements[j])).start )
        v2 = ((DirectedEdge)(vertex.orderedEdges.elements[j])).end;
      else
        v2 = ((DirectedEdge)(vertex.orderedEdges.elements[j])).start;

      sum += arccos( v1.radius + v2.radius, vertex.radius + v1.radius, vertex.radius + v2.radius );
    }
    return sum;
  }


  public static List CreateOrderedAdjEdgeList(DirectedVertex vertex)
  {
    List orderedList = new List();  // ordered list of edges
    List posNormalEdge;             // list of normalized edge positions
    List lowerHalf = new List();    // list of edges above the vertex
    List upperHalf = new List();    // list of edges below the vertex
    List lowerHalfPos = new List(); // list of normalized positions
                                    // mapped to lowerHalf
    List upperHalfPos = new List(); // list of normalized positions
                                    // mapped to upperHalf

    int i, j, k=0, l;               // loop and offset variables
    double xVal, prevX;             // x value limits for sorting

    // get list of normalized positions of adjacent edges
    posNormalEdge = CreateNormalEdgePosList(vertex, 20.0);

    // seperate edges into two sets:
    // those above the vertex and those below it
    for (i=0, j=0, k=0; i<vertex.inedges.length; i++) {
      if ( ((Position)(posNormalEdge.elements[i])).y >= vertex.position.y ) {
        lowerHalf.insert( vertex.inedges.get(i), j );
        lowerHalfPos.insert( posNormalEdge.elements[i], j++ );
      }
      else {
        upperHalf.insert( vertex.inedges.get(i), k );
        upperHalfPos.insert( posNormalEdge.elements[i], k++ );
      }
    }
    for (i=0; i<vertex.outedges.length; i++) {
      if ( ((Position)(posNormalEdge.elements[vertex.inedges.length + i])).y >= vertex.position.y ) {
        lowerHalf.insert( vertex.outedges.get(i), j );
        lowerHalfPos.insert( posNormalEdge.elements[vertex.inedges.length + i], j++ );
      }
      else {
        upperHalf.insert( vertex.outedges.get(i), k );
        upperHalfPos.insert( posNormalEdge.elements[vertex.inedges.length + i], k++ );
      }
    }


    // order the two lists so edges fall in a clockwise direction
    k = 0;
    prevX = 100000;
    // order the lower half first
    for (l=0; l<lowerHalf.length; l++) {
      xVal = 0;
      for (i=0, j=0; i<lowerHalf.length; i++) {
        if ( ((Position)(lowerHalfPos.get(i))).x >= xVal &&
            ((Position)(lowerHalfPos.get(i))).x < prevX) {
          xVal = ((Position)(lowerHalfPos.get(i))).x;
          j = i;
        }
      }
      orderedList.insert( lowerHalf.get(j), k++ );
      prevX = xVal;
    }

    // order the upper half next
    prevX = 0;
    for (l=0; l<upperHalf.length; l++) {
      xVal = 100000;
      for (i=0, j=0; i<upperHalf.length; i++) {
        if ( ((Position)(upperHalfPos.get(i))).x <= xVal &&
            ((Position)(upperHalfPos.get(i))).x > prevX) {
          xVal = ((Position)(upperHalfPos.get(i))).x;
          j = i;
        }
      }
      orderedList.insert( upperHalf.get(j), k++ );
      prevX = xVal;
    }
    return orderedList;
  }

  public static List CreateNormalEdgePosList(DirectedVertex vertex, double nlength)
  {
    // array of edges' normal positions
    List posNormalEdge = new List();
    int i, j;       // loop variables

    for (i=0; i<vertex.inedges.length; i++) {
      posNormalEdge.insert(
          normalEdgePos((DirectedEdge)(vertex.inedges.elements[i]),
            vertex.position, nlength),
          i );
    }
    j = i;
    for (i=0; i<vertex.outedges.length; i++, j++) {
      posNormalEdge.insert(
          normalEdgePos((DirectedEdge)(vertex.outedges.elements[i]),
            vertex.position, nlength),
          j );
    }
    return posNormalEdge;
  }

  public static Position normalEdgePos(DirectedEdge edge, Position pos, double length)
  {
    double adj;
    double hyp;
    double theta;
    double xlength, ylength;
    Position endpos;
    Position normalPos = new Position(0,0);

    if (pos == edge.start.position)
      endpos = edge.end.position;
    else
      endpos = edge.start.position;

    // find the angle between the edge and the x axis
    adj = Math.abs(pos.x-endpos.x);
    hyp = Math.sqrt(
        Math.pow(edge.start.position.x-edge.end.position.x,2) +
        Math.pow(edge.start.position.y-edge.end.position.y,2) );
    theta = Math.acos(adj/hyp);

    xlength = Math.cos(theta) * length;
    ylength = Math.sin(theta) * length;

    if (pos.x < endpos.x)
      normalPos.x = pos.x + xlength;
    else
      normalPos.x = pos.x - xlength;

    if (pos.y < endpos.y)
      normalPos.y = pos.y + ylength;
    else
      normalPos.y = pos.y - ylength;

    return normalPos;
  }


  public static double arccos(double a, double b, double c)
  {
    return Math.acos( (a*a - b*b - c*c) / (-2*b*c) );
  }

  public static int round(double d)
  {
	int i;
	double temp;
	
	i = (int)d;
	temp = d - i;
	
	if( temp < .5 )
  	  return i;
	i++;
	return i;
  }
}