Isomorphic Triangulation of Simple Polygons	Diana Garroway
Introduction | Definitions | Algorithm | Applet | History/Links

---

This applet has been designed to demonstrate the concept of creating isomorphic triangulations of two simple polygons.  It demonstrates the algorithm that is overviewed here.   Download the source for the applet here.  This source maybe used/distrubuted under the GNU software license.



Java applet

Limitations:

           This applet works for most polygons, but does occasionally fail by producing a triangulation that has edges that cross at non-vertex intersections.  This is due to a bug in the algorithm to embed the spiderweb connectivity into the polygons.  This algorithm was developed by Diana Garroway is outlined below.  The algorithm sometimes has trouble with skinny polygons, and polygons with large vertex weights.  Note:  The triangulation is correct in most cases, but please try another polygon if you see this problem.

Embeding Algorithm (just for interest!):
   
             For i = MaxWeight down to MinWeight do
                   For each polygon vertex j
                            if j has weight i
                                  create new vertex epsilon distance inside polygon from j
                                  Weight of j = Weight of j-1

                   For each polygon vertex j
                            if j has not been projected and j has Weight >= i and j is an ear of the inner polygon of weight i
                                     project j's newest epsilon vertex to fall on edge (j-1, j+1)
                            if j has already been projected, project j's newest epsilon vertex

             --> This algorithm can fail on skinny polygons because epsilon is fixed and it is possible that epsilon distance from the vertex is outside of the polygon.
             --> This algorithm can also fail if a polygon vertex never becomes an ear of the inner polygon.  This rarely happens, but is possible for polygons with large vertex sets.

             --> If you have a better algorithm, please email dianag@cim.mcgill.ca !