/*******************************************************************************
+
+  LEDA 3.5
+
+  triangulation.c
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/
//------------------------------------------------------------------------------
// TRIANGULATIONS
//
// - TRIANGULATE_POINTS
//------------------------------------------------------------------------------

#define left_bend(p,e)   (orientation(p,G[source(e)],G[target(e)]) > 0)

edge TRIANGULATE_POINTS(const list<POINT>& L0, GRAPH<POINT,int>& G)
{ 
  G.clear();
  if (L0.empty()) return nil;

  list<POINT> L = L0;

  L.sort();  

  // initizialize G with a single edge starting at the first point

  POINT last_p = L.pop();            // last visited point
  node  last_v = G.new_node(last_p); // last inserted node

  while (!L.empty() && last_p == L.head()) L.pop();

  if (!L.empty())
  { last_p = L.pop();
    node v = G.new_node(last_p);
    edge x = G.new_edge(last_v,v,0);
    edge y = G.new_edge(v,last_v,0);
    G.set_reversal(x,y);
    last_v = v;
   }

  // scan remaining points

  POINT p;
  forall(p,L) 
  { if (p == last_p) continue; 

    edge e =  G.last_adj_edge(last_v);

    last_v = G.new_node(p);
    last_p = p;

    // walk up to upper tangent
    do e = G.pred_face_edge(e); while (left_bend(p,e));

    // walk down to lower tangent and triangulate
    do { edge succ_e = G.succ_face_edge(e);
         edge x = G.new_edge(succ_e,last_v,0,0);
         edge y = G.new_edge(last_v,source(succ_e),0);
         G.set_reversal(x,y);
         e = succ_e;
       } while (left_bend(p,e));
   }

  // mark edges of convex hull as HULL_EDGES

  edge hull_edge = G.last_edge();

  edge e = hull_edge;
  do { G[e] = HULL_EDGE;
       e = G.face_cycle_succ(e);
     } while (e != hull_edge); 


  return hull_edge;
}

