Paper by Erik D. Demaine
- Hayley N. Iben, James F. O'Brien, and Erik D. Demaine, “Refolding Planar Polygons”, in Proceedings of the 22nd Annual ACM Symposium on Computational Geometry (SoCG 2006), Sedona, Arizona, June 5–7, 2006, pages 71–79.
This paper describes an algorithm for generating a
guaranteed-intersection-free interpolation sequence between any pair of
compatible polygons. Our algorithm builds on prior results from linkage
unfolding, and if desired it can ensure that every edge length changes
monotonically over the course of the interpolation sequence. The
computational machinery that ensures against self-intersection is independent
from a distance metric that determines the overall character of the
interpolation sequence. This decoupled approach provides a powerful control
mechanism for determining how the interpolation should appear, while still
assuring against intersection and guaranteeing termination of the algorithm.
Our algorithm also allows additional control by accommodating set of algebraic
constraints that can be weakly enforced throughout the interpolation sequence.
- See also animations of this algorithm.
- The paper is available in PDF (327k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- Refolding_DCG (Refolding Planar Polygons)
- Refolding_SIGGRAPH2004 (Refolding Planar Polygons)
- ForceLinkage_SoCG2004 (An Energy-Driven Approach to Linkage Unfolding)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated July 21, 2021 by