// define this if you're using VisualC++ so that your program doesn't crash
// due to dynamic_cast errors
//
//#define IM_USING_STUPID_WINDOWS

#include <CGAL/Cartesian.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/Segment_2_Segment_2_intersection.h>
#include <CGAL/Segment_2_Point_2_intersection.h>

#include <list>

using namespace std;

typedef CGAL::Cartesian<float> R;
typedef CGAL::Polygon_traits_2<R> Traits;
typedef CGAL::Point_2<R> PointC2;
typedef CGAL::Segment_2<R> Segment;
typedef CGAL::Bbox_2 Bbox;
typedef CGAL::Polygon_2<Traits, std::list<PointC2> > Polygon;
typedef CGAL::Polygon_2<Traits, std::list<PointC2> >::Vertex_iterator VertexIterator;
typedef CGAL::Polygon_2<Traits, std::list<PointC2> >::Edge_const_iterator EdgeIterator;
typedef CGAL::Object Object ;

// possible results for the bounding box/polygon intersection routine
enum bbpResult {overlap, inside, outside};
bbpResult bbox_poly_int(Bbox& b, Polygon& p);

int main()
{
  // create a polygon and put some points in it
  Polygon p;
  p.push_back(PointC2(0,0));
  p.push_back(PointC2(4,0));
  p.push_back(PointC2(4,4));
  p.push_back(PointC2(2,2));
  p.push_back(PointC2(0,4));

  CGAL::set_pretty_mode(std::cout);
  std::cout << "created the polygon p:" << std::endl;
  std::cout << p << std::endl;
  std::cout << std::endl;

  // create some bounding boxes that will represent cells that we'll
  // check for intersection
  //
  // the arguments to the constructor are (xmin, ymin, xmax, ymax)
  // (these arguments are actually doubles)
  Bbox c[9];
  c[0] = Bbox(1,0,2,1);
  c[1] = Bbox(4,1,5,2);
  c[2] = Bbox(5,2,6,4);
  c[3] = Bbox(4,4,5,5);
  c[4] = Bbox(2.1, 2.9, 3.1, 3.9);
  c[5] = Bbox(-0.5, 3.5, 0.5, 4.5);
  c[6] = Bbox(-0.5, 2.5, 2, 3.5);
  c[7] = Bbox(-1,0,5,5);
  c[8] = Bbox(-1,-1,5,0);

  for (int k=0; k<9; k++) {
    cout << "\nChecking cell " << k << std::endl;
    switch (bbox_poly_int(c[k], p)) {
      case inside:
	cout << "Cell " << k << " is inside the polygon\n";
	break;
      case overlap:
	cout << "Cell " << k << " overlaps the polygon\n";
	break;
      case outside:
	cout << "Cell " << k << " lies completely outside the polygon\n";
	break;
    }
  }
  return 0;
}

bbpResult bbox_poly_int(Bbox& b, Polygon& p)
{
  // if the bounding boxes don't overlap, then the bbox must be
  // outside the polygon
  if (!CGAL::do_overlap(b, p.bbox()))
    return outside;
  
  // Otherwise if any/all corners of the bounding box lie inside the
  // polygon, then there is an intersection...
  int inPts = 0;
  int outPts = 0;
  PointC2 b1(b.xmin(),b.ymin());
  PointC2 b2(b.xmax(),b.ymin());
  PointC2 b3(b.xmax(),b.ymax());
  PointC2 b4(b.xmin(),b.ymax());
  CGAL::Bounded_side bs;
  bs = p.bounded_side(b1);
  if  (bs == CGAL::ON_BOUNDED_SIDE) 
    inPts++;
  else if (bs == CGAL::ON_UNBOUNDED_SIDE)
    outPts++;
  bs = p.bounded_side(b2);
  if  (bs == CGAL::ON_BOUNDED_SIDE) 
    inPts++;
  else if (bs == CGAL::ON_UNBOUNDED_SIDE)
    outPts++;
  bs = p.bounded_side(b3);
  if  (bs == CGAL::ON_BOUNDED_SIDE) 
    inPts++;
  else if (bs == CGAL::ON_UNBOUNDED_SIDE)
    outPts++;
  bs = p.bounded_side(b4);
  if  (bs == CGAL::ON_BOUNDED_SIDE) 
    inPts++;
  else if (bs == CGAL::ON_UNBOUNDED_SIDE)
    outPts++;
  // cout << "There are " << inPts << " bbox vertices inside  the polygon.\n";
  // cout << "There are " << outPts << " bbox vertices outside the polygon.\n";

  // if no corners are outside, then the bounding box is completely
  // inside the polygon.  note that under this case, the corners may
  // be in the interior or on the boundary.
  if (outPts == 0)
    return inside;
  // otherwise if any corner is inside, then the bounding box and the
  // polygon overlap
  if (inPts > 0)
    return overlap;

  // if any vertices of the polygon lie inside the bbox, then the bbox
  // and the polygon overlap
  Polygon bb;
  bb.push_back(b1); // create a polygon for the bbox
  bb.push_back(b2);
  bb.push_back(b3);
  bb.push_back(b4);
  for (VertexIterator vi = p.vertices_begin(); vi != p.vertices_end(); ++vi)
    if (bb.bounded_side(*vi) == CGAL::ON_BOUNDED_SIDE) return overlap;

#ifndef IM_USING_STUPID_WINDOWS
  // otherwise, we need to check if any of the line segments of the
  // bounding box overlap the polygon edges.  If so, the bounding box
  // and the polygon overlap; otherwise, there is no intersection.
  //
  // this is sort of complicated to get right because of the question
  // of how to handle the cases where the boundary of the bbox
  // intersects the boundary of the polygon.  There are a number of
  // weird cases, but with the assumption that the polygon is convex,
  // I believe the following procedure is correct:
  //
  //   - For each  edge of the polygon, intersect it with the four bbox edges
  //     - if the result is a line segment, continue on to the next
  //       polygon edge
  //     - if the result is a point (and not and endpoint of the bbox edge
  //       or the polygon edge), then the bounding box intersects the
  //       polygon, so return "overlap".
  //   - Return "outside"
  //   
  for (EdgeIterator ei = p.edges_begin(); ei != p.edges_end(); ++ei) {
    Object result;
    PointC2 pt;
    Segment s;
//      std::cout << "cheking polygon edge " << *ei << std::endl;
//      cout << "  checking bbox edge from " << b1 << " to " << b2 << endl;
    result= CGAL::intersection(*ei, Segment(b1,b2));
    if (CGAL::assign(s, result)) continue;
    if (CGAL::assign(pt, result) && !CGAL::do_intersect(*ei,b1)
	&& !CGAL::do_intersect(*ei,b2)
	&& !CGAL::do_intersect(Segment(b1,b2), (*ei).start())
	&& !CGAL::do_intersect(Segment(b1,b2), (*ei).end()))
      return overlap;
//      cout << "  checking bbox edge from " << b2 << " to " << b3 << endl;
    result = CGAL::intersection(*ei, Segment(b2,b3));
    if (CGAL::assign(s, result)) continue;
    if (CGAL::assign(pt, result) && !CGAL::do_intersect(*ei,b2)
	&& !CGAL::do_intersect(*ei,b3)
	&& !CGAL::do_intersect(Segment(b2,b3), (*ei).start())
	&& !CGAL::do_intersect(Segment(b2,b3), (*ei).end()))
      return overlap;
//      cout << "  checking bbox edge from " << b3 << " to " << b4 << endl;
    result = CGAL::intersection(*ei, Segment(b3,b4));
    if (CGAL::assign(s, result)) continue;
    if (CGAL::assign(pt, result) && !CGAL::do_intersect(*ei,b3)
	&& !CGAL::do_intersect(*ei,b4)
	&& !CGAL::do_intersect(Segment(b3,b4), (*ei).start())
	&& !CGAL::do_intersect(Segment(b3,b4), (*ei).end()))
      return overlap;
//      cout << "  checking bbox edge from " << b4 << " to " << b1 << endl;
    result = CGAL::intersection(*ei, Segment(b4,b1));
    if (CGAL::assign(s, result)) continue;
    if (CGAL::assign(pt, result) && !CGAL::do_intersect(*ei,b4)
	&& !CGAL::do_intersect(*ei,b1)
	&& !CGAL::do_intersect(Segment(b4,b1), (*ei).start())
	&& !CGAL::do_intersect(Segment(b4,b1), (*ei).end()))
      return overlap;
  }
  // no intersections, so the bounding box is completely outside the
  // polygon
  return outside;
#else
  //
  // here's the version that will compile and run OK under VisualC++
  //
  for (EdgeIterator ei = p.edges_begin(); ei != p.edges_end(); ++ei) {
    Object result;
    PointC2 pt;
    Segment s;
//      std::cout << "cheking polygon edge " << *ei << std::endl;
//      cout << "  checking bbox edge from " << b1 << " to " << b2 << endl;
    result= CGAL::intersection(*ei, Segment(b1,b2));
    if (!result.is_empty() && !CGAL::do_intersect(*ei,b1)
	&& !CGAL::do_intersect(*ei,b2)
	&& !CGAL::do_intersect(Segment(b1,b2), (*ei).start())
	&& !CGAL::do_intersect(Segment(b1,b2), (*ei).end()))
      return overlap;
//      cout << "  checking bbox edge from " << b2 << " to " << b3 << endl;
    result = CGAL::intersection(*ei, Segment(b2,b3));
    if (!result.is_empty() && !CGAL::do_intersect(*ei,b2)
	&& !CGAL::do_intersect(*ei,b3)
	&& !CGAL::do_intersect(Segment(b2,b3), (*ei).start())
	&& !CGAL::do_intersect(Segment(b2,b3), (*ei).end()))
      return overlap;
//      cout << "  checking bbox edge from " << b3 << " to " << b4 << endl;
    result = CGAL::intersection(*ei, Segment(b3,b4));
    if (!result.is_empty() && !CGAL::do_intersect(*ei,b3)
	&& !CGAL::do_intersect(*ei,b4)
	&& !CGAL::do_intersect(Segment(b3,b4), (*ei).start())
	&& !CGAL::do_intersect(Segment(b3,b4), (*ei).end()))
      return overlap;
//      cout << "  checking bbox edge from " << b4 << " to " << b1 << endl;
    result = CGAL::intersection(*ei, Segment(b4,b1));
    if (!result.is_empty() && !CGAL::do_intersect(*ei,b4)
	&& !CGAL::do_intersect(*ei,b1)
	&& !CGAL::do_intersect(Segment(b4,b1), (*ei).start())
	&& !CGAL::do_intersect(Segment(b4,b1), (*ei).end()))
      return overlap;
  }
  // no intersections, so the bounding box is completely outside the
  // polygon
  return outside;
#endif
}