Transform polygons into one another?

Question

I am aware that there must be no standard way to achieve this, but I don't know what has been done so far. I feel like I'm missing keywords to investigate further.

I have any two 2D polygons $a$ and $b$, possibly concave but not crossed, and they share the same barycenter.

How do I gradually transform $a$ into $b$, in a way that, for the resulting "movie" $(c_t)_{t\in[0,1]}$:

• each $c_t$ "frame of the movie" is a non-crossed polygon
• $c_0=a\ \&\ c_1 = b$
• the number of vertices in $c_t$ respects $V(a) \leqslant V(C_t) \leqslant V(b)$ (or the other way round) for any $t$
• the amount of "area adjustment" $\int_0^1{A'(t)^2\mathrm{d}t}$ is minimal, where $A'(t)$ is the derivative of the area of $c_t$ with respect to $t$. Or anything that would measure "area adjustment". The idea is that, if workers where digging material in and out to perform the transformation, they should perform the least effort. (no matter where the material is put and where it is taken out from)

I am aware that there will be discontinuities if $V(a)\neq V(b)$, but I don't mind. What I'm more interested in is: what choices will I have to make? Are there interesting results that would help me build an algorithm finding a $c$? Are there interesting readings about interpolating polygons into one another?

[UPDATE:] As suggested by Joseph O'Rourke, this is a really good reading about polygon morphing. Based on the algorithm they suggest, what constraint should I use then for the morph to let the area of $c$ vary as few as possible between $A(a)$ and $A(b)$?

Answer 1

There as been some sophisticated work on morphing without self-intersection between two rather different polygons with fixed edge lengths:

Iben, Hayley N., James F. O’Brien, and Erik D. Demaine. "Refolding planar polygons." Discrete & Computational Geometry 41.3 (2009): 444-460. (Author link.)

---

---

Answer 2

I have not seen this problem studied. In finite element implementations it is often desirable to have transformations of small order polygons from "standard" elements, but there the transformations are affine, reversible, and typically just applied to the polygon as a whole, not (as here) "gradually", i.e. in a homotopic-to-the-identity fashion.

That said, I'd like to propose a scheme for constructing the required maps based on building blocks of piecewise affine maps over a mutual triangulation of two convex polygons. A generalization to non-convex but still star-shaped regions with respect to a common "center" seems possible, yet the caveat "possibly concave but not crossed" may entail unforeseen complications.

Let convex polygons $A,B$ have a common barycenter, which without loss of generality we take to be the origin $(0,0)$. The "frame[s] of the movie" are in essence a homotopy from $id:A\to A$ to some transformation $f:A\to B$. If we restrict the mapping to the boundary of $A$, then we'd have the usual notion of a path homotopy between the boundary of $A$ and the boundary of $B$.

Since these are convex polygons, we are not concerned with "holes" in either region. The common barycenter at the origin means both regions are star-shaped with respect to the origin. The rays from the origin to vertices of both polygons will subdivide them each into a finite number of triangles with common vertex at the origin.

The triangles that cover $A$ are naturally paired with those that cover $B$, and we may consider pairs of such triangles in a periodic sequence encircling the origin in a counter clockwise direction. Taking the origin to be fixed on each triangle from $A$ allows the natural affine map to the corresponding triangle from $B$ to indeed be a linear map on that piece of the mutual triangulation, and to obtain global continuity by ensuring agreement of piecewise maps on the rays that separate contiguous triangles.

Computation with these maps would be fairly easy, given the mutual triangulation formed by those rays from the origin.

Answer 3

Maurice Aarts et al have done really good work on the implementation of the algorithm from the aforementioned paper

Iben, Hayley N., James F. O’Brien, and Erik D. Demaine. "Refolding planar polygons." Discrete & Computational Geometry 41.3 (2009): 444-460.

Quote from the site:

Refolding Planar Polygons:

This paper describes an implementation of an algorithm for the refolding of multiple polygons with a guarantee of non-intersection. The implementation builds on prior results from single polygon refolding. The intersection avoidance machinery is adapted to handle multiple polygons without introducing extra complexity.

The report is available here and the project sourcecode is available here.