Guaranteed intersection-free polygon morphing

We present a method for naturally and continuously morphing two simple plan ar polygons with corresponding vertices in a manner that guarantees that th e intermediate polygons are also simple. This contrasts with all existing p olygon morphing schemes who cannot guarantee the non-self-intersection prop erty on a global scale, due to the heuristics they employ. Our method achie ves this property by reducing the polygon morphing problem to the problem o f morphing compatible planar triangulations of corresponding point sets, wh ich is performed by interpolating vertex barycentric coordinates instead of vertex locations. The reduction involves compatibly triangulating simple p olygons and polygons with a single hole. We show how to achieve this using only a small number of extra (Steiner) vertices. (C) 2001 Elsevier Science Ltd. All rights reserved.