Triangulation
www.visualnews.com www.cescg.org
www.iue.tuwien.ac.atwww.ceremade.dauphine.fr
Triangulation
• Dividing a polygon to a set of triangles
• Often with the constrain that each triangle
edge is fully shared by two triangles
• In 1925 it was proved that each surface can be
triangulated
Usage of triangulation
• Cartography, GIS
• Image processing – segmentation, pattern recognition
• Creating spatial models from laser scanning
• Spatial data visualization
• Finite element level set method – analysis of material
structure and properties, simulation
• Robot motion planning
• Simulation of natural phenomena – erosion
• Interpolation – transfer of point clouds to surfaces
• Biometry – fingerprints detection
Usage of triangulation
Triangulation
• Set of triangles T = Ti, i = 1, …, n is considered to
be a triangulation when:
– an arbitrary pair of triangles from T mutually
intersects in one common vertex or along a common
edge
– union of triangles from T is a continuous set
• Generally, the input is a continuous polygon
which does not have to be necessarily convex and
can contain holes
Triangulation
• Triangulation of a simple polygon P = dividing
P to triangles by a set of non-intersecting
lines, connecting two vertices from P and fully
lying inside P
• Triangulation is mostly non-unique
Triangulation
• Triangulation is the basic problem of
computational geometry – dividing complex
objects to simple ones
• The most simple objects are triangles in 2D (a
tetrahedra in 3D)
Triangulation
• There are several types of triangulation, e.g.:
– Delaunay triangulation – from all existing
triangulations it has the smallest sum of the
lenghts of all its edges, it is dual to the Voronoi
diagram
Triangulation
• For a given set of points (or a polygon) there are
several possible triangulations. But all of them
have the same number of triangles – triangulated
polygon with n edges has n – 2 triangles.
• Some polygons can be triangulated easily – e.g.,
convex ones
• Non-convex polygons have to be divided to socalled
monotone polygons. These can be then
easily triangulated.
Greedy triangulation
• Naïve approach
• Creates all potential edges, sorts them according
their length in an ascending order (the number of
these edges is n(n-1)/2)
• The edges are one by one added to the resulting
triangulation, we start with the shortest one
• The algorithm ends when the list of edges is
empty or when the number of edges in the
triangulation is 3n – 6
Greedy triangulation
• Criterion for adding the edge:
– Edge is added when it does not intersect with any
other edge already present in the triangulation
Greedy triangulation
repeat for all pi, i ∈ [1, n]:
repeat for j ∈ [i + 1, n]:
create edge e = (pi, pj)
for e compute d = dist(pi, pj) and store to Q
sort Q according to d
remove Q[0] and add it to T
until Q not empty
e = pop(Q)
repeat for all ei ∈ T:
test if e intersects with ei ∈ T
if e does not intersect with any ei ∈ T:
add e to T
Greedy triangulation
• Triangles do not have to fulfill any special
condition – the triangulation can contain
“ugly” triangles
• Complexity O(n3), can be optimized to
O(n2 log n)
Triangulation using sweep line
• For simplicity lets assume that we are
triangulating a monotone polygon
Monotone polygon
• Polygon is monotone when its intersection
with each horizontal line is convex (it is empty
set, point, or line) – the orientation of the
polygon matters!
Triangulation using sweep line
• 1st step: Lexicographically sort the vertices of
the convex hull
p > q py > qy or py = qy and px < qx
Triangulation using sweep line
• We determine the left and right path (split at
minimal and maximal point according to
lexicographical sorting) – they are stored in
two queues
left path right path
Triangulation using sweep line
• Algorithm is trying to create new triangle
always when the sweep line intersects with a
vertex of the polygon
• We use another data structure – stack. It will
contain vertices above the sweep line (already
traversed ones), which were not yet
triangulated
Triangulation using sweep line
sort vertices v1, v2, …, vn lexicographically
put v1, v2 to stack
for i = 3 to n:
if vi and the top of the stack lie on the same path (left or right)
add edges vivj, …, vivk, where vk is the last vertex
forming the “correct” line
pop vj, …, vk-1 and push vi
else
add edges from vi to all vertices stored in stack and
remove (pop) them from stack
store vtop
push vtop and vi
Triangulation using sweep line
First branch of the if condition:
Stack will contain (bot, …, vk, vi)
Triangulation using sweep line
else branch of the if condition:
Stack will contain (vj, vi)
Triangulation using sweep line
Yet another example
Time complexity
• Each vertex is added to the stack only once –
when “visited”, it is removed from stack
• In each step we add at least one edge
• Total triangulation time: O(n log n)
Your assignment
• Implement the sweep line algorithm for polygon
triangulation
• Our input data:
– Convex hull (created in previous assignments)
– Arbitrary polygon (has to be added to the basic
framework – simple connection of points added by
the user to the scene. We connect them in the same
order as they were inserted to the scene + connecting
the first and last point to close the polygon. We skip
the test for monotonity (we assume that the user
creates a monotone polygon, if not, we are fine with
wrong result ☺)