// chull_check.H
// check if points are extreme vertices of the convex hull (C++ template)
// Version : 1.0
// Last modified: 1999/08/23 18:48:49
// Authors : Hong Cao, 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_CHECK_H
#define CHULL_CHECK_H

#include <algo.h>

template <class POINT_ITER, class POINT, class ORESULT>
bool chull_check_ext(POINT_ITER firstv, POINT_ITER endv,  
		    bool (*compare) (POINT &, POINT &),
		    ORESULT (*orient) (POINT &, POINT &,POINT &),
		    int & failnum, POINT_ITER & failv)
// return 1 iff [firstv, endv) are extremal vertices of the convex hull
// of [firstv,endv) list in counter-clockwise order (else return 0)
//
// POINT_ITER = random access iterator (pointer to objects in an array)
// POINT = type of object pointed to by POINT_ITER
// ORESULT = type returned by function orient
// firstv = iterator (pointer) referring to first element
// endv = iterator (pointer) which is past-the-end of points
// orient = calculate orientation
// compare = point comparison function
// failnum = index number to error message.  0 = no error.
// failv = iterator (pointer) to vertex where check fails 

/*
  failnum =
     0 : no failures detected
    10 : two points with same x & y coordinates
    20 : orient(*failv, *(failv+1), *(failv+2)) <= 0 
    30 : orient(*lastv, *firstv, *(firstv+1)) <= 0
    40 : orient(*(lastv-1), *lastv, *firstv ) <= 0
    50 : orient(*firstv, *failv, *(failv+1)) <= 0
*/
{
  const POINT_ITER lastv = endv -1; // last convex hull vertex
  
  failnum = 0; // initialize fail message number to 0 (no failure)
  failv = 0;

  if (endv - firstv < 2)           // nothing to check
    return(1);

  if (endv - firstv == 2)          // check if points are identical
    if (!compare(*firstv, *lastv) && !compare(*lastv, *firstv)) {
      failnum = 10;
      failv = firstv;              // *firstv == *lastv
      return(0);
    }
    else
      return(1);

  // check orient(p[i], p[i+1], p[i+2])>0, i.e. in counter-clockwise 
  for ( POINT_ITER curv = firstv ; curv != endv-2; curv++)
    if (orient(*curv, *(curv+1), *(curv+2)) <= 0) {
      failnum = 20;    
      failv = curv;     // orient(*failv, *(failv+1), *(failv+2)) <= 0 
      return(0);
    }
  
  // check the first point
  if( orient(*(endv-1), *firstv, *(firstv+1)) <= 0) {
    failnum = 30;     
    failv = firstv;    // orient(*lastv, *firstv, *(firstv+1)) <= 0
    return(0);
  }

  // check the last point
  if( orient(*(endv -2), *(endv -1), *firstv) <= 0) {
    failnum = 40;    
    failv = lastv;     // orient(*(lastv-1), *lastv, *firstv) <= 0
    return(0);
  }

  // check orient(p[1], p[i], p[i+1])>0
  for ( POINT_ITER curv = firstv + 1; curv != endv-1; curv++)
    if( orient( *firstv, *curv, *(curv+1)) <= 0) {
      failnum = 50;    
      failv = curv;    // orient(*firstv, *failv, *(failv+1)) <= 0
      return(0);
    }

  return(1);
};


template <class ARG, class ORESULT>
class compare_orient{
  // return 1 iff orient(p0, p1, p2) > 0 (left turn) (else return 0)

protected:
  ORESULT(*F)(ARG &, ARG &, ARG &);
  ARG P0;

public:
  compare_orient(ARG &P, ORESULT (*func) (ARG &, ARG &, ARG &)):
    F(func), P0(P) {};

  int operator()(ARG &P1, ARG &P2) const{
    ORESULT tmp_result = F(P0, P1, P2);
    if (tmp_result > 0)
      return(1);
    else
      return(0);
  }
};


template <class POINT_ITER, class POINT, class ORESULT>
bool chull_check_cont(POINT_ITER firstv, POINT_ITER endv, 
		      POINT_ITER firstp, POINT_ITER endp, 
		      bool (*compare) (POINT &, POINT &),
		      ORESULT (*orient) (POINT &, POINT &,POINT &),
		      int & failnum, POINT_ITER & failv, POINT_ITER & failp)
// return 1 iff [firstp, endp) are contained in the interior or
// on the boundary of the convex hull of [firstv, endv) (else return 0)
//
// Requires (pre-condition):
//
// 1. points in [firstv, endv) are distinct extremal vertices 
// of the convex hull of [firstv,endv) in counter-clockwise order
//
// firstv = iterator (pointer) referring to first vertex of convex hull
// endv = iterator (pointer) which is past-the-end of convex hull vertices
// firstp =  iterator (pointer) referring to  first interior point
// endp = iterator (pointer) which is past-the-end of interior points
// orient = calculate orientation
// compare = point comparison function
// failnum = index number to error message.  0 = no error.
// failv = iterator (pointer) to vertex in [firstv,endv) where check fails 
// failp = iterator (pointer) to point in [firstp, endp) where check fails 

/*
  failnum = 
     0 : no failures detected
   110 : orient(*firstv, *(firstv+1), *failp) < 0  (failv = firstv)
   120 : orient(*lastv, *firstv, *failp) < 0   (failv = lastv)
   130 : orient(*failv, *(failv+1), *failp) < 0 for some vertex v
   140 : endv - firstv == 0 and endp - firstp > 0
   150 : endv - firstv == 1 && (failp.x != firstv.x || failp.y != firstv.y)
           (failv = firstp)
   160 : endv - firstv == 2 && (failp is not on line segment (*firstv, *lastv))
           (failv = firstp)
*/

{
  const POINT_ITER lastv = endv - 1;  // last vertex of convex hull

  failnum = 0; // initialize fail message number to 0 (no failure)
  failp = 0;

  if (endp - firstp < 1)
    return(1);         // no interior points; nothing to check

  if (endv - firstv > 2) {
// at least 3 extreme vertices in [firstv,endv)

// check interior points
    for ( POINT_ITER curp = firstp; curp != endp; curp++) {
      if( orient (*firstv, *(firstv+1), *curp) < 0) {
	failnum = 110;
	failv = firstv;  // orient(*firstv, *(firstv+1), *failp) < 0
	failp = curp;    // *failp is to the right of first edge 
	return 0;
      };

// find the first vertex for which orient(firstv, vertex, curp) <= 0
      POINT_ITER tempv = 
	lower_bound((firstv+2), endv, *curp,
		    compare_orient<POINT, ORESULT>(*firstv, (orient)));

      if(tempv == endv) {
	failnum = 120;
	failv = lastv;    // orient(*firstv, *lastv, *failp) < 0
	failp = curp;     // *failp is to the right of last edge
	return 0;
      };

      if( orient(*(tempv-1), *(tempv), *curp) < 0) {
	failnum = 130;
	failv = tempv-1;  // orient(*failv, *(failv+1), *failp) < 0
	failp = curp;     // *failp is to the right of edge (*failv,*(failv+1))
	return 0;
      };
    };
  }
  else if (endv - firstv < 1) {
    failnum = 140;     // no convex hull vertices listed
    failv = endv;
    failp = firstp;
    return(0);
  }
  else if (endv - firstv == 1) {
    for (POINT_ITER curp = firstp; curp != endp; curp++)
      if (compare(*curp, *firstv) || compare(*firstv, *curp)) {
	failnum = 150;    
	failv = firstv;
	failp = curp;  // *failp not in equal to *firstv
	return(0);
      };
  }
  else {               // (endv - firstv == 2)
    POINT_ITER leftv, rightv;
      
    if(compare(*firstv, *lastv)) {
      leftv = firstv;
      rightv = lastv;
    }
    else {
      leftv = lastv;
      rightv = firstv;
    };

    for (POINT_ITER curp = firstp; curp != endp; curp++)
      if (compare(*curp, *leftv) || compare( *rightv, *curp)
	  || (orient( *leftv, *curp, *rightv) != 0)) {
	failnum = 160;    
	failv = firstv;
	failp = curp;  // *failp not in between *firstv and *lastv
	return(0);
      };
  };
    
  return(1);            // passed all checks
};



template < class POINT_ITER, class POINT, class ORESULT>
bool chull_check(POINT_ITER firstv, POINT_ITER endv, 
		 POINT_ITER firstp, POINT_ITER endp,
		 bool (*compare) (POINT &, POINT &),
		 ORESULT (*orient) (POINT &, POINT &,POINT &),
		 int & failnum, POINT_ITER & failv, POINT_ITER & failp)
// return 1 if [firstv, endv) are extremal vertices of the convex hull
// of ([firstv,endv) union [firstp,endp)) listed in counter-clockwise order
//
// firstv = iterator (pointer) to first element in vertex array
// endv = iterator (pointer) to past-the-end of last element in vertex array
// firstp = iterator (pointer) to first element in point array
// endp = iterator (pointer) to past-the-end of last element in point array
// orient = calculate orientation
// compare = point comparison function
// failnum = index number to error message.  0 = no error.
// failv = iterator (pointer) to vertex in [firstp, endc) where check fails
// failp = iterator (pointer) to point in [endc, lastp) where check fails
{
  failnum = 0; // initialize fail message number to 0 (no failure)
  failv = failp = 0;

  if (chull_check_ext(firstv, endv, *compare, *orient, failnum, failv) == 0)
    return (0);
  
  if (chull_check_cont(firstv, endv, firstp, endp,
		       *compare, *orient, failnum, failv, failp) == 0)
    return(0);

  return(1);
};

#endif CHULL_CHECK_H