Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Given an arbitrary non-convex polygon (2d) with $n$ vertices, is there any procedure by which to map it to a single convex polygon, and then back again? Maybe operating somehow on the angles between edges to map the image to the right (below) to the image to the left? If so, is there any generalization to polytopes (>2d)? Any guidance is appreciated.
If both polygons have a similar triangulation, i.e. can be decomposed to the same number of nondegenerate triangles with the same connectivity graph, then yes.
(And such mapping is trivial, as it is a set of mappings between corresponding triangles.)
Whether this is a necessary (and not just sufficient) condition, I do not know.
This extends trivially to higher dimensions. In 2D, each cell in the grid is a 2-simplex, i.e. triangle; in 3D, a 3-simplex, i.e. a tetrahedron; in 4D, a 4-simplex, i.e. a 5-cell, and so on.
In the example case, the two have a similar triangulation using three triangles, giving a trivial bijective mapping between the two:
When morphing between images, the shapes are covered by a (triangular) grid where grid vertices are at similar details, and the mapping itself is usually bicubic (using coordinates of more than one grid cell, so that grid cells are less visible in the morphed output).
Edited to describe the affine (linear) map between triangles:
An affine map between two triangles is trivial, by using barycentric coordinates $(u, v, w)$: If $\vec{p}_u$, $\vec{p}_v$, and $\vec{p}_w$ are the vertices of the triangle, then barycentric coordinates $(u, v, w)$ correspond to point $u \vec{p}_u + v \vec{p}_v + w \vec{p}_w$.
By definition, $u + v + w = 1$. Point $(u, v, w)$ is within the triangle if and only if $0 \le u \le 1$, $0 \le v \le 1$, and $0 \le w \le 1$.
Because $u + v + w = 1$ by definition, one of them (usually $w$, via $w = 1 - u - v$) is left out for simplicity.
If we have a triangle with vertex $\vec{p}_0 = (x_0 , y_0)$, and the other two vertices at $\vec{p}_u = (x_0 + x_u , y_0 + y_u)$ and $\vec{p}_v = (x_0 + x_v , y_0 + y_v)$, then $$\left\lbrace\begin{aligned} x(u, v) &= x_0 + u x_u + v x_v \\ y(u, v) &= y_0 + u y_u + v y_v \\ \end{aligned}\right. \quad \iff \quad \left\lbrace\begin{aligned} u(x, y) &= \displaystyle \frac{(x - x_0)v_y - (y - y_0)v_x}{u_x v_y - u_y v_x} \\ v(x, y) &= \displaystyle \frac{u_x (y - y_0) - u_y (x - x_0)}{u_x v_y - u_y v_x} \\ \end{aligned}\right.$$ In a computer program, you'll want to use form $$\left\lbrace\begin{aligned} u_i &= (x - X_i) A_i + (y - Y_i) B_i \\ v_i &= (x - X_i) C_i + (y - Y_i) D_i \\ \end{aligned}\right.$$ for each source triangle $i$, the correct one being the one for which $0 \le u_i \le 1$, $0 \le v_i \le 1$, $0 \le u_i + v_i \le 1$. The six constants ($X_i$, $Y_i$, $A_i$, $B_i$, $C_i$, $D_i$) are calculated from the three vertices of triangle $i$, $(x_0, y_0)$, $(x_1, y_1)$, and $(x_2, y_2)$, via $$\begin{aligned} X_i &= x_0 \\ Y_i &= y_0 \\ A_i &= \displaystyle\frac{y_2 - y_0}{(x_1 - x_0)(y_2 - y_0) - (y_1 - y_0)(x_2 - x_0)} \\ B_i &= \displaystyle\frac{x_0 - x_2}{(x_1 - x_0)(y_2 - y_0) - (y_1 - y_0)(x_2 - x_0)} \\ C_i &= \displaystyle\frac{y_0 - y_1}{(x_1 - x_0)(y_2 - y_0) - (y_1 - y_0)(x_2 - x_0)} \\ D_i &= \displaystyle\frac{x_1 - x_0}{(x_1 - x_0)(y_2 - y_0) - (y_1 - y_0)(x_2 - x_0)} \\ \end{aligned}$$ This is numerically stable and accurate with floating-point numbers (noting that it will fail for degenerate triangles, because the denominator will be zero), and fast enough to find the correct source triangle when given an arbitrary point $(x, y)$ that may or may not be inside the polygon.
When the source triangle $i$ is known, the inverse is trivial. The point corresponding to $(u, v)$ in the target triangle with vertices at $(x_0, y_0)$, $(x_1, y_1)$, $(x_2, y_2)$, is $$\left\lbrace\begin{aligned} x &= (1 - u - v) x_0 + u x_1 + v x_2 \\ y &= (1 - u - v) y_0 + u y_1 + v y_2 \\ \end{aligned}\right.$$ which is also numerically stable for points within the triangle.
Therefore, for each triangle, you'll need to store the vertex coordinates and the four helper constants, for a total of ten floating-point numbers (scalars) per triangle.
Whenever you have two corresponding triangles (no matter which is source and which target), choose the base vertex so that it is closest to a right angle in both triangles, to maximize numerical stability.
While there probably is an algorithm for obtaining a similar triangulation for two arbitrary polygons, I personally do not know it; hopefully others will pipe up and suggest some.
