Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Question

I am looking for a unique characterization of a convex polygon with $n$ vertices, relative to a feature point $p$ in the interior of the polygon. This characterization would be a vector of numbers. Suppose a polygon is described by its feature point and vertices $P=(p,v_1,\ldots,v_n)$, then the characterization function is $C(P)$ such that $C(P)=C(Q)$ if and only if $P$ is congruent* to $Q$. The most important thing I need is that for two polygons which are "almost" congruent, their characterization vectors should be "close" (like, say, small 2-norm difference). The question then is what is a simple definition of the characterization function $C(\cdot)$ which satisfies my requirements?

*Here I define congruent as identical up to rotation and translation (reflections are not allowed), cyclic permutation of vertex indices, as well as identical feature point locations. If $P$ is congruent to $Q$, then any cyclic permutation of the vertices of either polygon should still leave $C(P)=C(Q)$ (thus $C$ should be invariant to cyclic permutations of the vertices). If two polygons are congruent, then when they are overlaid, the feature points of both polygons must also match up (this is why I originally stated that the polygon is defined relative to the feature point).

An illustration of what I mean is shown below. The dots inside are the feature points of the surrounding polygon.

alt text

Things that don't work

Most characterizations of polygons usually calculate the 2x2 moment of inertial tensor relative to the center of mass of the polygon. This is not good enough because first of all, the moment tensor is not enough to completely define the shape, and second, the feature point of a polygon must also match for two congruent polygons.

Ideas

  • A vector of higher order moments relative to the feature point. (Is this unique?)
  • A vector of displacements from a regular $n$-gon vertex positions. (Does this satisfy the nearness aspect?)
share|improve this question
    
The list of distances to the vertices, and the angles determined by the segments joining your point to them. Does that work? –  Mariano Suárez-Alvarez Jan 22 '11 at 18:42
add comment

3 Answers

up vote 3 down vote accepted

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.

share|improve this answer
    
Given that the OP has apparently allowed the feature point to be any interior point in the polygon, if you add it to the polygon as a distinguished vertex, you will end up with a non-convex polygon. As a result, there may not be a unique counter clock-wise ordering of the vertices. Won't that be a problem? Alternatively, if you deal the featured point separately from the polygon, you have to choose a distinguished vertex of the polygon in such a way that you always choose equivalent vertices in congruent polygons. –  Eric Nitardy Feb 10 '11 at 14:44
    
@Eric: I would have the distinguished vertex take the place of an interior feature point, since the distinguished vertex (and preferred tracing direction) is (are) all you really need to achieve a workable correspondence between convex polygons. If it's absolutely necessary to consider a separate feature point, one could, say, append to $R(P)$ (and normalize in $C(P)$) the value $f-c$, where $f$ and $c$ are the complex numbers associated to the feature point and (average-of-vertices) centroid; such appended components would match for congruent figures, and be close for nearly-congruent ones. –  Blue Feb 10 '11 at 19:42
    
@Eric: One can actually do a decomposition of the polygon-plus-feature-point figure into "sum" of symmetric versions of that figure, as I did with polygons alone. The collection of symmetric figures is slightly different than before, however. I think you get "$\lbrace n/k \rbrace$ polygon plus origin" for $k\ne 0$, but the counterpart of $P_0$ is different, and there's a brand new component; they're the "spectral realizations" of the wheel graph. (Here's info on such realizations: daylateanddollarshort.com/math/pdfs/spectral.pdf) We then encode the shape in a complex vector as before. –  Blue Feb 10 '11 at 19:56
    
@Don: If you add the feature point as a vertex, it is arbitrary between which two vertices you put it. So you must choose a second vertex. If you treat the feature point separately, you must choose a first vertex for your polygon. Unfortunately, cyclic re-orderings of vertices change your $C(P)$. For example $P=(\sqrt{2},e^{i\frac{3\pi}{4}},e^{i\frac{5\pi}{4}})$ and $P'=(e^{i\frac{3\pi}{4}},e^{i\frac{5\pi}{4}},\sqrt{2})$ are the same polygon, but $C(P)\neq C(P')$. So either way, you need to choose a first(second) vertex in a way that you always choose equivalent vertices in congruent polygons. –  Eric Nitardy Feb 11 '11 at 4:43
    
@Eric: I don't have a complete solution to OP's question, so I'm just offering partial solutions that might be helpful. It's true that my $C(P)$(s) is (are) not invariant under cyclic permutations, which is a problem. That said, it *is* (almost-always) possible to unambiguously identify the necessary distinguished vertex: take the 1st vertex counter-clockwise from where the perimeter is met by the ray from the centroid ($c$) through the feature point ($f$). Although (again) an imperfect soln ($c = f$ isn't covered), it makes my $C(P)$ an intrinsic property, rendering cyclic re-ordering moot. –  Blue Feb 11 '11 at 7:05
show 4 more comments

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

share|improve this answer
    
I already saw that paper. It only uses the ratio of moments to characterize the overall shape, which is not unique. –  Victor Liu Jan 22 '11 at 23:05
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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