There are a number of implementations of this available on the web, but most seem to be in C/C++:
http://vterrain.org/Implementation/Libs/triangulate.html

However if you start from that code and a nice fast algorithm, it should be pretty simple to port over to Java.  E.g. http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml is a pretty small set of code in C++ which is close to Java - should take about an hour to port over.

That'll be much easier than coming up with your own algorithm.

Doug

Hi, thanks Doug!

I have done a port of the Flipcode: Efficient polygon triangulation, it is not exactly the same as I get it to return an index array (OpenGL requires) instead of an array of 3 vertices per triangle found.

Theoretically everything works fine and I get it to return a float array of indexed vertices for each polygon. However iterating through 17000 records this takes about 15 seconds, probably too long for your average user to wait for their map to be displayed. Below is the code for anyone interested not saying it is a particulary efficient port but a first try. Any optimization ideas are very welcome.

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 allOpen in new window

When I query my objects from the database I place them into a JTS Geometry object I then run through it getting the vertices creating the first float array. (As below) Then creates the second index float array.

import com.vividsolutions.jts.geom.Geometry;
import com.vividsolutions.jts.geom.LineString;
import com.vividsolutions.jts.geom.Polygon;
import com.vividsolutions.jts.io.WKBReader;

Select allOpen in new window

while (stmt.step()){
	Geometry geometry = new WKBReader().read(stmt.column_bytes(2));
	
	if (geometry.getGeometryType().equals("Point")){
	}
	else if (geometry.getGeometryType().equals("LineString")){
	}
	else if (geometry.getGeometryType().equals("Polygon")){
		
		LineString mExteriorPolygon = ((Polygon)geometry).getExteriorRing();
		float[] mExtPolygonData = new float[mExteriorPolygon.getNumPoints() * 3];
		
        for (int counter=0; counter <= mExteriorPolygon.getNumPoints()-1;counter++){
        	mExtPolygonData[counter * 3] = (float) mExteriorPolygon.getPointN(counter).getCoordinate().x;
        	mExtPolygonData[(counter * 3) + 1] = (float) mExteriorPolygon.getPointN(counter).getCoordinate().y;
        	mExtPolygonData[(counter * 3) + 2] = 0.0f; //z
        }
		
        FloatBuffer mPointArrayBuffer = ByteBuffer.allocateDirect(mExtPolygonData.length * mBytesPerFloat)
		        .order(ByteOrder.nativeOrder()).asFloatBuffer();
        mPointArrayBuffer.put(mExtPolygonData).position(0);

        //*******Create the index array********
        int[] returnvalue = PolygonTriangulation.Process(mExtPolygonData);
        //*********************************
        default_settings.orgNonAssetCatMappableLayers.get(Count).objFloatBuffer.add(mPointArrayBuffer);
		default_settings.orgNonAssetCatMappableLayers.get(Count).objTypeArray.add((byte) 3);
	}
}
stmt.close();

Select allOpen in new window

What I am wondering is as far as speed goes, how can I improve this?
Is going native the answer?
JTS may have a solution but I'll need to research this, based on:http://vterrain.org/Implementation/Libs/triangulate.html Ref No: 10

Regards Hank

Thanks Doug,
Learnt a lot!
Regards Hank

Hi Doug,
hey I've just opened up a new question, about SWIG and noticed through another question that you've had some experience with this. I would appreciate your advice!
http://www.experts-exchange.com/Programming/Languages/Java/Q_27885456.html#a38455198