This algorithm demonstrates a way of triangulating polygons that is intuitively easy to understand and explain diagrammatically. However, this technique produces a sub-optimal number of triangles, a condition slightly ameliorated by a greedy merge of adjacent triangles. A second disadvantage is that the resulting triangulation of a polygon is inherently tied to its rotation.
Description and Explanation of the Algorithm
Polygon decomposition into triangles is a subject classed under the computer science branch of computational geometry, and is generally solved using:
For objects with more than 3 vertices, the test for convex polygons is performed by taking the cross product of the two vectors at each vertex of the polygon to obtain the perpendicular vector v. A convex polygon will have all vs facing the same direction, whereas a concave polygon will have vs facing both directions. A convex polygon with n vertices can always be triangulated into n-2 triangles in O(n) time by taking any vertex as the origin and adding edges to all vertices except its two adjacent vertices without further calculations.
Polygons detected as concave will be put through the regular triangulation algorithm. This begins with horizontal decomposition, where imaginary horizontal lines are extended from each vertex of the dynamic object, and intersections of these imaginary lines with polygon edges of the dynamic object are added as vertices. The new vertices added by horizontal decomposition facilitate the decomposition of the polygon into triangles and trapezoids. The polygon is traversed top-down, from left to right.
Figure 1: An example of horizontal decomposition at work.
Considering two horizontal rows at a time, we extract edge pairs from left to right and, based on information on whether the two edges of a pair intersect, deduce if the edge pair forms a triangle or trapezoid. Intersecting edge pairs form triangles, and trapezoids otherwise. As an example, take Figure 1’s y1 and y2 as the two rows. The first two edges from the left form the first edge pair, and since they do not intersect, we know this pair forms a trapezoid. The second edge pair formed by edges 3 and 4 intersects at y2, so we know this pair forms a triangle. Using this algorithm, we can decompose the polygon into triangles and trapezoids. Trapezoids then need merely be further decomposed into two triangles by adding a diagonal edge between two opposite corner vertices. Upon reaching the bottom of the polygon, triangulation is done. This algorithm takes O(n log n) time.
Figure 2: Merge-able triangles.
At the next stage, the greedy merge algorithm considers, for each triangle, whether it is possible to merge with any other triangle of the polygon and result in a larger combined triangle. Merge-able triangles have two properties, depicted in Figure 2. They each have a coincident, identical edge, and a parallel non-coincident edge that coincides at a vertex. Merge-able triangles are found, merged, and the algorithm repeats until no more merge-able triangles can be found. The time complexity of this algorithm is O(n2), scaling with the number of triangles in the polygon. The maximum number of edge-edge comparisons for each polygon required is f(n) = (n-1)*9 + f(n – 1), where n is the number of triangles fed into the algorithm.
Figure 3: Three different triangulation methods for the same polygon.
Left: Base triangulation method. Middle: Triangulation with merge. Right: Handled as convex.
While horizontal decomposition into triangles does not result in an optimal number of triangles, the implemented optimizations to reduce the final number of triangles bring us closer to the optimal number. The merits of this technique are in its elegance and ease of implementation. It localizes the problem of triangulation by a systematic polygon traversal of edge pairs, then compensates for non-optimality with a greedy merge.
The triangulation algorithm flows thus:
- if(object has 3 vertices)
- add to triangle vertex list
- end if
- else if(object is convex)
- decompose as convex object
- add decomposed triangles’ vertices to triangle vertex list
- end else if
- add vertices to object via horizontal decomposition
- triangulate and merge
- store triangles in temporary list 1
- re-wind trapezoid
- triangulate and merge
- store triangles in temporary list 2
- add triangles’ vertices from list with lower triangle count to triangle vertex list
- end else
Using the Code
This algorithm was coded in C# and utilizes the Farseer Physics engine. To create a polygon for triangulation, use the left mouse button to select vertices, then press ‘a’ to finalize and triangulate the polygon. Right mouse button allows you to undo last vertex or delete a polygon. Pressing ‘z’ toggles greedy merge on and off.
- 21st November, 2009: Initial version