Morphing between polylines
Alon Efrat, Sariel Har-Peled, Leonidas Guibas, T. M. Murali · 2001
We study the problem of continuously transforming or morphing two non-intersecting simple (not self-intersecting) polylines in the plane. Our morphing strategies have the property that every intermediate polyline is also simple. We also guarantee that no portion of the polylines to be morphed is stretched or compressed by more than a user-defined parameter during the entire morphing. Our algorithms are driven by a new metric for measuring the similarity between two polylines, which may have other applications. We compute morphing schemes that minimize this metric and also approximate the minimum value efficiently. Department of Computer Science, D340 Levine Science Research Center, Duke University, Box 90129, Durham, NC 27708-0129, USA, [email protected] http://www.cs.duke.edu/~sariel/ y Compaq Computer Corporation, Cambridge Research Lab, One Cambridge Center, Cambridge MA 02142, [email protected]. 1 1 Introduction In the last few years, the problem of continuously morph...