/***************************************************************************
 *   Developer: Francisco Martínez del Río (2011)                          *
 *   fmartin@ujaen.es                                                      *
 *   Version: 1.4.1                                                        *
 *                                                                         *
 *   This is a public domain program                                       *
 ***************************************************************************/

#include "polygon.h"
#include "utilities.h"
#include <limits>
#include <set>
#include <cstdlib>
#include <algorithm>

void Contour::boundingbox (Point& min, Point& max)
{
	min.x = min.y = numeric_limits<double>::max ();
	max.x = max.y = -numeric_limits<double>::max ();
	Contour::iterator i = begin();
	while (i != end()) {
		if (i->x < min.x)
			min.x = i->x;
		if (i->x > max.x)
			max.x = i->x;
		if (i->y < min.y)
			min.y = i->y;
		if (i->y > max.y)
			max.y = i->y;
		++i;
	}
}

bool Contour::counterclockwise ()
{
	if (_precomputedCC)
		return _CC;
	_precomputedCC = true;
	double area = 0.0;
	for (unsigned int c = 0; c < nvertices () - 1; c++)
		area += vertex (c).x * vertex (c+1).y - vertex (c+1).x *  vertex (c).y;
	area += vertex (nvertices ()-1).x * vertex (0).y - vertex (0).x *  vertex (nvertices ()-1).y;
	return _CC = area >= 0.0;
}

void Contour::move (double x, double y)
{
	for (unsigned int i = 0; i < points.size (); i++) {
		points[i].x += x;
		points[i].y += y;
	}
}


unsigned Polygon::nvertices () const
{
	unsigned int nv = 0;
	for (unsigned int i = 0; i < ncontours (); i++)
		nv += contours[i].nvertices ();
	return nv;
}

void Polygon::boundingbox (Point& min, Point& max)
{
	min.x = min.y = numeric_limits<double>::max ();
	max.x = max.y = -numeric_limits<double>::max ();
	Point mintmp;
	Point maxtmp;
	for (unsigned int i = 0; i < ncontours (); i++) {
		contours[i].boundingbox (mintmp, maxtmp);
		if (mintmp.x < min.x)
			min.x = mintmp.x;
		if (maxtmp.x > max.x)
			max.x = maxtmp.x;
		if (mintmp.y < min.y)
			min.y = mintmp.y;
		if (maxtmp.y > max.y)
			max.y = maxtmp.y;
	}
}

void Polygon::move (double x, double y)
{
	for (unsigned int i = 0; i < contours.size (); i++)
		contours[i].move (x, y);
}


/*
 * The following code is necessary for implementing the computeHoles member function
 *
 */

namespace { // start of anonymous namespace
	struct SweepEvent;
	struct SegmentComp : public binary_function<SweepEvent*, SweepEvent*, bool> {
		bool operator() (SweepEvent* e1, SweepEvent* e2) const;
	};

	struct SweepEvent {
		Point p;   // point associated with the event
		bool left; // is the point the left endpoint of the segment (p, other->p)?
		int pl;    // Polygon to which the associated segment belongs to
		SweepEvent* other; // Event associated to the other endpoint of the segment
		/**  Does the segment (p, other->p) represent an inside-outside transition in the polygon for a vertical ray from (p.x, -infinite) that crosses the segment? */
		bool inOut;
		set<SweepEvent*, SegmentComp>::iterator poss; // Only used in "left" events. Position of the event (segment) in S

		/** Class constructor */
		SweepEvent (const Point& pp, bool b, int apl) : p (pp), left (b), pl (apl) {}
		/** Return the segment associated to the SweepEvent */
		Segment segment () { return Segment (p, other->p); }
		/** Is the segment (p, other->p) below point x */
		bool below (const Point& x) const { return (left) ? signedArea (p, other->p, x) > 0 : signedArea (other->p, p, x) > 0; }
		/** Is the segment (p, other->p) above point x */
		bool above (const Point& x) const { return !below (x); }
	};

	struct SweepEventComp : public binary_function<SweepEvent*, SweepEvent*, bool> {
		bool operator() (SweepEvent* e1, SweepEvent* e2) const {
			if (e1->p.x < e2->p.x) // Different x coordinate
				return true;
			if (e2->p.x < e1->p.x) // Different x coordinate
				return false;
			if (e1->p != e2->p) // Different points, but same x coordinate. The event with lower y coordinate is processed first
				return e1->p.y < e2->p.y;
			if (e1->left != e2->left) // Same point, but one is a left endpoint and the other a right endpoint. The right endpoint is processed first
				return !e1->left;
			// Same point, both events are left endpoints or both are right endpoints. The event associate to the bottom segment is processed first
			return e1->below (e2->other->p);
		}
};

} // end of anonymous namespace

bool SegmentComp::operator() (SweepEvent* e1, SweepEvent* e2) const {
	if (e1 == e2)
		return false;
	if (signedArea (e1->p, e1->other->p, e2->p) != 0 || signedArea (e1->p, e1->other->p, e2->other->p) != 0) {
		// Segments are not collinear
		// If they share their left endpoint use the right endpoint to sort
		if (e1->p == e2->p)
			return e1->below (e2->other->p);
		// Different points
		SweepEventComp comp;
		if (comp (e1, e2))  // has the segment associated to e1 been sorted in evp before the segment associated to e2?
			return e1->below (e2->p);
		// The segment associated to e2 has been sorted in evp before the segment associated to e1
		return e2->above (e1->p);
	}
	// Segments are collinear. Just a consistent criterion is used
	if (e1->p == e2->p)
		return e1 < e2;
	SweepEventComp comp;
	return comp (e1, e2);
}

//#define _DEBUG_
void Polygon::computeHoles ()
{
	if (ncontours () < 2) {
		if (ncontours () == 1 && contour (0).clockwise ())
			contour (0).changeOrientation ();
		return;
	}
	vector<SweepEvent> ev;
	vector<SweepEvent*> evp;
	ev.reserve (nvertices ()*2);
	evp.reserve (nvertices ()*2);
	for (unsigned i = 0; i < ncontours (); i++) {
//		cout << contour (i);
		contour (i).setCounterClockwise ();
//		cout << contour (i);
		for (unsigned j = 0; j < contour (i).nedges (); j++) {
			Segment s = contour(i).segment (j);
			if (s.begin ().x == s.end ().x) // vertical segments are not processed
				continue;
			ev.push_back (SweepEvent (s.begin (), true, i));
			ev.push_back (SweepEvent (s.end (), true, i));
			SweepEvent* se1 = &ev[ev.size ()-2];
			SweepEvent* se2 = &ev[ev.size ()-1];
			se1->other = se2;
			se2->other = se1;
			if (se1->p.x < se2->p.x) {
				se2->left = false;
				se1->inOut = false;
			} else {
				se1->left = false;
				se2->inOut = true;
			}
			evp.push_back (se1);
			evp.push_back (se2);
		}
	}
	sort (evp.begin (), evp.end (), SweepEventComp ());

	set<SweepEvent*, SegmentComp> S; // Status line
	vector<bool> processed (ncontours (), false);
	vector<int> holeOf (ncontours (), -1);
	int nprocessed = 0;
	for (unsigned i = 0; i < evp.size () && nprocessed < ncontours (); i++)  {
		SweepEvent* e = evp[i];
		#ifdef _DEBUG_
		cout << "Process event: " << *e << endl;
		#endif

		if (e->left) { // the segment must be inserted into S
			e->poss = S.insert(e).first;
			if (!processed[e->pl]) {
				processed[e->pl] = true;
				nprocessed++;
				set<SweepEvent*, SegmentComp>::iterator prev = e->poss;
				if (prev == S.begin()) {
					contour (e->pl).setCounterClockwise ();
				} else {
					prev--;
					if (!(*prev)->inOut) {
						holeOf[e->pl] = (*prev)->pl;
						contour (e->pl).setExternal (false);
						contour ((*prev)->pl).addHole (e->pl);
						if (contour((*prev)->pl).counterclockwise ())
							contour (e->pl).setClockwise ();
						else
							contour (e->pl).setCounterClockwise ();
					} else if (holeOf[(*prev)->pl] != -1) {
						holeOf[e->pl] = holeOf[(*prev)->pl];
						contour (e->pl).setExternal (false);
						contour (holeOf[e->pl]).addHole (e->pl);
						if (contour(holeOf[e->pl]).counterclockwise ())
							contour (e->pl).setClockwise ();
						else
							contour (e->pl).setCounterClockwise ();
					} else {
						contour (e->pl).setCounterClockwise ();
					}
				}
			}
		} else { // the segment must be removed from S
			S.erase (e->other->poss);
		}
		#ifdef _DEBUG_
		cout << "Tras ajuste: " << endl;
		for (set<SweepEvent*, SegmentComp>::const_iterator it2 = S.begin(); it2 != S.end(); it2++)
			cout << **it2 << endl;
		cout << endl;
		string st;
		getline (cin, st);
		#endif
	}
}