# 2D Polygon Triangulation

I am creating a game engine using the JBox2D physics engine. It only allows you to create polygon fixtures up to 8 vertices, To create a body with more than 8 vertices, you need to create multiple fixtures for the body.

My question is, How can I split the polygons a user creates into smaller polygons for JBox2D?

Also, what topology should I use when splitting the polygons and why? (If JBox2D can have up to 8 vertices, why not split polygons into 8 per polygon)

This simple algorithm assumes you're working with a convex polygon (in the case of physics engines you definitely should be):

Loop over the polygon with two indices, one called next and one called last. This is also known as a format called "Triangle Fan". Here's a demo image:

You set up these two indices and loop something like this:

TriVertexList TriangleFan( int vCount, Vec2[] v )
{
int start = 0;
int last = 1;
int prev = 0;
TriVertexList out;

while(start != last)
{
out.push( v[start], v[last], v[prev] );
prev = last;
last = last + 1 == vCount ? 0 : last + 1;
}

return out;
}


This algorithm can easily be extended to 3D (which I currently use to triangulate my 3D meshes).

• You have the indices labeled last and prev which is confusing. Better to call them cur and prev. – Nathan Reed Oct 8 '13 at 1:40
• And this will create artifacts on more complex shapes. Imagine a U or a A. If you always assume that the 0 is the first index to have as your start point your going to get alot of artifacts. – Tordin Oct 8 '13 at 9:41
• @Tordin That's why I stated the assumption is a convex polygon. – RandyGaul Oct 8 '13 at 15:53
• Oh, yeah my misstake there. i missed that part :) – Tordin Oct 9 '13 at 6:28