public AdvancingFront(AdvancingFrontNode head, AdvancingFrontNode tail)
 {
     Head = head;
     Tail = tail;
     Search = head;
     AddNode(head);
     AddNode(tail);
 }

 private static void FillRightAboveEdgeEvent(DTSweepContext tcx, DTSweepConstraint edge, AdvancingFrontNode node)
 {
     while (node.Next.Point.X < edge.P.X)
     {
         // Check if next node is below the edge
         Orientation o1 = TriangulationUtil.Orient2d(edge.Q, node.Next.Point, edge.P);
         if (o1 == Orientation.CCW)
         {
             FillRightBelowEdgeEvent(tcx, edge, node);
         }
         else
         {
             node = node.Next;
         }
     }
 }

 private static void FillLeftConcaveEdgeEvent(DTSweepContext tcx, DTSweepConstraint edge, AdvancingFrontNode node)
 {
     Fill(tcx, node.Prev);
     if (node.Prev.Point != edge.P)
     {
         // Next above or below edge?
         if (TriangulationUtil.Orient2d(edge.Q, node.Prev.Point, edge.P) == Orientation.CW)
         {
             // Below
             if (TriangulationUtil.Orient2d(node.Point, node.Prev.Point, node.Prev.Prev.Point) == Orientation.CW)
             {
                 // Next is concave
                 FillLeftConcaveEdgeEvent(tcx, edge, node);
             }
             else
             {
                 // Next is convex
             }
         }
     }
 }

 private static void FillEdgeEvent(DTSweepContext tcx, DTSweepConstraint edge, AdvancingFrontNode node)
 {
     if (tcx.EdgeEvent.Right)
     {
         FillRightAboveEdgeEvent(tcx, edge, node);
     }
     else
     {
         FillLeftAboveEdgeEvent(tcx, edge, node);
     }
 }

        /// <summary>
        /// Recursive algorithm to fill a Basin with triangles
        /// </summary>
        private static void FillBasinReq(DTSweepContext tcx, AdvancingFrontNode node)
        {
            // if shallow stop filling
            if (IsShallow(tcx, node))
            {
                return;
            }

            Fill(tcx, node);
            if (node.Prev == tcx.Basin.leftNode && node.Next == tcx.Basin.rightNode)
            {
                return;
            }
            else if (node.Prev == tcx.Basin.leftNode)
            {
                Orientation o = TriangulationUtil.Orient2d(node.Point, node.Next.Point, node.Next.Next.Point);
                if (o == Orientation.CW)
                {
                    return;
                }
                node = node.Next;
            }
            else if (node.Next == tcx.Basin.rightNode)
            {
                Orientation o = TriangulationUtil.Orient2d(node.Point, node.Prev.Point, node.Prev.Prev.Point);
                if (o == Orientation.CCW)
                {
                    return;
                }
                node = node.Prev;
            }
            else
            {
                // Continue with the neighbor node with lowest Y value
                if (node.Prev.Point.Y < node.Next.Point.Y)
                {
                    node = node.Prev;
                }
                else
                {
                    node = node.Next;
                }
            }
            FillBasinReq(tcx, node);
        }

 private AdvancingFrontNode LocateNode(double x)
 {
     AdvancingFrontNode node = FindSearchNode(x);
     if (x < node.Value)
     {
         while ((node = node.Prev) != null)
             if (x >= node.Value)
             {
                 Search = node;
                 return node;
             }
     }
     else
     {
         while ((node = node.Next) != null)
             if (x < node.Value)
             {
                 Search = node.Prev;
                 return node.Prev;
             }
     }
     return null;
 }

        // True if HoleAngle exceeds 90 degrees.
        private static bool LargeHole_DontFill(AdvancingFrontNode node)
        {
            AdvancingFrontNode nextNode = node.Next;
            AdvancingFrontNode prevNode = node.Prev;
            if (!AngleExceeds90Degrees(node.Point, nextNode.Point, prevNode.Point))
                return false;

            // Check additional points on front.
            AdvancingFrontNode next2Node = nextNode.Next;
            // "..Plus.." because only want angles on same side as point being added.
            if ((next2Node != null) && !AngleExceedsPlus90DegreesOrIsNegative(node.Point, next2Node.Point, prevNode.Point))
                return false;

            AdvancingFrontNode prev2Node = prevNode.Prev;
            // "..Plus.." because only want angles on same side as point being added.
            if ((prev2Node != null) && !AngleExceedsPlus90DegreesOrIsNegative(node.Point, nextNode.Point, prev2Node.Point))
                return false;

            return true;
        }

 /// <summary>
 /// ???
 /// </summary>
 /// <param name="node">middle node</param>
 /// <returns>the angle between 3 front nodes</returns>
 private static double HoleAngle(AdvancingFrontNode node)
 {
     // XXX: do we really need a signed angle for holeAngle?
     //      could possible save some cycles here
     /* Complex plane
      * ab = cosA +i*sinA
      * ab = (ax + ay*i)(bx + by*i) = (ax*bx + ay*by) + i(ax*by-ay*bx)
      * atan2(y,x) computes the principal value of the argument function
      * applied to the complex number x+iy
      * Where x = ax*bx + ay*by
      *       y = ax*by - ay*bx
      */
     double px = node.Point.X;
     double py = node.Point.Y;
     double ax = node.Next.Point.X - px;
     double ay = node.Next.Point.Y - py;
     double bx = node.Prev.Point.X - px;
     double by = node.Prev.Point.Y - py;
     return Math.Atan2(ax * by - ay * bx, ax * bx + ay * by);
 }

        private static void EdgeEvent(DTSweepContext tcx, DTSweepConstraint edge, AdvancingFrontNode node)
        {
            try
            {
                tcx.EdgeEvent.ConstrainedEdge = edge;
                tcx.EdgeEvent.Right = edge.P.X > edge.Q.X;

                if (IsEdgeSideOfTriangle(node.Triangle, edge.P, edge.Q))
                {
                    return;
                }

                // For now we will do all needed filling
                // TODO: integrate with flip process might give some better performance
                //       but for now this avoid the issue with cases that needs both flips and fills
                FillEdgeEvent(tcx, edge, node);

                EdgeEvent(tcx, edge.P, edge.Q, node.Triangle, edge.Q);
            }
            catch (PointOnEdgeException e)
            {
                Debug.WriteLine("Skipping Edge: {0}", e.Message);
            }
        }

 /// <summary>
 /// The basin angle is decided against the horizontal line [1,0]
 /// </summary>
 private static double BasinAngle(AdvancingFrontNode node)
 {
     double ax = node.Point.X - node.Next.Next.Point.X;
     double ay = node.Point.Y - node.Next.Next.Point.Y;
     return Math.Atan2(ay, ax);
 }

 /// <summary>
 /// We will traverse the entire advancing front and fill it to form a convex hull.
 /// </summary>
 private static void TurnAdvancingFrontConvex(DTSweepContext tcx, AdvancingFrontNode b, AdvancingFrontNode c)
 {
     AdvancingFrontNode first = b;
     while (c != tcx.aFront.Tail)
     {
         if (TriangulationUtil.Orient2d(b.Point, c.Point, c.Next.Point) == Orientation.CCW)
         {
             // [b,c,d] Concave - fill around c
             Fill(tcx, c);
             c = c.Next;
         }
         else
         {
             // [b,c,d] Convex
             if (b != first && TriangulationUtil.Orient2d(b.Prev.Point, b.Point, c.Point) == Orientation.CCW)
             {
                 // [a,b,c] Concave - fill around b
                 Fill(tcx, b);
                 b = b.Prev;
             }
             else
             {
                 // [a,b,c] Convex - nothing to fill
                 b = c;
                 c = c.Next;
             }
         }
     }
 }

 public void RemoveNode(AdvancingFrontNode node)
 {
     //_searchTree.delete( node.key );
 }

 public void AddNode(AdvancingFrontNode node)
 {
     //_searchTree.put(node.key, node);
 }

        /// <summary>
        /// This implementation will use simple node traversal algorithm to find a point on the front
        /// </summary>
        public AdvancingFrontNode LocatePoint(TriangulationPoint point)
        {
            double px = point.X;
            AdvancingFrontNode node = FindSearchNode(px);
            double nx = node.Point.X;

            if (px == nx)
            {
                if (point != node.Point)
                {
                    // We might have two nodes with same x value for a short time
                    if (point == node.Prev.Point)
                    {
                        node = node.Prev;
                    }
                    else if (point == node.Next.Point)
                    {
                        node = node.Next;
                    }
                    else
                    {
                        throw new Exception("Failed to find Node for given afront point");
                        //node = null;
                    }
                }
            }
            else if (px < nx)
            {
                while ((node = node.Prev) != null)
                {
                    if (point == node.Point)
                    {
                        break;
                    }
                }
            }
            else
            {
                while ((node = node.Next) != null)
                {
                    if (point == node.Point)
                    {
                        break;
                    }
                }
            }
            Search = node;
            return node;
        }

 private static void FillRightBelowEdgeEvent(DTSweepContext tcx, DTSweepConstraint edge, AdvancingFrontNode node)
 {
     if (node.Point.X < edge.P.X) // needed?
     {
         if (TriangulationUtil.Orient2d(node.Point, node.Next.Point, node.Next.Next.Point) == Orientation.CCW)
         {
             // Concave
             FillRightConcaveEdgeEvent(tcx, edge, node);
         }
         else
         {
             // Convex
             FillRightConvexEdgeEvent(tcx, edge, node);
             // Retry this one
             FillRightBelowEdgeEvent(tcx, edge, node);
         }
     }
 }

        /// <summary>
        /// Adds a triangle to the advancing front to fill a hole.
        /// </summary>
        /// <param name="tcx"></param>
        /// <param name="node">middle node, that is the bottom of the hole</param>
        private static void Fill(DTSweepContext tcx, AdvancingFrontNode node)
        {
            DelaunayTriangle triangle = new DelaunayTriangle(node.Prev.Point, node.Point, node.Next.Point);
            // TODO: should copy the cEdge value from neighbor triangles
            //       for now cEdge values are copied during the legalize
            triangle.MarkNeighbor(node.Prev.Triangle);
            triangle.MarkNeighbor(node.Triangle);
            tcx.Triangles.Add(triangle);

            // Update the advancing front
            node.Prev.Next = node.Next;
            node.Next.Prev = node.Prev;
            tcx.RemoveNode(node);

            // If it was legalized the triangle has already been mapped
            if (!Legalize(tcx, triangle))
            {
                tcx.MapTriangleToNodes(triangle);
            }
        }

 private static void FillRightConvexEdgeEvent(DTSweepContext tcx, DTSweepConstraint edge, AdvancingFrontNode node)
 {
     // Next concave or convex?
     if (TriangulationUtil.Orient2d(node.Next.Point, node.Next.Next.Point, node.Next.Next.Next.Point) ==
         Orientation.CCW)
     {
         // Concave
         FillRightConcaveEdgeEvent(tcx, edge, node.Next);
     }
     else
     {
         // Convex
         // Next above or below edge?
         if (TriangulationUtil.Orient2d(edge.Q, node.Next.Next.Point, edge.P) == Orientation.CCW)
         {
             // Below
             FillRightConvexEdgeEvent(tcx, edge, node.Next);
         }
         else
         {
             // Above
         }
     }
 }

        /// <summary>
        /// Fills holes in the Advancing Front
        /// </summary>
        private static void FillAdvancingFront(DTSweepContext tcx, AdvancingFrontNode n)
        {
            double angle;

            // Fill right holes
            AdvancingFrontNode node = n.Next;
            while (node.HasNext)
            {
                // if HoleAngle exceeds 90 degrees then break.
                if (LargeHole_DontFill(node))
                    break;

                Fill(tcx, node);
                node = node.Next;
            }

            // Fill left holes
            node = n.Prev;
            while (node.HasPrev)
            {
                // if HoleAngle exceeds 90 degrees then break.
                if (LargeHole_DontFill(node))
                    break;

                angle = HoleAngle(node);
                if (angle > PI_div2 || angle < -PI_div2)
                {
                    break;
                }
                Fill(tcx, node);
                node = node.Prev;
            }

            // Fill right basins
            if (n.HasNext && n.Next.HasNext)
            {
                angle = BasinAngle(n);
                if (angle < PI_3div4)
                {
                    FillBasin(tcx, n);
                }
            }
        }

        private static bool IsShallow(DTSweepContext tcx, AdvancingFrontNode node)
        {
            double height;

            if (tcx.Basin.leftHighest)
            {
                height = tcx.Basin.leftNode.Point.Y - node.Point.Y;
            }
            else
            {
                height = tcx.Basin.rightNode.Point.Y - node.Point.Y;
            }
            if (tcx.Basin.width > height)
            {
                return true;
            }
            return false;
        }

        /// <summary>
        /// Fills a basin that has formed on the Advancing Front to the right
        /// of given node.
        /// First we decide a left,bottom and right node that forms the 
        /// boundaries of the basin. Then we do a reqursive fill.
        /// </summary>
        /// <param name="tcx"></param>
        /// <param name="node">starting node, this or next node will be left node</param>
        private static void FillBasin(DTSweepContext tcx, AdvancingFrontNode node)
        {
            if (TriangulationUtil.Orient2d(node.Point, node.Next.Point, node.Next.Next.Point) == Orientation.CCW)
            {
                // tcx.basin.leftNode = node.next.next;
                tcx.Basin.leftNode = node;
            }
            else
            {
                tcx.Basin.leftNode = node.Next;
            }

            // Find the bottom and right node
            tcx.Basin.bottomNode = tcx.Basin.leftNode;
            while (tcx.Basin.bottomNode.HasNext && tcx.Basin.bottomNode.Point.Y >= tcx.Basin.bottomNode.Next.Point.Y)
            {
                tcx.Basin.bottomNode = tcx.Basin.bottomNode.Next;
            }

            if (tcx.Basin.bottomNode == tcx.Basin.leftNode)
            {
                // No valid basins
                return;
            }

            tcx.Basin.rightNode = tcx.Basin.bottomNode;
            while (tcx.Basin.rightNode.HasNext && tcx.Basin.rightNode.Point.Y < tcx.Basin.rightNode.Next.Point.Y)
            {
                tcx.Basin.rightNode = tcx.Basin.rightNode.Next;
            }

            if (tcx.Basin.rightNode == tcx.Basin.bottomNode)
            {
                // No valid basins
                return;
            }

            tcx.Basin.width = tcx.Basin.rightNode.Point.X - tcx.Basin.leftNode.Point.X;
            tcx.Basin.leftHighest = tcx.Basin.leftNode.Point.Y > tcx.Basin.rightNode.Point.Y;

            FillBasinReq(tcx, tcx.Basin.bottomNode);
        }