// DirectedGraph.java
// Copyright (C) 2000 Linyuan Lu
// Code based on David Binger's Graph.java 
// Copyright (C) 1997 David Binger
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, 
// Boston, MA  02111-1307, USA.

// Version 0.1
import java.io.*;
import java.awt.*;

public class DirectedGraph extends Selectable
{
  //original graph vertices, edges, and faces  
  public List vertices = new List();
  public List edges = new List();
  public List faces = null;

  //dual graph vertices, edges and an external face
  public List dualVertices = new List();
  public List dualEdges = new List();
  public Face externalFace;
  public Image dualImg = null;
  private Dimension dualImageSize = new Dimension(0,0);
  private double sumOfAngles;
  private List tempVertices;
  private int quad1=5, quad2=10, quad3=10, quad4=5;
  Graphics dualGraph;
  DirectedVertex highestY=null;
  DirectedVertex lowestY=null;
  DirectedVertex highestX=null;
  DirectedVertex lowestX=null;

  public void resetDual()
  {
    dualEdges = new List();
    dualVertices = new List();
    externalFace = null;
    faces = new List();
    sumOfAngles = 0;
    tempVertices = null;      
    quad1=5;
    quad2=10;
    quad3=10;
    quad4=5;
    highestY=null;
    lowestY=null;
    highestX=null;
    lowestX=null;

  }
  
  public int getE(){
	int sum=0;
	int n=vertices.length;
	Object a[]=vertices.elements;
	for(int i=0;i<n;i++){
	    sum=sum+((DirectedVertex) a[i]).inDegree();
	}
	return sum;
  }

  public DirectedGraph() {}

  public final DirectedVertex vertex(int n) {
    return ((DirectedVertex)(vertices.elements[n]));
  }

  public final DirectedEdge edge(int n) {
    return ((DirectedEdge)(edges.elements[n]));
  }

  public final DirectedVertex addVertex(DirectedVertex v) {
    vertices.push(v);
    return v;
  }

  public final DirectedVertex addVertex() {
    DirectedVertex v = new DirectedVertex();
    vertices.push(v);
    return v;
  }

  public final DirectedVertex addVertex(int x,int y) {
    DirectedVertex v = new DirectedVertex(x,y);
    vertices.push(v);
    return v;
  }

  public final void delEdge(DirectedEdge e) {
    e.start.delOutEdge(e);
    e.end.delInEdge(e);
    edges.delete(e);
  }

  public final void delVertex(DirectedVertex v) {
     int n = v.inedges.length;
    Object a[] = v.inedges.elements;
    for (int j=0;j<n;j++) {
      DirectedEdge e = (DirectedEdge)a[j];
      edges.delete(e);
      e.start.delOutEdge(e);
    }
    n = v.outedges.length;
    Object b[] = v.outedges.elements;
    for (int j=0;j<n;j++) {
      DirectedEdge e = (DirectedEdge)b[j];
      edges.delete(e);
      e.end.delInEdge(e);
    }
    
    vertices.delete(v);
  }
  
  public final DirectedEdge addEdge(DirectedVertex a, DirectedVertex b) {
    DirectedEdge e = new DirectedEdge(a,b);
    int n=edges.length;
    Object x[]=edges.elements;
    for(int i=0;i<n;i++){
	if(e.start.equals(((DirectedEdge)x[i]).start)&&
	   e.end.equals(((DirectedEdge)x[i]).end)){
	    ((DirectedEdge)x[i]).multi+=e.multi; 
	    a.addOutEdge(e); 
	    b.addInEdge(e);
	    return ((DirectedEdge)x[i]);
	}
    }
     edges.push(e);
     a.addOutEdge(e); 
     b.addInEdge(e);
      return e;
  }

  public final DirectedEdge addEdge(int a,int b) {
    DirectedVertex v1 = (DirectedVertex)vertices.elements[a];
    DirectedVertex v2 = (DirectedVertex)vertices.elements[b];
    DirectedEdge edge = addEdge(v1,v2);    
    return edge;
  }    

  public String toString() {
    String s = "(graph\n";
    s += vertices.toString() +"\n";
    s += edges.toString();
    s = s +"\n)";
    return s;
  }
  
  public final void paint(Graphics g) {
    int n = edges.length;
    Object x[] = edges.elements;
    int j;
/*
    //original edges
    for (j=0;j<n;j++)
      ((DirectedEdge)x[j]).paint(g);
    n = edges.length;
    x = edges.elements;
    for (j=0;j<n;j++)
      ((DirectedEdge)x[j]).paintLabel(g);
    
    //original vertices
    n = vertices.length;
    x = vertices.elements;
    for (j=0;j<n;j++)
      ((DirectedVertex)x[j]).paint(g);
    for (j=0;j<n;j++)
      ((DirectedVertex)x[j]).paintLabel(g);    
*/

    for (j=0;j<n;j++)
      ((DirectedEdge)x[j]).paint(g);
    n = vertices.length;
    x = vertices.elements;
    for (j=0;j<n;j++)
      ((DirectedVertex)x[j]).paint(g);
    for (j=0;j<n;j++)
      ((DirectedVertex)x[j]).paintLabel(g);
    n = edges.length;
    x = edges.elements;
    for (j=0;j<n;j++)
      ((DirectedEdge)x[j]).paintLabel(g);
 

    //dual vertices
    n = dualVertices.length;
    x = dualVertices.elements;
    for (j=0;j<n;j++)
    {
      ((DirectedVertex)x[j]).changeColor = true;  //change color to red
      ((DirectedVertex)x[j]).paint(g);
      ((DirectedVertex)x[j]).changeColor = false;  //reset color to black
    }

    //dual edges
  n = dualEdges.length;
  if (n > 0)
  {   
      x = dualEdges.elements;
      for (j=0;j<n;j++)
      {
        ((DirectedEdge)x[j]).changeColor = true;    //change color to red
        ((DirectedEdge)x[j]).paintMyLine(g);
        ((DirectedEdge)x[j]).changeColor = false;    //reset color to black
      }
  }    
}

  // Move vertices and edges.
  public final void moveRelative(double x,double y) {
    int n = edges.length;
    Object a[] = edges.elements;
    int j;
    for (j=0;j<n;j++)
      ((DirectedEdge)a[j]).moveRelative(x,y);
    n = vertices.length;
    a = vertices.elements;
    for (j=0;j<n;j++)
      ((DirectedVertex)a[j]).moveRelative(x,y);
  }

  //checking if two edges are crossing
    public boolean isCrossing(DirectedEdge e1, DirectedEdge e2){
        if(e1.start==e2.start
           || e1.start==e2.end
           || e1.end==e2.start
           || e1.end==e2.end) return false;

        double s,t; //the affine coordinates respect to e1=AB and e2=CD.
        double e1x=e1.start.position.x - e1.end.position.x; // e1x is x coodinates of A-B.
        double e1y=e1.start.position.y - e1.end.position.y; // e1y is y coodinates of A-B.
        double e2x=e2.start.position.x - e2.end.position.x; // e2x is x coodinates of C-D.
        double e2y=e2.start.position.y - e2.end.position.y; // e2y is y coodinates of C-D.

        double dbx=e2.end.position.x-e1.end.position.x; // dbx is x coodinates of D-B.
        double dby=e2.end.position.y-e1.end.position.y; // dby is y coodinates of D-B.

        double determint=e1x * e2y - e1y * e2x;
        if(determint <0.001 && determint >0.001)
            return false; // e1 and e2 are parallel.
        s = (dbx * e2y -dby * e2x)/determint;
        t = (dbx * e1y -dby * e1x)/determint;
        if(0<s && s<1 && 0<t && t<1) return true;
        else return false;
    }


  /***********************************************************/
  /* addFaceIntoList:                                        */   
  /*        This function will add a face into a list of     */
  /*        faces if the face doesn't exist                  */
  /***********************************************************/
  private final void addFaceIntoList(Face f)
  {
        Face thisFace;
        if (faces.length == 0)
            faces.push(f);
        else
        {
            for (int i=0; i < faces.length; i++)
            {
                thisFace = (Face)(faces.elements[i]);
                //face already exist in the list
                if (thisFace.Compare(f))
                    return;
                //add new list
            }
            faces.push(f);
        }
  }

  public DirectedVertex findMidPoint (DirectedVertex v2, DirectedVertex v3,DirectedEdge e1)
  {
        DirectedVertex v1, v;        
        double x,y;
        //determine vertex 1
        if (v2.Compare(e1.start))
            v1 = e1.end;
        else   
            v1 = e1.start;
        
        x = (v1.position.x + v2.position.x + v3.position.x) / 3;
        y = (v1.position.y + v2.position.y + v3.position.y) / 3;
        
        v = new DirectedVertex(0,0);
        v.position.x = x;
        v.position.y = y;
        
        return v;
  }

  public Face findFace(DirectedVertex origin, DirectedEdge currentEdge, DirectedVertex currentVertex)
  {
        //find the angle for the given edge
        double angle = currentEdge.angle(currentVertex);
        Face f;
        DirectedVertex newEndPoint, midPoint=null;
        DirectedEdge e, edgeWithLargestAngle = null, rightNearestEdge = null;
                //Note: the rightNearestEdge is the edge to the right of the current edge,
                //      clockwise direction.

        //the currentVertex contains a list of outedges
        for (int i=0; i < currentVertex.myedges.length; i++)
        {
            //find the edge that has the angle smaller than the angle of the 
            //given edge
            e = (DirectedEdge)(currentVertex.myedges.elements[i]);
            if (!((e.start.Compare(currentEdge.start) && e.end.Compare(currentEdge.end)) ||
                (e.start.Compare(currentEdge.end) && e.end.Compare(currentEdge.start)) ||
                (e.end.Compare(currentEdge.start) && e.start.Compare(currentEdge.end))))
            {    
                if (angle > e.angle(currentVertex))
                {
                    if (rightNearestEdge == null)
                        rightNearestEdge = e;
                    else
                    {
                        //find the edge that has the largest angle than other edges
                        //which have the angle less than the angle of the current edge
                        if (rightNearestEdge.angle(currentVertex) < e.angle(currentVertex))
                            rightNearestEdge = e;
                    }
                }
                //find the edge that has the largest angle
                else
                {
                    if (edgeWithLargestAngle == null)
                        edgeWithLargestAngle = e;
                    else
                    {
                        if (edgeWithLargestAngle.angle(currentVertex) < e.angle(currentVertex))
                            edgeWithLargestAngle = e;
                    }
                }
            }
        }

        //if e equals null then we will use the edge that has largest angle;
        //otherwise use the edge that is nearest to the current edge
        if (rightNearestEdge != null)
            e = rightNearestEdge;
        else
            e = edgeWithLargestAngle;

        if (e == null) return null;
        
        //compute the new endpoint
        if (currentVertex.Compare(e.start))
            newEndPoint = e.end;
        else
            newEndPoint = e.start;
            
        //compute the angle between the given edge and the right nearest edge
        //add the angle into the total angle of a face
        if (rightNearestEdge == null)
            sumOfAngles = sumOfAngles + (angle + (360 - edgeWithLargestAngle.angle(currentVertex)));
        else
            sumOfAngles = sumOfAngles + (angle - rightNearestEdge.angle(currentVertex));

        //check to see if the currentVertex equals to the origin, if it is 
        //then the face is completed
        if (newEndPoint.Compare(origin))
        {            
            tempVertices.push(currentVertex);
            midPoint = findMidPoint(currentVertex,newEndPoint,currentEdge);
            //add the sum of angle into the face
            f = new Face(tempVertices,sumOfAngles,midPoint);
            //reset the sum of angle
            sumOfAngles = 0;
            return f;
        }
        else
        {
            //add the current vertex into a list of vertices which are used to
            //determine the face
            tempVertices.push(currentVertex);
            return findFace(origin,e,newEndPoint);
        }
  }
    
  /***********************************************************/
  /* findAllFaces:                                           */   
  /*        Determine all the faces for the given graph      */
  /***********************************************************/
  public final void findAllFaces()
  {
        DirectedVertex v,endVertex;
        DirectedEdge e;
        Face newFace = null;
        //For each vertex, find all the faces
        for (int i=0; i < vertices.length; i++)
        {
            v = (DirectedVertex)(vertices.elements[i]);
            //For each vertex, there are outedges connected to the vertex    
            for (int j=0; j < v.myedges.length; j++)
            {
                e = (DirectedEdge)(v.myedges.elements[j]);
                tempVertices = new List();
                //first point of the face
                tempVertices.push(v);


                //determine the end point of the edge
                if (v.Compare(e.start))
                    endVertex = e.end;
                else
                    endVertex = e.start;

                //find new face 
                newFace = findFace(v,e,endVertex);    

                //add new face into the list of faces
                if (newFace != null)
                    addFaceIntoList(newFace);                
            }
        }
  }

  /***********************************************************/
  /* findExtFace:                                            */   
  /*        Determine the external face for the given graph. */
  /*        There is only one external face for any graph    */
  /*        The external face can be calculated as follow:   */
  /*        1) For each face, find the largest edge          */
  /*        2) Find the face that has the largest edge       */
  /*        3) Store the external face in a global variable  */
  /*        4) Remove the external face from the list of     */
  /*           faces                                         */
  /***********************************************************/
  public final void findExtFace()
  {
        Face thisFace, f=null;
        
        //Choose a face that has the longest distance between vertices. 
        //The idea is that the external face almost always has a distance 
        //greater than the other distances from other faces        
        for (int i=0; i < faces.length; i++)
        {
            thisFace = (Face)(faces.elements[i]);
            if (i == 0)
                f = thisFace;
            else
            {
               //determine if this face has the longest distance between vertices
               //than the other face (f)
               if (thisFace.longestDistThan(f) == 0)
               {    
                    //if two faces has the same longest distance, the face has the
                    //largest sum of angles will be the external face
                    if (thisFace.sumOfAngles > f.sumOfAngles)
                        f = thisFace;
               }
               else if (thisFace.longestDistThan(f) == 1)
               {    //new longest distance
                    f = thisFace;
               }
            }
        }
        //after the loop, f should be an external face

        //store f into the external face of the graph
        if (f != null)
            externalFace = new Face(f.faceVertices,f.sumOfAngles,f.middlePoint);
        //reset the mid-point for the external face

        if (faces.length > 1)
            //remove f from the list of faces
            faces.delete(f);
  }

  /***********************************************************/
  /* findDualGraph:                                          */   
  /*        From all the faces and points inside the faces,  */
  /*        compute the dual graph                           */
  /***********************************************************/
  public final void findDualGraph()
  {
        Face thisFace;
        DirectedEdge e, newEdge, newEdge1;
        DirectedVertex vertexA=null, vertexB=null, vertexTemp=null;
        int counter = 1;
        
        //determine the vertices for the dual graph
        for (int i=0; i < faces.length; i++)
        {
            thisFace = (Face)(faces.elements[i]);
            dualVertices.push(thisFace.middlePoint);
        }
        
        //determine the edges for the dual graph
        //For a particular edge find two faces those are connected
        //together by the edge
        for (int i=0; i < edges.length; i++)
        {
            e = (DirectedEdge)(edges.elements[i]);
            
            if (faces.length > 1)
            {
                //this loop will not compute the dual edge for two faces where one
                //face is the external face
                for (int j=0; j < faces.length; j++)
                {
                    thisFace = (Face)(faces.elements[j]);
                    if ((counter == 1) && (thisFace.isEdgeAdjacentToFace(e)))
                    {
                        vertexA = thisFace.middlePoint;
                        counter++;
                    }
                    else if ((counter == 2) && (thisFace.isEdgeAdjacentToFace(e)))
                    {
                        vertexB = thisFace.middlePoint;
                        vertexTemp = e.midEdge();
                        newEdge = new DirectedEdge(vertexA,vertexTemp);
                        newEdge1 = new DirectedEdge(vertexTemp,vertexB);
                        dualEdges.push(newEdge);
                        dualEdges.push(newEdge1);
                        break;
                    }
                }            

                //determine external point
                for (int j=0; j < faces.length; j++)
                {
                    thisFace = (Face)(faces.elements[j]);
                    if (j == 0)
                    {
                        highestY = (DirectedVertex)(thisFace.faceVertices.elements[0]);
                        lowestY = (DirectedVertex)(thisFace.faceVertices.elements[0]);
                        highestX = (DirectedVertex)(thisFace.faceVertices.elements[0]);
                        lowestX = (DirectedVertex)(thisFace.faceVertices.elements[0]);
                    }
                    
                    for (int k = 1; k < thisFace.faceVertices.length; k++)
                    {   
                        vertexA = (DirectedVertex)thisFace.faceVertices.elements[k];

                        if (vertexA.position.y < highestY.position.y)
                            highestY = vertexA;
                        else if (vertexA.position.y > lowestY.position.y)
                            lowestY = vertexA;

                        if (vertexA.position.x > highestX.position.x)
                            highestX = vertexA;
                        else if (vertexA.position.x < lowestX.position.x)
                            lowestX = vertexA;
                    }
                }    

                externalFace.middlePoint = new DirectedVertex(0,0);
                externalFace.middlePoint.position.x = highestX.position.x+60;
                externalFace.middlePoint.position.y =(highestY.position.y+lowestY.position.y)/2;
                dualVertices.push(externalFace.middlePoint);
                
                //determine the dual edge for the external face and another face
                for (int j=0; j < faces.length; j++)
                {
                    thisFace = (Face)(faces.elements[j]);
                    if ((thisFace.isEdgeAdjacentToFace(e)) && 
                        (externalFace.isEdgeAdjacentToFace(e)))
                    {
                        outerPoint(thisFace,e);
                        break;
                    }
                }
                counter = 1;    
                
            }
            else
            {    
                //determine the dual edge for the external face and another face
                for (int j=0; j < faces.length; j++)
                {
                    thisFace = (Face)(faces.elements[j]);
                    if ((thisFace.isEdgeAdjacentToFace(e)) && 
                        (externalFace.isEdgeAdjacentToFace(e)))
                    {
                        //reset external midpoint (will be recalculated in function outerPoint)
                        externalFace.middlePoint = null;
                        outerPoint(thisFace,e);
                        break;
                    }
                }
            }
        }
  }

  public void outerPoint(Face f, DirectedEdge edge)
  {
    DirectedVertex vertex;
    DirectedVertex outerPt;
    DirectedEdge insideEdge;
    DirectedVertex extendedPt;
    DirectedEdge upperEdge;
    DirectedEdge extendedEdge;
    DirectedEdge lastEdge;
    DirectedVertex upperPt;
    DirectedVertex lowerPt;
    DirectedEdge lowerEdge;
    DirectedVertex sidePt;
    DirectedEdge sideEdge;
    
    if (externalFace.middlePoint != null)
        outerPt = externalFace.middlePoint;
    else
    {
        highestY = (DirectedVertex)(f.faceVertices.elements[0]);
        lowestY = (DirectedVertex)(f.faceVertices.elements[0]);
        highestX = (DirectedVertex)(f.faceVertices.elements[0]);
        lowestX = (DirectedVertex)(f.faceVertices.elements[0]);

        for (int i = 1; i < f.faceVertices.length; i++)
        {   

            vertex = (DirectedVertex)f.faceVertices.elements[i];

            if (vertex.position.y < highestY.position.y)
                highestY = vertex;
            else if (vertex.position.y > lowestY.position.y)
                lowestY = vertex;

            if (vertex.position.x > highestX.position.x)
                highestX = vertex;
            else if (vertex.position.x < lowestX.position.x)
                lowestX = vertex;
        }
        
        outerPt = new DirectedVertex(0,0);
        outerPt.position.x = highestX.position.x+60;
        outerPt.position.y =(highestY.position.y+lowestY.position.y)/2;
        dualVertices.push(outerPt);
    }
    
    insideEdge = new DirectedEdge(f.middlePoint,edge.midEdge());
    dualEdges.push(insideEdge);
    
    if (insideEdge.quadrant(f.middlePoint) == 1)
    {
        upperPt = new DirectedVertex(0,0);
        upperPt.position.x = edge.midEdge().position.x;
        upperPt.position.y = highestY.position.y - (quad1 * 5);
        extendedPt = new DirectedVertex(0,0);
        extendedPt.position.x = highestX.position.x + 30;
        extendedPt.position.y = upperPt.position.y;

        upperEdge = new DirectedEdge(edge.midEdge(), upperPt);
        extendedEdge = new DirectedEdge(upperPt, extendedPt);
        lastEdge = new DirectedEdge(extendedPt, outerPt);
        
        //add dual edges
        dualEdges.push(upperEdge);
        dualEdges.push(extendedEdge);
        dualEdges.push(lastEdge);
        quad1++;
    }
    else if (insideEdge.quadrant(f.middlePoint) == 2)
    {
        upperPt = new DirectedVertex(0,0);
        upperPt.position.x = edge.midEdge().position.x;
        upperPt.position.y = highestY.position.y - (quad2 * 5);

        extendedPt = new DirectedVertex(0,0);
        extendedPt.position.x = highestX.position.x+ 30;
        extendedPt.position.y =  upperPt.position.y;

        upperEdge = new DirectedEdge(edge.midEdge(), upperPt);
        extendedEdge = new DirectedEdge(upperPt, extendedPt);
        lastEdge = new DirectedEdge(extendedPt, outerPt);

        //add dual edges
        dualEdges.push(upperEdge);
        dualEdges.push(extendedEdge);
        dualEdges.push(lastEdge);
        quad2++;
    }
    else if (insideEdge.quadrant(f.middlePoint) == 3)
    {
        lowerPt = new DirectedVertex(0,0);
        lowerPt.position.x = edge.midEdge().position.x;
        lowerPt.position.y = lowestY.position.y+ (quad3 *5);

        extendedPt = new DirectedVertex(0,0);
        extendedPt.position.x = highestX.position.x + 30;
        extendedPt.position.y = lowerPt.position.y;

        lowerEdge = new DirectedEdge(edge.midEdge(), lowerPt);
        extendedEdge = new DirectedEdge(lowerPt, extendedPt);
        lastEdge = new DirectedEdge(extendedPt, outerPt);

        //add dual edges
        dualEdges.push(lowerEdge);
        dualEdges.push(extendedEdge);
        dualEdges.push(lastEdge);
        quad3--;
    }
    else if (insideEdge.quadrant(f.middlePoint) == 4)
    {
        lowerPt = new DirectedVertex(0,0);
        lowerPt.position.x = edge.midEdge().position.x;
        lowerPt.position.y = lowestY.position.y + (quad4 * 5);
        extendedPt = new DirectedVertex(0,0);
        extendedPt.position.x = highestX.position.x + 30;
        extendedPt.position.y = lowerPt.position.y;

        lowerEdge = new DirectedEdge(edge.midEdge(), lowerPt);
        extendedEdge = new DirectedEdge(lowerPt, extendedPt);
        lastEdge = new DirectedEdge(extendedPt, outerPt);

        //add dual edges
        dualEdges.push(lowerEdge);
        dualEdges.push(extendedEdge);
        dualEdges.push(lastEdge);        
        quad4--;
    }
    else if (insideEdge.quadrant(f.middlePoint) == 5)
    {
        lastEdge = new DirectedEdge(edge.midEdge(), outerPt);

        //add dual edges
        dualEdges.push(lastEdge);
    }
    else if (insideEdge.quadrant(f.middlePoint) == 6)
    {
        sidePt = new DirectedVertex(0,0);
        sidePt.position.x = edge.midEdge().position.x - 10;
        sidePt.position.y = edge.midEdge().position.y;

        lowerPt = new DirectedVertex(0,0);
        lowerPt.position.x = sidePt.position.x;
        lowerPt.position.y = lowestY.position.y + 10;

        extendedPt = new DirectedVertex(0,0);
        extendedPt.position.x = lowestX.position.x + 30;
        extendedPt.position.y = lowerPt.position.y;

        sideEdge = new DirectedEdge(edge.midEdge(), sidePt);
        lowerEdge = new DirectedEdge(sidePt, lowerPt);
        extendedEdge = new DirectedEdge(lowerPt, extendedPt);
        lastEdge = new DirectedEdge(extendedPt, outerPt);

        //add dual edges
        dualEdges.push(sideEdge);
        dualEdges.push(lowerEdge);
        dualEdges.push(extendedEdge);
        dualEdges.push(lastEdge);
    }
    else if (insideEdge.quadrant(f.middlePoint) == 7)
    {
        upperPt = new DirectedVertex(0,0);
        upperPt.position.x = edge.midEdge().position.x;
        upperPt.position.y = highestY.position.y - 10;

        extendedPt = new DirectedVertex(0,0);
        extendedPt.position.x = highestX.position.x + 30;
        extendedPt.position.y = upperPt.position.y;

        upperEdge = new DirectedEdge(edge.midEdge(), upperPt);
        extendedEdge = new DirectedEdge(upperPt, extendedPt);
        lastEdge = new DirectedEdge(extendedPt, outerPt);
        
        //add dual edges
        dualEdges.push(upperEdge);
        dualEdges.push(extendedEdge);
        dualEdges.push(lastEdge);
    }
    else if (insideEdge.quadrant(f.middlePoint) == 8)
    {
        lowerPt = new DirectedVertex(0,0);
        lowerPt.position.x = edge.midEdge().position.x;
        lowerPt.position.y = lowestY.position.y+10;

        extendedPt = new DirectedVertex(0,0);
        extendedPt.position.x = highestX.position.x + 30;
        extendedPt.position.y = lowerPt.position.y;

        lowerEdge = new DirectedEdge(edge.midEdge(), lowerPt);
        extendedEdge = new DirectedEdge(lowerPt, extendedPt);
        lastEdge = new DirectedEdge(extendedEdge.end, outerPt);
        
        //add dual edges
        dualEdges.push(lowerEdge);
        dualEdges.push(extendedEdge);
        dualEdges.push(lastEdge);
    }
  }
}