12,448,164 members (59,685 online)
alternative version

37K views
28 bookmarked
Posted

# Triangulation of Arbitrary Polygons

, 22 Nov 2009 CPOL
 Rate this:
This article describes a way of triangulating polygons that is intuitively easy to understand and explain diagrammatically

## Introduction

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:

### Convex Polygons

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.

### Concave Polygons

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.

### Greedy Merge

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:

1. if(object has 3 vertices)
2. add to triangle vertex list
3. end if
4. else if(object is convex)
5. decompose as convex object
6. add decomposed triangles’ vertices to triangle vertex list
7. end else if
8. else
9. add vertices to object via horizontal decomposition
10. triangulate and merge
11. store triangles in temporary list 1
12. re-wind trapezoid
13. triangulate and merge
14. store triangles in temporary list 2
15. add triangles’ vertices from list with lower triangle count to triangle vertex list
16. 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.

## History

• 21st November, 2009: Initial version

## About the Author

 Singapore
No Biography provided

## You may also be interested in...

 Pro Pro

## Comments and Discussions

 First Prev Next
 What about harder cases? supercat924-Nov-09 12:36 supercat9 24-Nov-09 12:36
 Re: What about harder cases? Daniel Chia24-Nov-09 18:17 Daniel Chia 24-Nov-09 18:17
 Sorry, I'm not sure what you mean by splitting the top segment in two, can you illustrate it graphically? I also don't quite follow what you mean by an "original" edge, so can you please clarify? Thanks for your comments
 Re: What about harder cases? supercat930-Nov-09 6:25 supercat9 30-Nov-09 6:25
 Re: What about harder cases? Daniel Chia1-Dec-09 4:57 Daniel Chia 1-Dec-09 4:57
 Is your triangulation algorithm dependent on XNA? Ozgur Ozcitak22-Nov-09 22:16 Ozgur Ozcitak 22-Nov-09 22:16
 Re: Is your triangulation algorithm dependent on XNA? azurerain23-Nov-09 5:29 azurerain 23-Nov-09 5:29
 Last Visit: 31-Dec-99 18:00     Last Update: 25-Aug-16 12:01 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.