using UnityEngine;
using System.Collections.Generic;

public class Triangulator
{
	private static Triangulator tri = new Triangulator ();

	public static int[] Triangulate (IList<Vector2> points)
	{
		//var helper = new Triangulator (points);
		tri.m_points = points;
		return tri.Triangulate ();
	}

	public static void Triangulate (IList<Vector2> points, List<int> result)
	{
		//var helper = new Triangulator (points);
		tri.m_points = points;
		tri.Triangulate (result);
	}

	public static Mesh CreateMesh (IList<Vector2> points)
	{
		int[] indices = Triangulator.Triangulate (points);

		// Create the Vector3 vertices
		Vector3[] vertices = new Vector3[points.Count];
		for (int i = 0; i < vertices.Length; i++) {
			vertices [i] = new Vector3 (points [i].x, points [i].y, 0);
		}
		
		// Create the mesh
		Mesh result = new Mesh ();
		result.vertices = vertices;
		result.triangles = indices;

//		result.RecalculateNormals ();
//		result.RecalculateBounds ();
		
		return result;
	}

	private static List<Vector3> CreateMeshCool_vertices = new List<Vector3> (100);
	private static List<int> CreateMeshCool_triangles = new List<int> (300);
	private static List<Vector2> CreateMeshCool_UVs = new List<Vector2> (100);

	public static Mesh CreateMeshCool (IList<Vector2> points, Mesh result)
	{
		// Create the Vector3 vertices
		var vertices = CreateMeshCool_vertices;
		vertices.Clear ();
		var uvs = CreateMeshCool_UVs;
		uvs.Clear ();
		for (int i = 0; i < points.Count; i++) {
			var p = points [i];
			vertices.Add (new Vector3 (p.x, p.y, 0));
			uvs.Add (p);
		}

		var triangles = CreateMeshCool_triangles;
		triangles.Clear ();
		Triangulator.Triangulate (points, triangles);
		
		// Create the mesh
		//Mesh result = new Mesh ();
		result.Clear ();
		result.SetVertices (vertices);
		result.SetUVs (0, uvs);
		result.SetTriangles (triangles, 0);
		
		//result.RecalculateBounds ();
		
		return result;
	}

	private IList<Vector2> m_points;

	public Triangulator ()
	{

	}

	public Triangulator (IList<Vector2> points)
	{
		m_points = points;
	}

	public int[] Triangulate ()
	{
		List<int> indices = new List<int> ();
		
		int n = m_points.Count;
		if (n < 3)
			return indices.ToArray ();

		if ((m_points [0] - m_points [m_points.Count - 1]).sqrMagnitude < 0.001) {
			n--;
		}

		int[] V = new int[n];
		if (Area () > 0) {
			for (int v = 0; v < n; v++)
				V [v] = v;
		} else {
			for (int v = 0; v < n; v++)
				V [v] = (n - 1) - v;
		}
		
		int nv = n;
		int count = 2 * nv;
		for (int m = 0, v = nv - 1; nv > 2;) {
			if ((count--) <= 0)
				return indices.ToArray ();
			
			int u = v;
			if (nv <= u)
				u = 0;
			v = u + 1;
			if (nv <= v)
				v = 0;
			int w = v + 1;
			if (nv <= w)
				w = 0;
			
			if (Snip (u, v, w, nv, V)) {
				int a, b, c, s, t;
				a = V [u];
				b = V [v];
				c = V [w];
				indices.Add (a);
				indices.Add (b);
				indices.Add (c);
				m++;
				for (s = v, t = v + 1; t < nv; s++, t++)
					V [s] = V [t];
				nv--;
				count = 2 * nv;
			}
		}
		
		indices.Reverse ();
		return indices.ToArray ();
	}

	private static List<int> Triangulate_vHelper = new List<int> (200);

	public void Triangulate (List<int> result)
	{
		List<int> indices = result;
		indices.Clear ();
		
		int n = m_points.Count;
		if (n < 3)
			return;

		if ((m_points [0] - m_points [m_points.Count - 1]).sqrMagnitude < 0.001) {
			n--;
		}

		var V = Triangulate_vHelper;
		V.Clear ();
		if (Area () > 0) {
			for (int v = 0; v < n; v++)
				V.Add (v);
		} else {
			for (int v = 0; v < n; v++)
				V.Add ((n - 1) - v);
		}
		
		int nv = n;
		int count = 2 * nv;
		for (int m = 0, v = nv - 1; nv > 2;) {
			if ((count--) <= 0)
				return;
			
			int u = v;
			if (nv <= u)
				u = 0;
			v = u + 1;
			if (nv <= v)
				v = 0;
			int w = v + 1;
			if (nv <= w)
				w = 0;
			
			if (Snip (u, v, w, nv, V)) {
				int a, b, c, s, t;
				a = V [u];
				b = V [v];
				c = V [w];
				indices.Add (a);
				indices.Add (b);
				indices.Add (c);
				m++;
				for (s = v, t = v + 1; t < nv; s++, t++)
					V [s] = V [t];
				nv--;
				count = 2 * nv;
			}
		}
		
		indices.Reverse ();
	}

	private float Area ()
	{
		int n = m_points.Count;
		if ((m_points [0] - m_points [m_points.Count - 1]).sqrMagnitude < 0.001) {
			n--;
		}
		float A = 0.0f;
		for (int p = n - 1, q = 0; q < n; p = q++) {
			Vector2 pval = m_points [p];
			Vector2 qval = m_points [q];
			A += pval.x * qval.y - qval.x * pval.y;
		}
		return (A * 0.5f);
	}

	private bool Snip (int u, int v, int w, int n, List<int> V)
	{
		int p;
		Vector2 A = m_points [V [u]];
		Vector2 B = m_points [V [v]];
		Vector2 C = m_points [V [w]];
		if (Mathf.Epsilon > (((B.x - A.x) * (C.y - A.y)) - ((B.y - A.y) * (C.x - A.x))))
			return false;
		for (p = 0; p < n; p++) {
			if ((p == u) || (p == v) || (p == w))
				continue;
			Vector2 P = m_points [V [p]];
			if (InsideTriangle (A, B, C, P))
				return false;
		}
		return true;
	}

	private bool Snip (int u, int v, int w, int n, int[] V)
	{
		int p;
		Vector2 A = m_points [V [u]];
		Vector2 B = m_points [V [v]];
		Vector2 C = m_points [V [w]];
		if (Mathf.Epsilon > (((B.x - A.x) * (C.y - A.y)) - ((B.y - A.y) * (C.x - A.x))))
			return false;
		for (p = 0; p < n; p++) {
			if ((p == u) || (p == v) || (p == w))
				continue;
			Vector2 P = m_points [V [p]];
			if (InsideTriangle (A, B, C, P))
				return false;
		}
		return true;
	}

	private bool InsideTriangle (Vector2 A, Vector2 B, Vector2 C, Vector2 P)
	{
		float ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy;
		float cCROSSap, bCROSScp, aCROSSbp;
		
		ax = C.x - B.x;
		ay = C.y - B.y;
		bx = A.x - C.x;
		by = A.y - C.y;
		cx = B.x - A.x;
		cy = B.y - A.y;
		apx = P.x - A.x;
		apy = P.y - A.y;
		bpx = P.x - B.x;
		bpy = P.y - B.y;
		cpx = P.x - C.x;
		cpy = P.y - C.y;
		
		aCROSSbp = ax * bpy - ay * bpx;
		cCROSSap = cx * apy - cy * apx;
		bCROSScp = bx * cpy - by * cpx;
		
		return ((aCROSSbp >= 0.0f) && (bCROSScp >= 0.0f) && (cCROSSap >= 0.0f));
	}
}