/*

    ......... 2015 Ivan Mahonin

    This program is free software: you can redistribute it and/or modify

    it under the terms of the GNU General Public License as published by

    the Free Software Foundation, either version 3 of the License, or

    (at your option) any later version.

    This program is distributed in the hope that it will be useful,

    but WITHOUT ANY WARRANTY; without even the implied warranty of

    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License

    along with this program.  If not, see <http: licenses="" www.gnu.org="">.</http:>

*/

#include <iostream></iostream>

#include "triangulator.h"

using namespace std;

bool Triangulator::intersect_lines(Vector a0, Vector a1, Vector b0, Vector b1) {

	static const Real precision = 1e-6;

	Vector da(a1 - a0);

	Vector pa(-da.y, da.x);

	Real d0, d1;

	d0 = pa.dot(b0 - a0);

	if (fabs(d0) < precision) return false;

	d1 = pa.dot(b1 - a0);

	if (fabs(d1) < precision) return false;

	if ((d0 > 0.0) == (d1 > 0.0)) return false;

	Vector db(b1 - b0);

	Vector pb(-db.y, db.x);

	d0 = pa.dot(a0 - b0);

	if (fabs(d0) < precision) return false;

	d1 = pa.dot(a1 - b0);

	if (fabs(d1) < precision) return false;

	if ((d0 > 0.0) == (d1 > 0.0)) return false;

	return true;

}

void Triangulator::build_path(const Contour &contour, Path &path, int index_offset) {

	// TODO: connect multiple contours

	path.clear();

	path.resize(contour.get_chunks().size());

	for(int i = 0; i < (int)contour.get_chunks().size(); ++i) {

		const Contour::Chunk &c = contour.get_chunks()[i];

		Vertex &v = path[i];

		v.index = i + index_offset;

		v.p = c.p1;

		v.next = &v + 1;

	}

	path.back().next = &path.front();

}

bool Triangulator::check_triangle(Vertex *first, TriangleList &triangles) {

	// path is a dot

	if (first->next == first)

		return true;

	// path is a two lines

	if (first->next->next == first)

		return true;

	// path is triangle

	if (first->next->next->next == first) {

		triangles.push_back(first->index);

		triangles.push_back(first->next->index);

		triangles.push_back(first->next->next->index);

		return true;

	}

	return false;

}

void Triangulator::split_path(Vertex *first, TriangleList &triangles) {

	if (check_triangle(first, triangles))

		return;

	// split path

	Vertex *va0 = first;

	for(Vertex *va1 = va0->next; va1 != first; va1 = va1->next) {

		if (va0 != va1 && va0->next != va1 && va1->next != va0) {

			bool intersects = false;

			for(Vertex *vb0 = first->next; vb0->next != first; vb0 = vb0->next) {

				Vertex *vb1 = vb0->next;

				if ( va0 != vb0 && va0 != vb1 && va1 != vb0 && va1 != vb1

				  && intersect_lines(va0->p, va1->p, vb0->p, vb1->p) )

					{ intersects = true; break; }

			}

			if (!intersects) {

				Vertex *next = va1->next;

				va1->next = va0;

				if (!check_triangle(va0, triangles))

					split_path(va0, triangles);

				va1->next = next;

				va0->next = va1;

				if (check_triangle(va0, triangles))

					return;

				va1 = va0;

			}

		}

	}

	cout << "bug - path not fully triangulated" << endl;

}

void Triangulator::triangulate(const Contour &contour, TriangleList &triangles, int index_offset) {

	Path path;

	build_path(contour, path, index_offset);

	triangles.reserve(triangles.size() + 3*(path.size() - 2));

	split_path(&path.front(), triangles);

}