# Do I need to roll my own polygon segmentation algorithm to automate Box2d body creation from a tile map?

Before re-inventing the wheel I figured I'd ask:

I'm working on a tile-based 2d-maze level generator for cocos2d + box2d. The idea is:

• I'm using one of the well-known graph traversal algorithms to generate a random maze.
• this data gets encoded as an XML of the type that both Tiled and cocos2d can work with.
• based on the generated maze tile data, my program should also generate the polygonal data (vertices) that define the walls of the maze so that I can get them from, for instance, a Tiled's XML's object layer and into Box2d for defining bodies.

However, I'm at step 3 and so far, I'm thinking of solving this step with something along the lines of a flood/segmentation/magic wand algorithm. That is, from step 2 I get the graph's nodes which translate in Tiled's XML to, for instance, a 2d array where walls are marked with a number and open spaces are 0s. This is in the cvs non-compressed XML representation for instance.

So what I need to do now is sort of solve the convex-hull problem for a bunch of points (the non-zero numbers in this 2d array), but actually creating different polygons. I also need to then break any concave ploys into convex, but that can be done easiest with ear-clipping and, should I decided to get fancier, Delaunay or something.

Let me illustrate with images:

And in the next image you can see A the set's convex-hull (approximately), and B what I'm trying to achieve (concave subsets of the hull):

That is, I need to be able to distinguish separate polys. Of course, but for one, these also turn out to be concave which Box2d will not like. But like I said, I'll turn them to convex sets afterwards.

The question is, is there anything built-in or tested/tried that I could just grab and use or do I need to implement my magic wand algorithm?

I'm also open to different approaches all together :)

-
given the unanimous silence... at this point I think the way I'll go about it is with blob extraction, which I'll either code myself or use OpenCV's – SaldaVonSchwartz May 21 '12 at 17:46