Morphing simple polygons

ABSTRACT

In this paper we investigate the problem of morphing (i.e. continuously deforming) one simple polygon into another. We assume that our two initial polygons have the same number of sides n, and that corresponding sides are parallel. We show that a morph is always possible by a varying simple interpolating polygon also of n sides parallel to those of the two original ones. If we consider a uniform scaling or translation of part of the polygon as an atomic morphing step, then we show that O(n4/3+&egr;) such steps are sufficient for the morph.

REFERENCES

• CR: Joseph Culberson , Gregory Rawlins, Turtlegons: generating simple polygons for sequences of angles, Proceedings of the first annual symposium on Computational geometry, p.305-310, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323272]
• CW: K. Culik and D. Wood. A note on some tree similarity measures. In IPL, 15, pages 39-42, 1982.
• KR: A. Kaul and J. Rossignac. Solid-interpolating deformations. In Proceedings of Eurographics 1991, pages 494-505, 1991.
• SGWM: Thomas W. Sederberg , Peisheng Gao , Guojin Wang , Hong Mu, 2-D shape blending: an intrinsic solution to the vertex path problem, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.15-18, September 1993 [doi>10.1145/166117.166118]
• SG: Thomas W. Sederberg , Eugene Greenwood, A physically based approach to 2–D shape blending, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.25-34, July 1992
• STT: D D Sleator , R E Tarjan , W P Thurston, Rotation distance, triangulations, and hyperbolic geometry, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.122-135, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12143]
• T: C. Thomassen. Deformations of planar graphs. In J. Comb. Theory Set. B, 34, pages 244-257, 1983.
• V: V Vijayan, Geometry of planar graphs with angles, Proceedings of the second annual symposium on Computational geometry, p.116-124, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10528]
• W: E. Welzl. Personal communication, 1993.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

General Terms:
Algorithms, Theory, Verification