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

Does Triangle do what you want?

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

Answer 2

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

Some pseudocode:

• Place an axis-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

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.

Answer 4

This can be done for concave/convex polygons using a simple ear-clipping method (assuming we don't need to support holes).

• Tessellate the polygon
  http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.115.291
• Rotate edges between triangles where the area divided by the perimeter is smaller once the edge is rotated into the new state.

This is 2 steps, so it may be more efficient to iteratively clip the 'best' ear to get more even results, so you don't have to re-arrange topology as a second pass (YMMV).
(Note that the reasons 2 steps are used here is that calculating more even distribution isn't always needed).

---

Full disclosure, I ran into this problem myself, when I needed a fast tessellator for polygons for a real-time modeling application.

Working implementation written in C,
which take and return POD's (float[2] array, filling in a uint[3] array):

• polyfill_2d.c (tessellates)

• polyfill_2d_beautify.c (adjusts topology for more even results)

• also made a port of polyfill_2d.c to Rust

(Note, the ear clipping is based on libgdx with spatial optimizations to the intersection checks, to scale up to thousands of sides without such a significant performance hit, since clipping every ear was checking all-other-points each time).