7
$\begingroup$

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)$?

$\endgroup$
  • $\begingroup$ The last requirement makes things very difficult, it is not even clear (to me) that the minimizing path exists (or is unique!). (I think that minimizers do not, in general, exist, even for quadrilaterals.) $\endgroup$ – Moishe Kohan Dec 25 '14 at 19:33
  • $\begingroup$ @studiosus This is why I feel like there will be more choices to make ($c$ is not unique). But you understand that there would be much much more "weird" solutions if any $c_t$ could be as big or as small as it wants. They are not very interesting. Thank you for glancing at my problem anyway :) $\endgroup$ – iago-lito Dec 25 '14 at 19:53
  • 1
    $\begingroup$ You mean to say "possibly concave", not "eventually concave". In English "eventually" means they are going to be concave if you wait long enough. $\endgroup$ – Henning Makholm Dec 25 '14 at 20:46
  • 2
    $\begingroup$ I just realized that in your last requirement you have the derivative of the area rather than area itself. Then, assuming smoothness of $A(t)$, you your integral is simply $A(1)-A(0)$. $\endgroup$ – Moishe Kohan Dec 26 '14 at 0:01
  • 1
    $\begingroup$ @Iago-lito: A physicist or geometer would use "energy" $\int_0^1 (A'(t))^2dt$ as the measure of "work" in your situation. Here $A(t)=A(c_t)$. I think, this is consistent with what you want. $\endgroup$ – Moishe Kohan Dec 26 '14 at 20:00
3
$\begingroup$

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.)


Piston


$\endgroup$
  • $\begingroup$ Amazing. This is it. So they finally achieved it with a gradient descent, and this makes their algorithm pretty much robust and flexible. I need then to find a constraint so that the area will tend to vary in a monotonic way (they focused on edges length, which I don't mind about). Did they release their C++ implementation? I couldn't find anything about it. $\endgroup$ – iago-lito Dec 26 '14 at 11:34
  • $\begingroup$ @Iago-lito: Area vs. edge-lengths are completely different, and I suspect that the fixed-edge-lengths solution illustrated above will have little import for fixed-area morphings. $\endgroup$ – Joseph O'Rourke Dec 27 '14 at 0:47
  • $\begingroup$ Too bad. But I still hope I'll find a way to project their direction D in a way that minimizes the area variation. I'll post it here then. Thanks a lot anyway for this very good reference. Maybe I'll try and contact them later if I'm still stuck. :) $\endgroup$ – iago-lito Dec 27 '14 at 8:17
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Welcome to Math.SE. I edited the answer so that it reads more of an answer than a comment. Also removed the email; it is not appropriate to include personal communication details in posts. You can put them in the user profile. $\endgroup$ – user147263 Jul 5 '15 at 23:26
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for this formalization. This already allows pretty nice transformations. I'll try and look what happens when we try to generalize to "non-convex but still star-shaped" polygons. But you're definitely right when you write that "possibly concave" will be a pain ;) $\endgroup$ – iago-lito Dec 26 '14 at 8:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.