an approach to triangulating polygons with holes
I know this has been done before, probably much more efficiently, but I had an idea wednesday and had to pursue it to its conclusion 
The other day Katopz pointed me to this snippet which triangulates polygons. I’ve also seen an approach to ear cutting by nicoptere.
I figured that by converting an “O” into a “C” leaves me with two polygons which are easy to triangulate. Allow me to elaborate:
So the idea is just to cut out a rectangle (two triangles), which connects the polygon and the hole. Triangulate the “cut shape” and then concat the extra two triangles to it. But which rectangle to choose?
I wrote a class called PolygonWithHoles.as . This contains a polygon (Vector.<Point>), and holes (Vector.<Vector.<Point>>). The idea is too loop through the “holes” one at a time (cue beavis and butthead). The safest bet is to find the shortest “connection” between a point on the main polygon and the hole (done by looping and using Point.dist()).
This too has one stipulation. In order to have a rectangle, the code has to find the “shortest connection” either before or after our initially picked “shortest connection”.
Once the “cut out rectangle” has been discovered, the perimeter of the main polygon and the hole are merged through a few loops. If there are more holes, the now modified main shape is chopped again and again, eventually resulting in a “hole free” polygon. This can then be triangulated, and the “removed rectangles” are appended as sets of triangles.
This approach seems to work well over 90% of the time. A few characters in some fonts do throw an error… not sure why. The triangulation is pretty fast, you can see this in the tracebox in the demo. The vectorization of the text is the slow bit.
The next step, of course, is to extrude the characters using textures Maybe even add shading some day…
The code is more or less legible this time, eventually I hope to clean this up into some sort of an API… Once again, the download is a zip of my always expanding “FindBitmapPixelOutline” project… download it’s latest incarnation here. The project you want to look at is “TriangulationTest.mxml”. Warning, it’s 6 megs with tons of crap you probably don’t want 
.
July 30th, 2009 at 3:20 pm
did you tried this with sepiroth true type parser rather than with marching squares trick?
July 30th, 2009 at 3:33 pm
hi makc,
No, I haven’t tried it. I don’t see why it wouldn’t work though. I guess it would take a couple of steps. First, you’d need to convert any curves into multiple line segments. Then create a vector of points from the shapes, in such a way that you pass the “container” and the “hole” correctly into the function.
These guys seem have those steps covered, only they use an alchemy port for the triangulating:
http://blog.barcinski-jeanjean.com/2009/01/07/text-extrusion-and-triangulation-experiments/
September 11th, 2009 at 3:59 pm
I discovered a weaknesses in your ‘choping of holes’ approach. It is not checked that other points of the hole are ‘in’ the chopping area. For example: take a square polygon (only 4 points on the corner) and a circular hole in it with lots of points, near one of the corners of the square. The choping ‘area’ is quite big as it will span one side of of the square and will include multiple points of the circle. In this is case, looking for the shorest connection is not enough. A possible candicate connection must be checked on intersection with other points.
A second problem: say I have two holes, hole 1 and hole 2. Hole 2 is in the path of the shortest connection between hole 1 and the polygon…
September 11th, 2009 at 4:04 pm
Thanks for that Jelle. I only tried this out on “letter shapes”, so I guess that doesn’t qualify as extensive testing
Good to know…