BACKGROUND
Polygon triangulation is an essential problem in computational
geometry because working with a set of triangles is faster than
working with an entire polygon in case of complex graphics.
Polygons are very convenient for computer representation of real world object boundaries. Real world objects can be very complex as they can include polygons with a few thousand vertices, they may be convex or concave, have self intersections and may include nested holes and often there is need to decompose the polygons into simpler components that can be easily and rapidly processed.
Several algorithms such as color filling, character recognition, shading and shortest path rely entirely upon partitioned polygons.
Polygons are very convenient for computer representation of real world object boundaries. Real world objects can be very complex as they can include polygons with a few thousand vertices, they may be convex or concave, have self intersections and may include nested holes and often there is need to decompose the polygons into simpler components that can be easily and rapidly processed.
Several algorithms such as color filling, character recognition, shading and shortest path rely entirely upon partitioned polygons.
A video card,
also referred to as a graphics accelerator
card / display adapter is an item of personal computer hardware whose
function is to generate and output images to a display. The
graphics card is responsible for simplification (Triangulation) of
complicated display objects in real time so that the main processor
can handle the display objects much faster. Without the
simplification the display will not be processed in real time and the
display will be delayed. For example in computer games, the display
depends on the user inputs, like if one is playing a car race game
and if the user presses ↑ key, the car should move forward
immediately; but if the frames or the display objects are not
processed fast enough then the display is rendered after some delay i.e.
the perception of car moving forward is delayed. This delay hampers the real
time game play experience. Triangulation is one of the
many logics which are present in a graphics card which helps in accelerating the rendering of complex objects on computer screen.
The problem of polygon triangulation can be stated as “given
the coordinates of the n vertices of a polygon P in order around P,
find n3 diagonals that partition P into n2 triangles”.
See figure 1. Red lines represent actual polygon contour
whereas inner black lines represent new diagonal edges introduced
after triangulation of a polygon.
Figure 1  A triangulated polygon
SEIDEL'S ALGORITHM
Given the importance of triangulation, a lot of effort has been put into finding
a fast polygon triangulating routine. The simplest recursive
triangulation of a polygon runs in time O (n^{3}) by cutting
ears from the polygon. O (n^{2}) algorithms have been known
since at least 1911. But it wasn’t until 1978, when Garey et al
found an O (n log n) algorithm that real work started in this field.
A variety of new algorithms were found pushing the limit further and
further down. In 1984 it was shown that given a trapezoidation of a
polygon, a triangulation could be obtained in linear time and further
work focused on finding an efficient way of computing such a
trapezoidation. However, the outstanding open problem in
computational geometry, that of the lower time bound of
triangulation, was not solved until Chazelle found a purely linear
algorithm in 1990. This algorithm is very complex to implement.
In 1991, Seidel found a practical algorithm for triangulating
polygons with an expected running time of O (n log*n). The algorithm
can triangulate any set of overlapping and selfintersecting polygons
and lines in the plane with nearlinear expected time. Its virtues
lie in its simplicity. It uses no divideandconquer or recursion and
no “Jordan Sorting”. Its expected performance admits a very
straightforward and selfcontained analysis. Finally, it is practical
and relatively simple to implement, a property that very few, if any,
of the algorithms mentioned can claim.
It should also be mentioned that in 2000 Amato et al. found a
similar linear algorithm with far less overhead than Chazelle’s, by
using randomization as in Seidel’s algorithm. This would still be a
formidable job to implement with all its details.
Seidel’s algorithm suggests following steps for triangulation of a
polygon: 
1. Trapezoidal decomposition or trapezoidation
2. Generation of monotone mountains
3. Triangulation by ear clipping method
1. Trapezoidal decomposition or trapezoidation
A
trapezoidation is formed by extending a horizontal ray in each
direction from every vertex, and stopping the ray as soon as it hits
another edge. This will divide the plane into regions by edges and rays,
and each such region is a trapezoid. A trapezoid has a horizontal upper
and lower boundary, and an edge or a piece of an edge as a boundary on
either side. Either the upper or lower boundary may have zero length, in
which case the trapezoid will be a triangle. The set of trapezoids
obtained in this manner is called a trapezoidation, and is unique for
any given polygon. See figure 2.
Figure 2 Trapezoidal decomposition
Seidel’s
algorithm is a randomized way of computing trapezoidation. This means
that every edge is equally likely to be added in the trapezoidation. For
this purpose a random sequence of edges is generated. This ensures that
actual running time will not be significantly worse than expected
running time.
Trapezoidation
routine starts with an empty plane and adds in edges one by one. The
algorithm checks if endpoints of the edge are added to the
trapezoidation already. Those which have not been added are added one by
one. This will divide the region (in which point is added) into two by
means of horizontal rays starting from that point and extending in both
directions (left & right). Next the edge is added between two
points. This is done by starting from the top point and moving down one
region at a time, until bottom point is reached. For each region
traversed in this manner, the region is divided in two by means of the
new edge. Whenever this causes two regions on top of each other to have
same left and right hand boundary, these two regions are merged into
one. Each of the regions created in this manner will be a trapezoid.
Note that in doing this; we never need to explicitly calculate the
intersections of edges and rays.
Each
trapezoid will know which edges and rays it is bounded by. For this we
will have a special memory structure which stores information about each
trapezoid. This structure is explained as below.
Trapezoid Data Structure:
High  Upper vertex of the trapezoid
Low  Lower vertex of the trapezoid
U1, U2  Upto two adjacent trapezoids above
D1, D2  Upto two adjacent trapezoids below
U3  Third extra region above (if any)
U3 SIDE  Determines whether the third extra region is towards left or right
LSEG, RSEG  Left and right edges of the trapezoid
SINK  Position of trapezoid in tree structure (discussed later)
STATE  Represents validity of trapezoid (Inside or outside)
The algorithm also needs to be able to efficiently tell where to place
new points in the current trapezoidation. One way of doing this is by
creating a tree lookup structure for trapezoids. The tree starts only
with a root representing the original empty plane and each time a region
is split in two, the corresponding leaf in the tree is changed into a
node with two children. This new node can either be a vertex or an edge.
The two children represent two resulting trapezoids. Thus each leaf in
the tree represents a trapezoid (region) and each node in the tree
represents either vertex or edge. By querying whether the point we are
adding is above or below a vertex in the tree, or to which side of an
edge it is, we can traverse the tree to find the correct region in which
the point will be added. The tree is a strict binary tree and also
called as “query structure”. This tree structure is explained below.
Query Structure:
Node type  Whether the node in tree is vertex or edge or trapezoid
Segment number  Points to vertex or edge if node type is either vertex or edge
Trapezoid number  Points to trapezoid in trapezoid data structure if node type is trapezoid.
Left  Points to left child node
Right  Points to right child node
Parent  Points to parent node
Steps for adding an edge in the trapezoidation are as follows:
1. Select an edge from randomly generated sequence of edges
2. Find higher vertex of that edge
3. Traverse the tree to find correct region in which higher vertex will be added
If
vertex is not already added, change the leaf node (trapezoid) into a
vertex node. This node will have two trapezoids as its left and right
children. Left child represents region below the vertex whereas right
child represents region above the vertex. Right child trapezoid is old
region to be split by the vertex. Left child trapezoid is new region
introduced after addition of vertex. Update the trapezoid structure.
If
vertex is already added (as part of previously added edge), just
traverse the tree to find the region in which the vertex reside. This is
required for addition of an edge.
4. Add lower vertex
to the trapezoidation and follow the same procedure as for higher vertex
to traverse the tree and find correct region.
5. Finally, add the
edge starting from higher vertex to lower vertex. This edge will split
all the regions which are below higher vertex and above lower vertex.
Update the trapezoid structure, for regions split by the edge.
Let us take an example to understand the procedure
Consider trapezoidation of polygon as in figure 3.
Figure 3  Sample Polygon
Let edge CD is added to the trapezoidation. Note that Query structure will contain only one region before
addition of edge CD as CD is the first edge to be added.
Add point C to trapezoidation as it is higher vertex.
Different condition that can occur while adding part of an edge in a
region are explained below. These conditions are discovered using extensive trial and error
method and lexicographic techniques.
Red lines represent already inserted edges. Blue line represents
current edge being added.
Sub condition 2: Three trapezoids above
Update tree structure
Add point D to trapezoidation
Traverse the tree to find correct region. Point D will split region
2.
Update the tree structure by adding point D and introducing two leaf
nodes to the left and right of D. Left node represents region 2
whereas right node represents new region viz. region 3.
Add edge starting from point C to point D
Edge CD will split region 2. Update tree structure by creating new
node representing
edge CD. Left child of node CD will be region 2 (old region) and
right child will be region 4 (new region).
Follow the same procedure for remaining edges.
Note that, for node type vertex in the tree, left of represents
below where as right of represents above. For node type edge left of
represents left and right of represents right.
While adding the edge to trapezoidation, trapezoid structure must be
updated also.
Condition 1: No trapezoids below (This condition is not possible)
Condition 2: Only one trapezoid below
Sub condition 1: Two trapezoids above
Sub condition 3: Only one region above and left to right
upward cusp
Sub condition 4: Only one region above and right to left upward cusp
Sub condition 5: Fresh segment
Sub condition 6: Last region forms left to right downward cusp
Sub condition 7: Last region forms right to left downward cusp
Sub condition 8: Intermediate region (Addition of edge results in
three upper neighbors)
Condition 3: Two trapezoids below
Sub conditions handled in this part are same as those in condition 2.
Only exception is that we must check whether the edge being added
divides d1 or d2.
2. GENERATION OF MONOTONE MOUNTAINS
Given the trapezoidation of a polygon, a triangulation can be
easily computed in linear time. Let us consider only those trapezoids
that are inside the polygon, as these are the ones we will want to
triangulate. Trapezoids which lie inside the polygon are found out
using fill rule. Fill rule and it’s realization for triangulation
is explained in section later below.
First of all, note that each trapezoid will be empty, i.e. there
will be no vertices or edges inside it. Further note that the upper
and lower boundaries of each trapezoid are created by the extension
of rays from vertices, such that each trapezoid has one bounding
upper and one bounding lower vertex. Lower is defined here
lexicographically, i.e. of two vertices with the same ycoordinate;
the rightmost will be considered lower. This is assumed for all
vertices and it assures that no edge is being treated as if it was
horizontal, and that no trapezoid will have more than one upper and
one lower bounding vertex. In some cases the two bounding vertices
will be on the same side of the trapezoid, and in other they may be
on opposite sides, or in the middle. Whenever the two vertices are
not along the same edge, one can draw a diagonal between them without
intersecting any edges since each trapezoid is empty.
Addition of these diagonals is illustrated in figure 4. Resulting
polygons bounded by edges and diagonals are termed as monotone mountains.
Monotone mountains have one edge called the base, which extends
from the uppermost point to the lowermost point. The rest of the
vertices form what is called a monotone chain, which is characterized
by the fact that traversing polygon from the top, every vertex will
be lower than the previous one. If a monotone mountain is put with
its base extending horizontally, it resembles a mountain range, hence
its name. See figure 4.
Figure 4  Introduction of trapezoid diagonals
Multiple Polygons
A small demo video showing different polygon triangulation outputs obtained from implementation of above algorithm 
Fill Rule
A simple, nonselfintersecting closed path divides the plane
into two regions, a bounded inside region and an unbounded outside
region. Note that knowing the orientation of the outermost path (i.e.
clockwise or anticlockwise) is not necessary to differentiate between
the inside and outside regions.
A path that self intersects, or that has multiple overlapping
sub paths, requires additional information in order to define the
inside region. Two rules that provide different definitions for the
area enclosed by such paths, known as the nonzero and even/odd fill
rules are discussed in this paper.
To determine whether any point in the plane is contained in the
inside region, imagine drawing a line from that point out to infinity
in any direction such that the line does not cross any vertex of the
path. For each edge that is crossed by the line, add 1 to the counter
if the edge starts from top to bottom (starting point is above) and
subtract 1 if the edge starts from bottom to top (starting point is
below). In this way, each region of the plane will receive an integer
value.
The nonzero fill rule says that the point is inside the polygon
if the resulting sum is not equal to zero.
The even/odd fill rule says that the point is inside the polygon
if the resulting sum is odd, regardless of sign (i.e. 3 is odd).
Consider the starshaped path shown in Figure 5 and 6 below,
indicated with solid lines. The orientation of the lines making up
the path is indicated with arrows. An imaginary line to infinity
starting in the central region of the star is shown as a dashed line
pointing to the right. Two edges of the star cross the line to
infinity going top to bottom, indicated by the downwardpointing
arrows. The central region therefore has a count of +2. According to
the even/odd rule, it is outside the path, whereas according to the
nonzero rule it is inside.
Figure 5  Even/odd fill rule Figure 6 
Nonzero fill rule
Fill Rule and Triangulation
Trapezoidation is the most important step in Seidel’s
algorithm. But as we know that, all trapezoids formed in this step do
not lie inside the polygon. Some of them lie outside or inside the
hole. So before going to build monotone chains, its necessary to mark
all trapezoids as inside or outside. Only those trapezoids which lie
inside the polygon are given as input to next step.
The question is how we can mark trapezoids as inside or outside
without knowing the orientation of the sub paths (i.e. clockwise or
anticlockwise). At this stage fill rule comes in picture. With the
help of fill rule and query structure built in trapezoidation phase
we can easily determine whether the trapezoid is inside or outside.
Note that interior seed point is not at all required.
As we know that each interior trapezoid is bounded by edges to
its left and right and for any trapezoid we can determine its
position in the query structure (remember sink?). Once the trapezoid
is located in tree structure, we traverse upwards until the node
representing left or right edge of that trapezoid is encountered. If
left edge is first encountered our direction will be left and if
right edge is first encountered our direction will be right. This is
done only for first trapezoid to determine direction of infinity
line. From this node (left or right edge) traverse the tree downward
to left or right (depending on direction) until node representing a
trapezoid is reached. This trapezoid is adjacent to the trapezoid
with which we started with. The nodes of type vertex also need to be
handled. For this additional variable to indicate the sub direction
is required. Initially we set this sub direction to left. So while
traversing downwards for odd occurrence of vertex node (1^{st},
3rd…) we go to left and change the sub direction to right. For even
occurrence of vertex node (2^{nd}, 4^{th}) we go to
right and change the sub direction to left. This alternate switching
of sub direction is related to the property of the tree structure
i.e. while adding the edge to the tree structure higher point is
added first and then lower point is added. While traversing downwards
if node of type edge is encountered and if direction is left (not sub
direction) we go to right otherwise (direction is right) we go to
left. If a node representing trapezoid is reached, we are in the
region adjacent to the region in which we were previously in.
For this newly encountered trapezoid check if it has both left
and right segments or not. If it has, traverse the tree upward until
the required segment node is not reached.
If direction is left we must traverse up to the node representing
left edge of this trapezoid and if direction is right we must traverse
up to the node representing right edge of this trapezoid. Once the
required edge is reached, again traverse downward (depending on
direction) until trapezoid node is reached. If the trapezoid which
does not have either left or right segment is reached, it means that
we are now outside the polygon and all the edges between the path of
infinity line are crossed. For each such edge crossed, we either
increment or decrement the counter depending on the direction of edge
(upward or downward).
If the counter is nonzero, according to nonzero fill rule,
corresponding trapezoid is inside.
If the counter is nonzero and odd, according to even/odd fill
rule, corresponding trapezoid is inside.
We continue with above procedure unless we are outside the given
input polygon. This is explained with suitable example as below.
Consider following input polygon.
Consider following input polygon.
Trapezoidation of above polygon is as shown below.
Query structure for above trapezoidation is as shown below.
Now suppose we want to determine whether trapezoid 10 is inside or
outside the polygon.

Traverse the tree upward until left or right edge of trapezoid 10 is reached.

In this case edge SR i.e. left edge will be reached first. Decrement counter, as edge SR is going upward.

From now onwards our direction will be left.

From edge SR traverse to the left until adjacent trapezoid is reached.

In our case, node Q in encountered (vertex node). This is first occurrence (odd) of vertex node so we proceed to left.

Edge QR is encountered. As the direction is left we go to right from this node.

Trapezoid 19 is reached which is adjacent to trapezoid 10.

Trapezoid 19 has both left as well as right segments.

From trapezoid 19, traverse upward until left segment of 19 i.e. QR is reached (note our direction is now left).

Increment the counter as edge QR is going downward.

Again from edge QR, traverse downward to the left (our direction is left) until trapezoid node is reached. Here trapezoid 16 will be encountered.

Trapezoid 16 has left as well as right segment.

Again from trapezoid 16, traverse upward until left segment of 16 i.e. AB is reached.

Increment the counter as edge AB is going downward.

From edge AB, traverse downward to the left (our direction is left) until trapezoid node is reached. Here trapezoid 2 will be encountered.

Trapezoid 2 does not have left segment, which means we are outside the polygon.

Check the counter value. For our case counter=1. According to nonzero as well as even/odd fill rule region 10 is inside the polygon.
3. TRIANGULATION BY EAR CLIPPING METHOD
If the inside angle between two edges of the polygon is less
than Ð», the vertex is convex. If the triangle described by a convex
vertex and its two neighbors contain no other vertices, the triangle
is an ear of the polygon. Any convex vertex of the monotone chain is
the tip of an ear, with the possible exception of the vertices of the
base. Cutting such an ear off from a monotone mountain will always
result in a smaller monotone mountain. This leads to a simple linear
procedure for triangulating such polygons. Start with a list of all
these convex vertices, and run through the list, cutting off each
convex vertex and creating a triangle. For each vertex that is being
cut, if its neighbors were not already convex, see if they have now
become convex, and if either one has, add it to the end of the list.
Once you have reached the end of the list, you are done. The
algorithm is summarized in Table1.
Monotone Mountain Triangulation
Initialize an empty list
Add all convex vertices, excluding the endpoints of the base to
the list
While list is not empty
Cut off the corresponding ear of the monotone mountain
Delete the vertex from the list
For the two neighbors of the vertex
If
the neighboring vertex is not an endpoint of the base, and was
made convex by cutting off the ear, then add
this neighbor to the list

Figure 7  Monotone Chain Figure 8 
Triangulated Polygon
After trapezoidation and generation of monotone mountains as you
see in the Figure 7 ABCD is the only partition that is not yet
triangulated. So the triangulation is completed using ear clipping.
B is a convex vertex as angle ABC is less than Ð» and there is no
vertex between A and C so diagonal is added between A and C and we
get the final triangulated output as shown in Figure 8.
Some sample outputs from 'C++' implementation of this algorithm:
Simple Polygon
Polygon with Holes
Some sample outputs from 'C++' implementation of this algorithm:
Simple Polygon
Polygon with Holes
Concentric Polygons
Polygons with Multiple Holes at Various Depths of concentricity
Multiple Polygons
A small demo video showing different polygon triangulation outputs obtained from implementation of above algorithm 
Comments
Post a Comment