The first difficulty I ran across in OMA was importing polygons into the game. The polygons in Box2D.XNA must be convex and are limited to 8 vertexes (for performance reasons), which means that when using complex polygons you have to divide them into simpler polygons. One of the authors of Box2D.XNA suggested ear clipping, an algorithm to divide polygons into triangles. The algorithm described in that paper is more optimized than the implementation I went with, because since I only partition the polygons during game initialization, performance isn't that important.

As mentioned in the paper, "an ear of a polygon is a triangle formed by three consecutive vertices Vi0, Vi1, and Vi2 for which no other
vertices of the polygon are inside the triangle." The basic algorithm consists of taking the initial polygon vertex list and removing ears one by one until only one triangle remains. The paper suggests using a double-linked list to store the polygon vertexes because it's a data structure that allows quick access to both current, previous and next elements when iterating the list, as well as fast removal and insertion.

Additionally, a circular list would be even more useful so that no boundary checks would be necessary. In the .Net C# framework, the double-linked list implementation doesn't allow for circular lists, meaning that the last element on the list will always be null, instead of the first element. You also can't change this pointer on the list, because a node can only be inserted in the list once. So I did my own generic circular list implementation, which is basically the same as all circular list implementations: :)

        public class CircularListNode    {        public CircularListNode previous, next;        public T value;    }    public class CircularList    {        public CircularListNode first, last;        public void Add(T value)        {            CircularListNode node;            node = new CircularListNode();            node.value = value;            if(first == null)            {                first = node;                last = node;            }            else            {                last.next = node;                node.previous = last;                last = node;                first.previous = last;                last.next = first;            }        }        public void Remove(CircularListNode node)        {            if(first == null)            {                return;            }            node.previous.next = node.next;            node.next.previous = node.previous;            if(node == first)            {                first = node.next;            }            if(node == last)            {                last = node.next;            }        }    }

(Note that this implementation in particular isn't meant to be used outside of this context: the node removal doesn't check if the list is empty because in our particular case it should never be.)

Next, the ear clipping algorithm:

    public class GeometryFactory    {        public static List> EarClip(CircularList vertices)        {            List> ears;            CircularListNode node1, node2;            bool isEar;            ears = new List>();            node1 = vertices.first;            while(node1.previous.previous != node1.next)            {                isEar = (InternalAngle(ref node1.previous.value, ref node1.value, ref node1.next.value) <= Math.PI);                if(isEar)                {                    node2 = node1.next.next;                    while(node2 != node1.previous)                    {                        if(PointInsideTriangle(ref node2.value,                                               ref node1.previous.value, ref node1.value, ref node1.next.value))                        {                            isEar = false;                            break;                        }                        node2 = node2.next;                    }                    if(isEar)                    {                        ears.Add(new List { node1.previous.value, node1.value, node1.next.value });                         node2 = node1.next;                        vertices.Remove(node1);                        node1 = node2;                    }                }                if(!isEar)                {                    node1 = node1.next;                }            }            ears.Add(new List { node1.previous.value, node1.value, node1.next.value });            return ears;        }

The EarClip function receives the vertex circular list (The vertexes must be ordered in anti-clockwise order). It then iterates it, looking for ears. The first check is done by the InternalAngle function, which verifies if the angle formed by the current vertex and its siblings is convex or concave. If it's concave, it can't be an ear and there's no need to do the next step: verifying if any of the other vertexes is inside the triangle formed by the current vertex (the "ear tip") and its siblings (which is done using the PointInsideTriangle function). Each time a ear is found the triangle it forms is added to the output ear list. The "ear tip" vertex is removed and the iteration continues. The iteration stops when there are only 3 elements on the list, which are the final triangle.

The InternalAngle function:

        private static float InternalAngle(ref Vector2 v1, ref Vector2 v2, ref Vector2 v3)        {            Vector2 a, b;            float angle;            a = v2 - v1;            b = v3 - v2;            angle = (float)Math.Atan2(b.Y, b.X) - (float)Math.Atan2(a.Y, a.X);            if(angle < 0)            {                angle += (float)Math.PI * 2;            }            return angle;        }

The PointInsideTriangle function (if you're interested in how it's derived go here):

        private static bool PointInsideTriangle(ref Vector2 p, ref Vector2 a, ref Vector2 b, ref Vector2 c)        {            Vector2 v0, v1, v2;            float dot00, dot01, dot02, dot11, dot12,                  invDenom, u, v;            // Compute vectors                    v0 = c - a;            v1 = b - a;            v2 = p - a;            // Compute dot products            Vector2.Dot(ref v0, ref v0, out dot00);            Vector2.Dot(ref v0, ref v1, out dot01);            Vector2.Dot(ref v0, ref v2, out dot02);            Vector2.Dot(ref v1, ref v1, out dot11);            Vector2.Dot(ref v1, ref v2, out dot12);            // Compute barycentric coordinates            invDenom = 1 / (dot00 * dot11 - dot01 * dot01);            u = (dot11 * dot02 - dot01 * dot12) * invDenom;            v = (dot00 * dot12 - dot01 * dot02) * invDenom;            // Check if point is in triangle            return (u > 0) && (v > 0) && (u + v < 1);        }

The List> returned by the EarClip function can be used to add each triangle to a Box2D.Xna shape:

	Body body;	BodyDef bd;	PolygonShape shape;	Fixture f;	CircularList vertices;	List> triangles;	vertices = new CircularList();        // Build the polygon vertex list here	bd = new BodyDef();        // Set additional body properties here	triangles = GeometryFactory.EarClip(vertices);	foreach(List triangle in triangles)	{		shape = new PolygonShape();		shape.Set(triangle.ToArray(), triangle.Count);		f = body.CreateFixture(shape, 1.0f);                // Set additional fixture properties here	}

And that's it.