// chull_2pass.H
// find the convex hull of a set of points (C++ template)
// incremental two pass algorithm 
// Version : 1.0
// Last modified: 1999/08/23 18:45:56
// Author : R. Wenger

/* Copyright (c) 1998 by The Ohio State University
 *
 * Permission to use, copy, modify, distribute, and sell this software 
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and/or
 * modified versions and that both that copyright notice and this 
 * permission notice appear in supporting documentation.  This software 
 * is provided "as is" without express or implied warranty, including 
 * but not limited to the warranties of merchantibility, fitness for 
 * a particular purpose and noninfringement.
 *
 */

#ifndef CHULL_2PASS_H
#define CHULL_2PASS_H

#include <algo.h>


#ifndef SWAP_ARG
#define SWAP_ARG

// function adaptor. swap function arguments.
// swap_arg(func)(a,b) = func(b, a)

template <class ARG>
  class swap_arg {

    protected :
      bool (*F)(ARG &, ARG &);

    public :
      swap_arg(bool (*func) (ARG &, ARG &)) : 
	F(func) {};
      bool operator()(ARG & a, ARG & b) const 
        { return(F(b,a)); }
  };

#endif SWAP_ARG


template <class POINT_ITER, class POINT, class ORESULT>
void chull_2pass(POINT_ITER firstp, POINT_ITER endp, 
		 bool (*compare) (POINT &, POINT &), 
		 ORESULT (*orient) (POINT &, POINT &, POINT &), 
		 POINT_ITER & endc)
// reorder points [firstp,endp) so that the points [firstp,endc) are 
// (extremal) vertices of the convex hull in counter-clockwise order
//
// POINT_ITER = random access iterator (pointer to objects in an array)
// COMPARE = comparison function defining a total ordering on points
// ORIENT = calculate orientation of 3 points
// firstp = iterator (pointer) referring to first element
// endp = iterator (pointer) which is past-the-end of points
// orient = calculate orientation of 3 points
// compare = point comparison function
// endc = iterator (pointer) which is past-the-end of the convex hull points

/* 
   POINT = type of object pointed to by POINT_ITER

   compare(POINT p1,p2) = 
     return 1 if p1.x < p2.x or (p1.x == p2.x and p1.y < p2.y)

   orient(POINT p1,p2,p3) = returns orientation of points p1, p2, p3 
     (pos = left, neg = right, 0 = collinear)
*/
{
  const POINT_ITER lastp = endp - 1;  // iterator to last point

  if (firstp == endp)
  { endc = endp; return; };

/* sort table in increasing order */
  sort(firstp, endp, compare);

  if (!compare(*firstp, *(endp-1)))
/* all points have same x/y coordinates */
  { endc = firstp+1; return; };  

/* find extreme points in lower convex hull */
  POINT_ITER lastc = firstp+1;

  for (POINT_ITER curp = firstp + 2; curp != endp; curp++) {
    while (lastc != firstp && orient(*(lastc-1), *lastc, *curp) <= 0)
      lastc--;

/* add *curp to list of vertices */
    lastc++;
    if (lastc < curp)
      iter_swap(lastc, curp);
  };

  if (lastc != lastp) {
    POINT_ITER imax = lastc;
    lastc++;

/* sort remainder of the table in decreasing order */
    sort(lastc, endp, swap_arg<POINT>(compare));

/* find extreme points in upper convex hull */
    for (POINT_ITER curp = imax + 2; curp != endp; curp++) {
      while (lastc != imax && orient(*(lastc-1), *lastc, *curp) <= 0)
	lastc--;

/* add *curp to list of vertices */
      lastc++;
      if (lastc < curp)
	iter_swap(lastc, curp);
    }

/* eliminate any trailing non-extreme points */
    while (lastc != imax && orient(*(lastc-1), *lastc, *firstp) <= 0)
      lastc--;
  };

  endc = lastc+1;

};

#endif CHULL_2PASS_H