1
$\begingroup$

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.

enter image description here

$\endgroup$
2
  • 1
    $\begingroup$ After I rolled back a suggested edit to remove the graph-theory tag, I received a downvote and vote to close. It's my understanding that polygons are particular undirected graphs. If I'm wrong, fair enough; you're welcome to explain that. Otherwise I'm casting the widest net I can. $\endgroup$ Commented Mar 1, 2021 at 19:21
  • 2
    $\begingroup$ search for "generalized barycentric coordinates concave". Lots of literature, e.g core.ac.uk/download/pdf/85209106.pdf and doc.cgal.org/latest/Barycentric_coordinates_2/index.html. $\endgroup$
    – brainjam
    Commented Mar 1, 2021 at 21:18

1 Answer 1

1
$\begingroup$

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: Pentagon triangulation

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.

$\endgroup$
6
  • $\begingroup$ Thanks for the answer. This helps. I assume for cases like the example above that additional vertex could always be fixed as the centroid of the convex polygon. Once the triangulation is formed, how would one then morph between convex and concave? Like say you had triangulated the concave polygon: is there some procedure to "flip" the triangles into a concave one? $\endgroup$ Commented Mar 1, 2021 at 19:58
  • $\begingroup$ @kevinkayaks: I was wrong, in this particular case no additional vertex is needed, as the shown triangulation with just three triangles is similar for both polygons. As shown by my ineptitude, there can be a large number of valid triangulations for each polygon, and it is not always obvious if the two have a similar one. What do you mean by "flipping"? $\endgroup$
    – Glärbo
    Commented Mar 1, 2021 at 20:33
  • $\begingroup$ Actually, you can characterize a triangulation by which chords are part of it, and for a strictly convex polygon any triangulation will be valid. $\endgroup$
    – Hugo Manet
    Commented Mar 2, 2021 at 10:05
  • $\begingroup$ If you wanted such an idea full procedure would be : if one of the polygon has less vertices than the other, subdivide its sides to add vertices. Then, triangulate the nonconvex polygon. Then, build a triangulation on the convex polygon that has the same connectivity. Then, map each triangle to the corresponding triangle. But this might fail if you have to subdivide the side of the convex polygon, because then you might have degenerate triangles when trying to do that. $\endgroup$
    – Hugo Manet
    Commented Mar 2, 2021 at 10:14
  • $\begingroup$ @kevinkayaks to map a triangle into a different-shaped triangle (respecting constraints about which side goes where, so that it's coherent), the most natural way is to use an affine function. This boils down to the barycentric coordinates suggested by @ brainjam in his comment on the question, but in the simple case of a triangle. $\endgroup$
    – Hugo Manet
    Commented Mar 2, 2021 at 10:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .