/*

    ......... 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://www.gnu.org/licenses/>.

*/

#ifndef _TRIANGULATOR_H_

#define _TRIANGULATOR_H_

#include <vector>

#include "geometry.h"

#include "contour.h"

class Triangulator {

public:

	class Vertex {

	public:

		int index;

		Vector p;

		Vertex *next;

		Vertex(): index(), next() { }

	};

	typedef std::vector<Vertex> Path;

	typedef std::vector<int> TriangleList;

	static bool intersect_lines(Vector a0, Vector a1, Vector b0, Vector b1);

	static void build_path(const Contour &contour, Path &path, int index_offset);

	static bool check_triangle(Vertex *first, TriangleList &triangles);

	static void split_path(Vertex *first, TriangleList &triangles);

	static void triangulate(const Contour &contour, TriangleList &triangles, int index_offset);

};

#endif