| Isomorphic Triangulation of Simple Polygons | Diana Garroway | |
|
||
Triangulation of simple polygons is a
common problem in Computational Geometry and has applications in many
different sciences. It has been well studied and many algorithms
exist. This webpage is dedicated to a slightly different problem:
triangulating 2 simple polygons in manner such that there exists an
isomorphic mapping between the two triangulations. Thus
just any triangulation algorithm will not suit our purpose. The
motivation for this problem comes from morphing algorithms in computer
graphics. In order to morph (interpolate) from one simple polygon
to another, and guarantee that the intermediate polygons are also
simple, it is often the case that a isomorphic triangulation of the two
polygons must be first known.
What is an Isomorphic
Triangulation?
The triangulations of two simple polygons, Tp and Tq, are called
isomorphic (or sometimes compatible) if there exists an isomorphism from the vertices of P to the
vertices of Q and the isomorphism holds the property that three
vertices of P form a triangle in Tp if and only if the mapping of the
three vertices in Q also form a triangle in Tq.
For example, in Figure 1, the mapping from polygon P to
polygon Q is shown using corresponding letters. Notice that
triangle(a, b, c) in P maps to triangle(a', b', c') in Q. So far,
we have followed the rules for an isomorphic triangulation, but the
mapping must hold for every set of 3 vertices. In Figure 1, triangle(
a, c, d) in P does not map to a triangle in the triangulation of Q, and
thus the shown triangulations of P and Q are not isomorphic under the
given vertex mapping. In this case, in order to make the
triangulations isomorphic, we have two options: we could change the
mapping or re-triangulate the polygons. The
example shown in Figure 2, re-triangulates polygon Q in order
to make the triangulations isomorphic. Now for each triangle in
polygon P, there is an equivalent triangle in polygon Q.
Figure 1: An example of triangulations of two simple polygons that are not isomorphic under the given mapping.
Figure 2: A new triangulation of Q such that the triangulations are isomorphic under the given mapping.
For any two simple
polygons, does an isomorphic triangulation always exist?
No, not always. Figure 3, shows an example of two simple
polygons that do not have an isomorphic triangulation. It does
not matter how the vertices are mapped, an isomorphic
triangulation does not exist.
Figure 3: An example of 2 polygons that do not have
triangulations that are isomorphic.
Then what do we do?
If extra points are allowed to be inserted into the interior of the
polygons, then we can guarantee that an isomorphic triangulation always
does exist. These extra points are called Steiner points.
For example, with the polygons P & Q from Figure 3, if we
add a single point to the centre of each, then an isomorphic
triangulation exists. Figure 4, shows this triangulation.
Figure 4: Isomorphic triangulation of P & Q with
1 steiner vertex.