Morphing between many polygons.
Morphing between different numbers of polygons across a change in
topology remains as an unsolved problem although there are many
solutions for morphing between two polygons or one-to-one morphing. A
new algorithm is presented in this paper for morphing between many
polygons. Delaunay triangulation is used to set up the correspondence
between vertices. An incremental Delaunay triangulation algorithm is
implemented for this purpose. We also present a supersampling method of
the polygons for making the Delaunay triangulation of the vertices in
the supersampled polygon equal its constrained Delaunay triangulation.
According to the correspondence, the gap between the source group and
the target group will dynamically shrink until it is completely zipped
up at the approximation of its medial axis. Our method can guarantee
that there is no self-intersection during the zipping process. The morph
requires no user interaction, is inexpensive, uses dynamic vertex
correspondence, and follows nonlinear vertex paths.
Xiaqing Wu, John K. Johnstone, Dept. of Computer Science, Univ. of
Ala. At Bham., Birmingham, AL, 35294-1170.