Click here to Skip to main content
13,047,567 members (60,847 online)
Click here to Skip to main content
Add your own
alternative version


29 bookmarked
Posted 22 Nov 2009

Triangulation of Arbitrary Polygons

, 22 Nov 2009
Rate this:
Please Sign up or sign in to vote.
This article describes a way of triangulating polygons that is intuitively easy to understand and explain diagrammatically


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.


  • 21st November, 2009: Initial version


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

Daniel Chia
Singapore Singapore
No Biography provided

You may also be interested in...

Comments and Discussions

QuestionWhat about harder cases? Pin
supercat924-Nov-09 12:36
membersupercat924-Nov-09 12:36 
AnswerRe: What about harder cases? Pin
Daniel Chia24-Nov-09 18:17
memberDaniel Chia24-Nov-09 18:17 
GeneralRe: What about harder cases? Pin
supercat930-Nov-09 6:25
membersupercat930-Nov-09 6:25 
Add a vertex between the two dotted lines, just above the one labeled (3 4); delete the edge connecting the upper-left and upper-right corners, and add edges connecting each of those corners to the new vertex.

Also, I'm curious whether doing horizontal raster splits is the best approach. I'm pretty sure that any simple (non-self-intersecting) polygon with four or more vertices will always have two vertices which may be connected without passing through any other edges or vertices. If one were to locate two such vertices, one could divide the polygon into smaller polygons, each of which could be split in like fashion. Doing that would yield a subdivision into (edges-2) triangles.
GeneralRe: What about harder cases? Pin
Daniel Chia1-Dec-09 4:57
memberDaniel Chia1-Dec-09 4:57 
QuestionIs your triangulation algorithm dependent on XNA? Pin
Ozgur Ozcitak22-Nov-09 22:16
memberOzgur Ozcitak22-Nov-09 22:16 
AnswerRe: Is your triangulation algorithm dependent on XNA? Pin
azurerain23-Nov-09 5:29
memberazurerain23-Nov-09 5:29 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

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

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.170713.1 | Last Updated 22 Nov 2009
Article Copyright 2009 by Daniel Chia
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid