Tessellating an arbitrary polygon by tiling triangles

Question

I need to fill an arbitrary polygon using a near-uniform tiling of triangles. How would I do this? You may provide either references to existing algorithms or even simply ideas or hints of your own.

The following is presumed:

• The polygon may be convex (but bonus points if you come up with an algorithm that works for concave shapes)
• The polygon has an arbitrary number of edges (3 or more)
• The amount of tessellation (preferably the number of vertices added by the algorithm) should be parametrized
• The polygon's edges may be divided by the algorithm
• Triangles should be nearly uniform in size and shape (i.e. corners will tend towards 60 degrees)
• Preferably the number edges at a vertex should be few rather than many. This will likely follow from the previous point (I.e. the algorithm should produce a "clean mesh").

This is not an easy problem to solve and I expect that a "heuristic" solution may be the most efficient... (right?)

Answer 1

Hi

Here's a hint: demonstrate to SO that you have made a serious attempt to tackle YOUR problem YOURSELF in your question. As it stands your post reads rather too much like an assignment that you are setting us.

Regards

Mark

Answer 2

Doesn't actually sound that complicated, algorithmically. Or am I missing anything?

Some pseudocode:

• Place an exis-aligned enclosing square tightly around your polygon.
• Subdivide each square into four children (quad-tree like), where the number of iterations determines your "amount of tessellation".
• Each resulting square is either cleanly outside your polygon (=ignore), cleanly inside your polygon (=split into two triangles of resulting tesselation along the diagonal) or intersects your polygon.
• Exact cases for the intersection squares are left as an exercise to the reader. ;-) [At this point in time, at least.]

It will give you triangles with 45°/45°/90° angles though. If you want as close to 60° as possible, you should start with tessellating the surface of your polygon with hexagons (with the size of the hexagon being your "amount of tessellation") and then checking each of the six 60°/60°/60° triangles that make up these hexagons. For these triangles you do the same as with the squares in the above pseudocode, except for the fact that you don't need to split the ones that cleanly inside your polygon as they are already triangles themselves.

Is this of any help whatsoever? Should work for any polygon (convex/concave/with holes in them), I think, given that what exactly you do for intersecting squares/triangles handles such polygons.

Answer 3

Does Triangle do what you want?

(The explanations of the algorithms on that site are better than whatever I could come up with.)

Answer 4

As Jason Orendorff pointed out, you should try to use Triangle to generate a quality mesh. It has lots of options that you can play with to try to get an isotropic mesh. Then, you could try to use an iterative algorithm to create a well-centered triangulation. More details are listed on this publications page. I have implemented the 2007 paper "Well-Centered Planar Triangulation -- an Iterative Approach," and it gives decent results on medium sized meshes. A well-centered triangulation is one in which all the circumcenters of triangles lie inside the respective triangle. Since you want something slightly different, you could simply try to change the error metric involved. You could find a measure of "non-congruence" among the triangles and minimize that error. Most likely such an error function will be non-convex, so the non-linear conjugate gradient optimization described is as well as you can do.