/*******************************************************************************
+
+  LEDA 3.5
+
+  convex_hull.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.
+ 
*******************************************************************************/

struct ch_edge {

POINT   source;
POINT   target;
ch_edge* succ;
ch_edge* pred;
ch_edge* link;
bool     outside;

ch_edge(const POINT& a, const POINT& b) : source(a), target(b) 
{ outside = true; }

~ch_edge() {}

};


static void MoveExtremesToFront(list<POINT>& L)
{
  // copy four extreme points to the front of |L|

  if (L.size() < 4) return;

  POINT p  = L.head();
  POINT le = p;
  POINT ri = p;
  POINT bo = p;
  POINT to = p;

  forall(p,L)
  { COORD x = p.xcoord();
    COORD y = p.ycoord();
    if (x < le.xcoord() || x == le.xcoord() && y < le.ycoord()) le = p;
    if (x > ri.xcoord() || x == ri.xcoord() && y > ri.ycoord()) ri = p;
    if (y < bo.ycoord() || y == bo.ycoord() && x > bo.xcoord()) bo = p;
    if (y > to.ycoord() || y == to.ycoord() && x < to.xcoord()) to = p;
   }
 
  L.push(le);
  L.push(ri);
  L.push(to);
  L.push(bo);
}



list<POINT>  CONVEX_HULL(list<POINT> L)
{ 
  list<POINT> CH;

  if (L.empty()) return CH;

  MoveExtremesToFront(L);

  list_item it = L.first();

  POINT A = L[it];
  it = L.succ(it);

  while (it && A == L[it])  it = L.succ(it);

  if (it == nil) 
  { CH.append(A);
    return CH;
   }

  POINT B = L[it];
  it = L.succ(it);

  while (it && collinear(A,B,L[it])) 
  { POINT p = L[it]; 
    if (left_turn(A,B,p.rotate90(B))) B = p;
    else
      if (left_turn(B,A,p.rotate90(A))) A = p;
    it = L.succ(it);
   }


  ch_edge* T1 = new ch_edge(A,B);
  ch_edge* T2 = new ch_edge(B,A);

  ch_edge* last_edge = T2;
  T2->link = T1;
  T1->link = nil;

  T1->succ = T2;
  T1->pred = T2;
  T2->succ = T1;
  T2->pred = T1;

  // scan remaining points

  while (it != nil)
  { POINT P = L[it];
    it = L.succ(it);

    ch_edge* p = (right_turn(A,B,P)) ?  T1 : T2;

    while (! p->outside)
    { ch_edge* r0 = p->pred;
      if (right_turn(r0->source,r0->target,P)) p = r0;
      else { ch_edge* r1 = p->succ;
             if (right_turn(r1->source,r1->target,P)) p = r1;
             else { p =  nil; break; }
            }
     }

    if (p == nil) continue;  // P inside current hull

    // compute "upper" tangent (p,high->source)
    ch_edge* high = p->succ;
    while (orientation(high->source,high->target,P) <= 0) high = high->succ;


    // compute "lower" tangent (p,low->target)
    ch_edge* low = p->pred;
    while (orientation(low->source,low->target,P) <= 0) low = low->pred;


    p = low->succ;  // p = successor of low edge

    // insert two edges between "low" and "high"

    ch_edge* e_l = new ch_edge(low->target,P);
    ch_edge* e_h = new ch_edge(P,high->source);

    e_h->link = e_l;
    e_l->link = last_edge;
    last_edge = e_h;

    e_h->succ = high;
    e_l->pred = low;
    high->pred = e_l->succ = e_h;
    low->succ  = e_h->pred = e_l;


    // mark edges between low and high as "inside" and define refinements
    while (p != high)
    { ch_edge* q = p->succ;
      p->pred = e_l;
      p->succ = e_h;
      p->outside = false;
      p = q;
     }
   }

 // return list of vertices

  CH.append(last_edge->source);
  for(ch_edge* p = last_edge->succ; p != last_edge; p = p->succ) 
     CH.append(p->source);

 // clean up 

  while (last_edge)
  { ch_edge* p = last_edge;
    last_edge = last_edge->link;
    delete p;
   }

  return CH;
}


