Click here to Skip to main content
15,860,972 members
Articles / Programming Languages / C#
Article

Triangulation of Arbitrary Polygons

Rate me:
Please Sign up or sign in to vote.
4.54/5 (7 votes)
22 Nov 2009CPOL4 min read 57.8K   5K   31   6
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.

Demo

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

Image 2

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.

Image 3

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

License

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


Written By
Singapore Singapore
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
QuestionWhat about harder cases? Pin
supercat924-Nov-09 12:36
supercat924-Nov-09 12:36 
AnswerRe: What about harder cases? Pin
Daniel Chia24-Nov-09 18:17
Daniel Chia24-Nov-09 18:17 
GeneralRe: What about harder cases? Pin
supercat930-Nov-09 6:25
supercat930-Nov-09 6:25 
GeneralRe: What about harder cases? Pin
Daniel Chia1-Dec-09 4:57
Daniel Chia1-Dec-09 4:57 
QuestionIs your triangulation algorithm dependent on XNA? Pin
Ozgur Ozcitak22-Nov-09 22:16
Ozgur Ozcitak22-Nov-09 22:16 
AnswerRe: Is your triangulation algorithm dependent on XNA? Pin
Daniel Chia23-Nov-09 5:29
Daniel Chia23-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.