Мы делаем новые мобильные игры

											
	public class PolygonTriangulator
	{
	private readonly TriangulationVertexInfo[] vertices;
	private readonly int[] remainingVertices;
	private readonly int[] indices;
	private int count;
	private struct TriangulationVertexInfo
	{
			public Vector2 position;
			public int prev;
			public int next;
			public float earArea;
	}
	private void UpdateVertexEarArea(int index)
	{
			ref var elem = ref vertices[index];
			elem.earArea = MathUtils.CCW(elem.position, vertices[elem.prev].position, vertices[elem.next].position);
	}

	private PolygonTriangulator(IReadOnlyList<Vector2> rawVertices)
	{
			vertices = new TriangulationVertexInfo[rawVertices.Count];
			for (var i = 0; i < vertices.Length; i++)
					vertices[i] = new TriangulationVertexInfo {position = rawVertices[i], prev = i - 1, next = i + 1};
			count = vertices.Length;

			if (vertices[0].position == vertices[count - 1].position)
					count--;
			remainingVertices = new int[count];
			indices = new int[(count - 2) * 3];

			vertices[0].prev = count - 1;
			vertices[count - 1].next = 0;
			for (var i = 0; i < count; i++)
			{
					UpdateVertexEarArea(i);
					remainingVertices[i] = i;
			}
	}
	public void RemoveVertexIndex(int index)
	{
			count--;
			var actualIndex = remainingVertices[index];
			remainingVertices[index] = remainingVertices[count];
			if (count > index)
					Array.Copy(remainingVertices, index+1, remainingVertices, index, count-index);
			ref var elem = ref vertices[actualIndex];
			var first = (count - 2) * 3;
			indices[first++] = actualIndex;
			indices[first++] = elem.next;
			indices[first] = elem.prev;
			vertices[elem.prev].next = elem.next;
			vertices[elem.next].prev = elem.prev;
			UpdateVertexEarArea(elem.prev);
			UpdateVertexEarArea(elem.next);
	}
	public bool IsValidEar(int index)
	{
			var actualIndex = remainingVertices[index];
			ref var vertex = ref vertices[actualIndex];
			if (vertex.earArea > 0)
					return false;
			var prev = vertices[vertex.prev].position;
			var next = vertices[vertex.next].position;
			for (var i = 0; i < count; i++)
			{
					ref var comparing = ref vertices[remainingVertices[i]];
					if (comparing.earArea <= 0 || i == actualIndex || i == vertex.prev || i == vertex.next)
							continue;
					if (MathUtils.CCW(prev, vertex.position, comparing.position) > 0 && MathUtils.CCW(vertex.position, next, comparing.position) > 0 &&
							MathUtils.CCW(next, prev, comparing.position) > 0)
							return false;
			}
			return true;
	}
	public int[] Triangulate()
	{
			var found = true;
			while (count >= 3 && found)
			{
					found = false;
					for (var i = count - 1; i >= 0; i--)
					{
							if (IsValidEar(i))
							{
									RemoveVertexIndex(i);
									if (count < 3)
											break;
									i--;
									found = true;
							}
					}
			}
			// Запасная триангуляция для некорректных многоугольников
			while (count >= 3)
					RemoveVertexIndex(count-1);
			return indices;
	}
	public static int[] TriangulatePolygon(IReadOnlyList<Vector2> vertices)
	{
			Profiler.BeginSample("Polygon triangulation");
			var result = new PolygonTriangulator(vertices).Triangulate();
			Profiler.EndSample();
			return result;
	}
	}