Unique characterization of convex polygons

Solution 1:

As described below, any $n$-gon is a "sum" of regular $\left\lbrace\frac{n}{k}\right\rbrace$-gons, with $k = 0, 1, 2, \cdots, n-1$. This can give rise to a vector of complex numbers that serves to characterize the shape of the polygon.

Given polygon $P$, we start by choosing a "feature point" in the form of a distinguished starting vertex, $v_0$, as well as a preferred tracing direction --in the universe of convex polygons, we can unambiguously take that direction as "always counter-clockwise"-- to get a list of successive vertices $v_0, v_1, \dots, v_{n-1}$. Write $[P]$ for the vector whose $j$-th element is the point of the Complex Plane at which the $j$-th vertex of $P$ lies.

Define the "standard regular $\left\lbrace\frac{n}{k}\right\rbrace$-gon", $P_k$, as the polygon whose $j$-th vertex coincides with the complex number $\exp\frac{2\pi i j k}{n}$. (As shapes, $P_k$ and $P_{n-k}$ (for $k \ne 0$) are identical, but they are traced in opposing directions.)

Now, any $n$-gon is the "sum" of rotated-and-scaled images of the $P_k$s, in the sense that we can write

$$[P] = r_0 [P_0] + r_1 [P_1] + \cdots + r_{n-1} [P_{n-1}]$$

with each complex $r_j$ effecting the corresponding rotation-and-scale. (Determine the $r_j$s by reading the above as $n$ component-wise equations. The solution is, clearly, unique.) Therefore, the vector $R(P) := (r_0, r_1, \dots, r_{n-1} )$ exactly encodes the polygon as a figure in the plane.

Note that, for $k > 0$, polygon $P_k$ is centered at the origin, while all the vertices of polygon $P_0$ coincide at the complex number $1$. Consequently, the $P_0$ component of the decomposition amounts to a translational element, identifying the centroid (average of vertex-points) of the figure. As we are concerned about shape without regard for position, we can suppress (or just ignore) the $r_0$ component of $R(P)$. Since a polygon's shape is independent of the figure's rotational orientation, we choose to normalize $R(P)$ by rotating the elements through an angle that would align $v_0$ with the positive-real axis, arriving at our $C(P)$:

$$C(P) := \frac{1}{\exp(i\arg{v_0})} R(P) = \frac{|v_0|}{v_0} (r_1,r_2,\dots,r_{n-1})$$

If polygons $P$ and $Q$ are congruent (with compatible distinguished vertices and tracing directions), then we have $C(P) = C(Q)$. When $P$ and $Q$ are nearly-congruent, $|C(P)-C(Q)|$ will be small, and vice-versa.

Note: When $P$ and $Q$ are similar (with compatible distinguished vertices and tracing directions), we have $\frac{C(P)}{|C(P)|} = \frac{C(Q)}{|C(Q)|}$.

Edit As noted in comments, this $C(P)$ isn't invariant under cyclic permutations of the vertices. It's worth investigating exactly what effect a cyclic permutation has.

Consider the triangle $P$ with $[P] = ( v_0, v_1, v_2 )$. The corresponding regular $P_k$ figures are given by

$$[P_0] := ( 1, 1, 1 )$$ $$[P_1] := ( 1, w, w^2 )$$ $$[P_2] := ( 1, w^2, w )$$

where $w = \exp\frac{2\pi i}{3}$.

We can easily solve the decomposition equation to get

$$R(P) = (r_0, r_1, r_2) = \frac{1}{3} \left( v_0+v_1+v_2 \;,\; v_0 + v_1 w^2 + v_2 w \;,\; v_0 + v_1 w + v_2 w^2 \right)$$

If $P'$ is identical to $P$, but with cyclically re-ordered vertices, $[P'] = ( v_1, v_2, v_0 )$, then

$$R(P') = \frac{1}{3} \left( v_1+v_2+v_0 \;,\; v_1 + v_2 w^2 + v_0 w \;,\; v_1 + v_2 w + v_0 w^2 \right) = ( r_0 \;,\; w r_1 \;,\; w^2 r_2 )$$

Observe that $w r_1 [P_1] = r_1 ( w, w^2, 1 )$ yields the same polygon as $r_1 [P_1] = r_1 ( 1, w, w^2 )$, except that its vertices have been cyclically re-ordered. Likewise for $w^2 r_2 [P_2]$ (and $w^0 r_0 [P_0]$, for that matter). The same holds for arbitrary $n$-gons.

Thus, as a family of polygonal shapes, the decomposition into regular components is independent of cyclic permutation, as is the correspondence between the vertices of the components and the vertices of the polygon. That is, in our triangles $P$ and $P'$, we have $v_0 = r_0 + r_1 + r_2$, and $v_1 = r_0 + w r_1 + w^2 r_2$, and $v_2 = r_0 + w^2 r_1 + w r_2$, regardless of where each $v_k$ appears in $[P]$ or $[P']$. Unfortunately, the $R(\cdot)$ vector doesn't suffice to capture this invariance; and $C(\cdot)$'s dependence on the distinguished vertex doesn't help matters.

$R(\cdot)$ and $C(\cdot)$ aren't entirely useless, however. The moduli, $|r_k|$, which yield the radii of the regular components, are invariants for the polygons.

Edit 2. Perhaps my $C(\cdot)$ provides a workable, comparable, characterization, after all ... with the caveat that we don't require equality between $C(P)$ and $C(Q)$ for congruent $P$ and $Q$, but, rather, an appropriate notion of equivalence.

To incorporate the feature point, we'll assume that our polygons are positioned with feature point at origin; the translational component, $P_0$, then becomes significant, so we won't suppress the corresponding element from $C(\cdot)$.

Let $r = C(P) = \frac{|u_0|}{u_0}(r_0, r_1, r_2, \dots, r_{n-1})$ and $s = C(Q) = \frac{|v_0|}{v_0} (s_0, s_1, s_2, \dots, s_{n-1})$ be two $C$-vectors with respect to starting vertices $u_0$ and $v_0$ in polygons $P$ and $Q$, respectively. Define "$r \equiv s$" iff, for all $k$ and some fixed integer $m$, we have $\frac{|v_0|}{v_0} s_k = \frac{|u_0|}{u_0} r_k w^{km}$, where $w = \exp \frac{2 \pi i}{n}$. That is, $|s_k| = |r_k|$, and $\arg(r_k) - \arg(s_k) + 2 \pi k m/n \equiv \arg(u_0) - \arg(v_0) \mod 2 \pi$. (I suspect there's a cleaner way to express this.) Then $P \cong Q$, with compatible feature points, if and only if $C(P) \equiv C(Q)$. (If we don't need feature points, we can position our polygons with their average-of-vertices centroids at the origin and suppress the $0$-th components of $C(\cdot)$.)

With this, we just need to determine the best way to measure the degree of non-equivalence for incongruent figures.

Solution 2:

Perhaps this(article about characterizing convex polygons) will help.

Solution 3:

You might explore the Fréchet Distance. In any case, here is a useful survey paper:

"Shape matching: similarity measures and algorithms," Remco C. Veltkamp
SMI '01 Proceedings of the International Conference on Shape Modeling & Applications, 2001.

And here are two references specifically on convex polygons:

"Optimal matching of convex polygons," Pedro Coxa, Henri Maitrea, Michel Minouxb and Celso Ribeiro. Pattern Recognition Letters Volume 9, Issue 5, June 1989, Pages 327-334.

"A simple algorithm for the unique characterization of convex polygons," P.K Harveya. Computers & Geosciences Volume 7, Issue 4, 1981, Pages 387-392.

(I see that the latter paper was already linked by PEV.)