import java.util.ArrayList;
public class PolygonTriangulation {
	
	static final float EPSILON=0.0000000001f;
	
	static public float Area(float[] contour) {
		int n = contour.length;
		float A = 0.0f;
		
		for(int p = n - 3, q = 0; q < n; p=q, q+=3)
		{
			A += contour[p] * contour[q+1] - contour[q] * contour[p+1];
		}
		return A * 0.5f;
	}

	static public boolean InsideTriangle(float Ax,float Ay,float Bx,float By,float Cx,float Cy,float Px,float Py){
		float ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy;
		float cCROSSap, bCROSScp, aCROSSbp;
		
		ax = Cx - Bx;  ay = Cy - By;
		bx = Ax - Cx;  by = Ay - Cy;
		cx = Bx - Ax;  cy = By - Ay;
		apx= Px - Ax;  apy= Py - Ay;
		bpx= Px - Bx;  bpy= Py - By;
		cpx= Px - Cx;  cpy= Py - Cy;
		
		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));
	}

	static public boolean Snip(float[] contour, int u, int v, int w, int n, int[] V) {
		int p;
		float Ax, Ay, Bx, By, Cx, Cy, Px, Py;
		
		Ax = contour[V[u]];
		Ay = contour[V[u+1]];
		
		Bx = contour[V[v]];
		By = contour[V[v+1]];
		
		Cx = contour[V[w]];
		Cy = contour[V[w+1]];
		
		if ( EPSILON > (((Bx-Ax)*(Cy-Ay)) - ((By-Ay)*(Cx-Ax))) ){
			return false;
		}
		
		for (p = 0; p < n; p++)
		{
			if( (p == u/2) || (p == v/2) || (p == w/2) ){
				continue;
			}
			
			Px = contour[V[p*2]];
			Py = contour[V[(p*2)+1]];
			
			if (InsideTriangle(Ax,Ay,Bx,By,Cx,Cy,Px,Py)){
				return false;
			}
		}
		return true;
	}
	
	//Brings in 3D vertex float array but processes it as 2D only.
	static public int[] Process(float[] contour) {
		//Pre-return list
		ArrayList<Integer> vertexArray = new ArrayList<Integer>();
		
		/* allocate and initialize list of Vertices in polygon */
		int n = contour.length;
		if ( n/3 < 3 )
			return null;

		//The (n/3)*2 occurs as we are removing the z coordinate from the mix
		int[] V = new int[(n/3)*2];

		/* we want a counter-clockwise polygon in V */
		if (0.0f < Area(contour)){
			for (int s = 0, v = 0; v < n-1; s+=2, v += 3){
				V[s] = v;
				V[s + 1] = v + 1;
			}
		}
		else{
			for(int s = 0, v = 0; v < n-1; s += 2, v += 3){
				V[s] = (n - 1) - (v + 2);
				V[s + 1] = (n - 1) - (v + 1);
			}
		}
		
		int nv = n/3;

		/*  remove nv-2 Vertices, creating 1 triangle every time */
		int count = 2 * nv;   /* error detection */

		for(int v = nv - 1; nv > 2;)
		{
			/* if we loop, it is probably a non-simple polygon */
			if (0 >= (count--))
			{
				//** Triangulate: ERROR - probable bad polygon!
				return null;
			}
			
			/* three consecutive vertices in current polygon, <u,v,w> */
			int u = v;
			if (nv <= u)
				u = 0;		/* previous */
			v = u + 1;
			if (nv <= v)
				v = 0;		/* new v    */
			int w = v + 1;
			if (nv <= w)
				w = 0;		/* next     */

			if (Snip(contour, u*2, v*2, w*2, nv, V))
			{
				vertexArray.add(V[u*2]/3);
				vertexArray.add(V[v*2]/3);
				vertexArray.add(V[w*2]/3);
				
				// remove v from remaining polygon
				for(int s = v * 2, t = (v * 2) + 2; t < (nv * 2); s += 2, t += 2){
					V[s] = V[t];
					V[s+1] = V[t+1];
				}
				nv--;
				
				// reset error detection counter
				count = 2 * nv;
			}
		}
		//Convert ArrayList into short array
		int[] index = new int[vertexArray.size()];
		for(int i = 0; i < vertexArray.size(); i++){
			index[i] = vertexArray.get(i);
		}
		return index;
	}
}

Select all