1
TCG2061 Computational GeometryChapter 6 (30/07/00)page
Chapter 6. Polygon Triangulation
6.1 Definition and Properties
A triangulation of a polygon is a decomposition of the polygon into a set of triangles with the following properties:
i)The vertices of the triangles must be vertices of the polygon.
ii)The edges of the triangles must not intersect. That is, the intersection of the interiors of any pair of triangles is empty.
iii)The union of all the triangles is the complete original polygon.
Polygon triangulation is often used to reduce problems involving complicated regions to problems involving only triangles. Such problems become easier to solve when reduced to triangular regions, since triangles are the simplest of regions to process.
Examples of applications that use polygon triangulation include point inclusion tests, and the rendering of complex polygons.
If all triangles in a polygon triangulation share a common vertex of the polygon, then the polygon is said to be triangulated from the vertex. Conversely, a polygon is triangulated from a vertex v, if it is possible to connect the vertex v to all of its non-adjacent vertices by chords to produce a triangulation.
6.2 Triangulation of Convex and Star-shaped Polygons
A convex polygon can be triangulated from a vertex using any of its vertices. (We can prove this by the fact that the interior of a convex polygon is its kernel. All points can "see" all other points and therefore any vertex can see all other vertices in the polygon.)
A star-shaped polygon can be triangulated from a vertex if its kernel contains at least one vertex of the polygon. Any vertex of the polygon that is also part of its kernel can see all other vertices of the polygon. A star-shaped polygon cannot be triangulated from a vertex if its kernel contains no vertices of the polygon.
6.3 Triangulation of x-Monotone Polygons
6.3.1 The Problem
X-monotone polygons have the property that any vertical line passing through the polygon will intersect the polygon edges in at most two places. This fact guarantees that any x-monotone polygon has an upper and lower chain of vertices that do not double-back on themselves. In general it should be possible to work through the polygon from left to right, splitting off triangles by connecting vertices from the upper chain with vertices in the lower chain. This is illustrated in the following figure.
There are several problems with this simplistic scheme. For example, what criteria should be used to select the vertices to connect from each chain? There are multiple ways to connect the vertices, as shown by the different triangulation below of the previous example. Which triangulation is "better?" In this context, what does "better" mean?
Another problem arises from the possibility of creating invalid triangles by connecting inappropriate vertices from each chain. The example below violates two criteria of triangulation: the new edge intersects a polygon edge and it encloses an interior area not part of the original polygon.
6.3.2 The Algorithm's Logic
The following algorithm was designed to efficiently triangulate x-monotone polygons and overcome the problems discussed in the previous section. Before the full algorithm is presented, let's examine specific details of the algorithm's logic.
Before processing begins, the vertices of the polygon are sorted by increasing x-coordinates. The vertices of the polygon are then processed one at a time from left to right (from minimum x-coordinate to maximum x-coordinate). For each vertex, one of two things will happen: either the vertex will be used to split off one or more triangles from the polygon or it will be saved on a vertex-stack for later use. The vertex-stack saves vertices on the same vertex chain (upper or lower chain) until a suitable vertex can be found to connect to them. Initially the vertex-stack is loaded with the first two vertices of the polygon. For the purposes of the following discussion, the vertices stored in the vertex-stack are labeled s0, s1, s2, s3, ... stwhere strepresents the vertex at the top of the stack.
At any intermediate stage of the algorithm there are three types of vertices:
- vertices that have been fully processed, thus splitting off a set of triangles from P,
- vertices in the vertex-stack waiting to be used, and
- unprocessed vertices.
An example of these types of vertices is shown in the following figure. The unprocessed (un-triangulated) region of P is denoted by P.
The polygon P has the following properties:
i)P is x-monotone.
ii)Initially P = P.
iii)When the polygon triangulation is complete, P = .
The stack-vertices have the following properties:
i)s0 is the leftmost vertex of the polygon P.
ii)s0,s1, s2, s3, ... st are consecutive vertices on either the upper chain or the lower chain of P.
iii)s1, s2, s3, ... st1 are reflex vertices in P.
iv)The vertex st which is at the top of the stack, is the last examined vertex.
Now consider the following cases as a new vertex v is processed. We call v the current vertex. Due to the lexical ordering of the vertices in the x-direction, v is always on the right of st. There are two cases to be considered:
Case 1:v and st are neighbors in P'.
This means v lies on the same chain as s0, s1, s2, s3, … st. In this situation, there are two sub-cases to consider.
Case 1a:The vertex stis reflex in P.
Therefore v cannot be connected by chords to any of the stack vertices. (The chord would lie outside of P' and possibly outside of P.)
Action: Push v onto the top of the stack for later processing.
Case 1b:The vertex st is convex in P.
Therefore v can be connected by chords to at least one vertex on the stack.
Action: As long as the angle vstst1 is less than 180 degrees, create a chord from v to st-1 and pop st off the stack. Stop creating chords when the angle vstst1 is greater than or equal to 180 degrees or when there are less than two vertices on the stack. Then push v onto the stack.
Case 2:v and s0 are neighbors in P'.
That means v lies on the opposite chain as s0, s1, s2, s3, … st. Therefore the vertex v is visible to all of the stack vertices.
Action: Chords for vsi are added for each vertex on the stack (except s0, since v and s0 are adjacent). After the chords are added, only the stack vertex st and v remain on the boundary of P. Hence all stack vertices are popped from the stack, and st is pushed onto the stack, followed by v.
The above process is repeated for each vertex of P until all vertices have been fully processed, i.e., when the last vertex examined is the rightmost vertex of P.
6.3.3 The Algorithm in Pseudocode
Note:The vertex stack is stored as an array named s, where s[0] is the bottom element on the stack and s[t] is the top element on the stack. The variable t always contains the index of the top element on the stack.
Note:Indention indicates compound statements. Statements indented the same amount are part of the same loop or if statement.
Create a sorted list of the polygon's vertices, (ascending according to x).
s[0] = v0 (the first vertex from the sorted list)
s[1] = v1 (the second vertex from the sorted list)
t = 1 (the index of the top element on the vertex stack)
Set P' = P (P' is initially equivalent to the original polygon)
For each remaining vertex in the sorted list (vi, i=2, 3, 4, … n-1)
if vi is a neighbor to s[t] in P' (case 1)
while t >= 1 and angle(vs[t]s[t-1]) < 180 (case 1b)
create a chord from v to s[t-1]
create a new triangle vs[t]s[t-1]
remove s[t] from P'
remove s[t] from the vertex stack (t = t-1)
else vi is a neighbor to s[0] in P' (case 2)
oldTop = t (remember the vertex on the top of the vertex stack)
while t > 0 (i.e., while the vertex stack has more than 1 point)
create a chord from v to s[t]
create a triangle vs[t]s[t-1]
remove s[t] from P'
remove s[t] from the vertex stack (t = t-1)
s[0] = s[oldTop]
t = t+1 (increase the size of the vertex stack)
s[t] = vi (the last step for every case puts vi on the vertex stack)
6.3.4 An Example
An x-monotone polygon and its triangulation are presented. The vertices are labeled such that they are lexicographically sorted in the x-direction. A "walk-through" of the algorithm as it triangulates the polygon is provided in the table.
Stack / Current Vertex / Algorithm Case / ChordsCreated
V2
V1 / st
s0 / V3 / 2 / V3-V2
V3
V2 / st
s0 / V4 / 2 / V4-V3
V4
V3 / st
s0 / V5 / 2 / V5-V4
V5
V4 / st
s0 / V6 / 2 / V6-V5
V6
V5 / st
s0 / V7 / 1b / V7-V5
V7
V5 / st
s0 / V8 / 1a
V8
V7
V5 / st
s1
s0 / V9 / 1a
V9
V8
V7
V5 / st
s2
s1
s0 / V10 / 1b / V10-V8,V10-V7
V10
V7
V5 / st
s1
s0 / V11 / 1b / V11-V7
Stack / Current Vertex / Algorithm Case / Chords
Created
V11
V7
V5 / st
s1
s0 / V12 / 2 / V12-V11,V12-V7
V12
V11 / st
s0 / V13 / 1b / V13-V11
V13
V11 / st
s0 / V14 / 1a
V14
V13
V11 / st
s1
s0 / V15 / 1b / V15-V13,V15-V11
V15
V11 / st
s0 / V16
V16
V15
V11 / st
s1
s0 / V17 / 2, 1b / V17-V15
6.4 Summary
To triangulate a simple (non-intersecting) polygon, an appropriate algorithm must be used as follows:
Polygon type / Algorithmconvex polygon / triangulate from any vertex.
star-shaped polygon / calculate its kernel; if the kernel contains a vertex, triangulate form that vertex; if not, ?.
x-monotone polygon / algorithm presented in section 6.3.
not star-shaped and not x-monotone / convert to a series of x-monotone polygons using the (incorrect) algorithm in chapter 2; then use the algorithm in section 6.3 on each x-monotone polygon.