Morphing simple polygons

被引：21

作者：

Guibas L. ^{[1
]}

Hershberger J. ^{[2
]}

Suri S. ^{[3
]}

机构：

[1] Department of Computer Science, Stanford University, Stanford

[2] Mentor Graphics, Wilsonville, OR 97070

[3] Department of Computer Science, Washington University, St. Louis

来源：

Discrete & Computational Geometry | 2000年 / 24卷 / 1期

关键词：

Simple Polygon; Uniform Scaling; Initial Polygon;

D O I：

10.1007/s004540010017

中图分类号：

学科分类号：

摘要：

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 through an interpolating simple polygon whose n sides vary but stay 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 (n log n) such steps are sufficient for the morph. Furthermore, the sequence of steps can be computed in O (n log n) time.

引用

页码：1 / 34

页数：33

共 12 条

[1]

Culberson J., Rawlins G., Turtlegons: Generating simple polygons from sequences of angles, Proceedings of the 1985 Computational Geometry Symposium, pp. 305-310, (1985)

[2]

Culik K., Wood D., A note on some tree similarity measures, IPL, 15, pp. 39-42, (1982)

[3]

Goodrich M.T., Tamassia R., Dynamic ray shooting and shortest paths in planar subdivisions via balanced geodesic triangulations, J. Algorithms, 23, pp. 51-73, (1997)

[4]

Hershberger J., Suri S., A pedestrian approach to ray shooting: Shoot a ray, take a walk, J. Algorithms, 18, pp. 403-431, (1995)

[5]

Hughes J.F., Scheduled Fourier volume morphing, Proceedings of the ACM Conference on Computer Graphics, pp. 43-46, (1992)

[6]

Kaul A., Rossignac J., Solid-interpolating deformations, Proceedings of Eurographics 1991, pp. 494-505, (1991)

[7]

Sederberg T., Gao P., Wang G., Mu H., 2-D shape blending: An intrinsic solution to the vertex path problem, Computer Graphics, 27, pp. 15-18, (1993)

[8]

Sederberg T., Greenwood E., A physically based approach to 2-D shape blending, Computer Graphics, 26, pp. 25-34, (1992)

[9]

Sleator D., Tarjan R., Thurston W., Rotation distance, triangulations, and hyperbolic geometry, Proceedings of the 1986 Symposium on Theory of Computing, pp. 122-135, (1986)

[10]

Thomassen C., Deformations of planar graphs, J. Combin. Theory Ser. B, 34, pp. 244-257, (1983)

← 1 2 →