|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.