9 votos

Caracterización única de polígonos convexos

Pregunta

Estoy buscando una caracterización única de un polígono convexo con $n$ vértices, en relación a una característica de punto de $p$ en el interior del polígono. Esta caracterización podría ser un vector de números. Supongamos que un polígono es descrito por su función de punto y vértices $P=(p,v_1,\ldots,v_n)$, entonces la caracterización de la función es $C(P)$ tal que $C(P)=C(Q)$ si y sólo si $P$ es congruente* a $Q$. La cosa más importante que yo necesito es que para que dos polígonos que son "casi" congruentes, su caracterización vectores debe estar "cerca" (como, digamos, pequeño 2-norma de diferencia). La pregunta entonces es ¿qué es una definición sencilla de la caracterización de la función de $C(\cdot)$ que satisface mis necesidades?

*Aquí defino congruentes como idéntica a la rotación y translación (reflexiones no están permitidas), cíclico permutación de vértices de los índices, así como de idéntica característica ubicaciones de punto. Si $P$ es congruente a $Q$, entonces cualquier permutación cíclica de los vértices de polígonos todavía debe salir de $C(P)=C(Q)$ (lo $C$ deben ser invariantes a la cíclica permutaciones de los vértices). Si dos polígonos son congruentes, entonces cuando se superponen, la función de puntos de ambos polígonos también deben coincidir (esta es la razón por la que originalmente se dijo que el polígono se define en relación a la función de punto).

Una ilustración de lo que quiero decir es que se muestra a continuación. Los puntos están dentro de la función de los puntos de los alrededores del polígono.

alt text

Cosas que no funcionan

La mayoría de las caracterizaciones de los polígonos generalmente calcular el 2x2 momento de tensor de inercia con respecto al centro de masa del polígono. Esto no es suficiente, porque primero de todo, el tensor de momento no es suficiente para definir completamente la forma, y en segundo lugar, la función de punto de un polígono también deben coincidir para que dos polígonos congruentes.

Ideas

  • Un vector de orden superior momentos en relación a la función de punto. (¿Único?)
  • Un vector de desplazamientos de forma regular de las $n$-gon vértice posiciones. (¿ Esto satisface la cercanía aspecto?)

3voto

Brian Deacon Puntos 4185

Como se describe a continuación, las $n$-gon es una "suma" de regular $\left\lbrace\frac{n}{k}\right\rbrace$-ágonos, con $k = 0, 1, 2, \cdots, n-1$. Esto puede dar lugar a un vector de números complejos que sirve para caracterizar la forma del polígono.

Dado polígono $P$, se comienza por la elección de un "punto" en la forma de un distinguido a partir del vértice, $v_0$, así como el preferido para el seguimiento de dirección, en el universo de los polígonos convexos, podemos, sin ambigüedades, tomar la dirección "siempre en sentido antihorario"-- para obtener una lista de los sucesivos vértices $v_0, v_1, \dots, v_{n-1}$. Escribir $[P]$ para el vector cuyas $j$-ésimo elemento es el punto del Plano Complejo en el que el $j$-ésimo vértice de $P$ mentiras.

Definir el "estándar regular $\left\lbrace\frac{n}{k}\right\rbrace$-gon", $P_k$, como el polígono cuyas $j$-ésimo vértice coincide con el número complejo a $\exp\frac{2\pi i j k}{n}$. (Como formas, $P_k$ $P_{n-k}$ ( $k \ne 0$ ) son idénticos, pero que se trazan en direcciones opuestas.)

Ahora, cualquier $n$-gon es la "suma" de rotar y escalar imágenes de la $P_k$s, en el sentido de que podemos escribir

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

con cada complejo de $r_j$ efectuar la correspondiente rotación y escala. (Determinar el $r_j$s por la lectura de la anterior como $n$ componente sabio ecuaciones. La solución es, sin duda, única.) Por lo tanto, el vector $R(P) := (r_0, r_1, \dots, r_{n-1} )$ exactamente codifica el polígono como una figura en el plano.

Tenga en cuenta que, para $k > 0$, polígono $P_k$ está centrada en el origen, mientras que todos los vértices del polígono $P_0$ coinciden en el complejo número de $1$. En consecuencia, el $P_0$ componente de la descomposición de cantidades a una traslación de elementos, identificar el centro de gravedad (promedio de vértice puntos) de la figura. Como nos preocupa la forma sin importar su posición, se puede suprimir (o ignorar) las $r_0$ componente de $R(P)$. Desde un polígono de la forma es independiente de la figura de la orientación de rotación, que elija para normalizar $R(P)$ por la rotación de los elementos a través de un ángulo que se alinee $v_0$ con el positivo-eje real, de llegar a nuestro $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})$$

Si los polígonos $P$ $Q$ son congruentes (compatible con distinguidos vértices y seguimiento de las direcciones), luego tenemos a $C(P) = C(Q)$. Al $P$ $Q$ son casi congruentes, $|C(P)-C(Q)|$ será pequeño, y viceversa.

Nota: Al $P$ $Q$ son similares (compatible con distinguidos vértices y seguimiento de las direcciones), tenemos $\frac{C(P)}{|C(P)|} = \frac{C(Q)}{|C(Q)|}$.

Editar Como se señaló en los comentarios, esta $C(P)$ no es invariante bajo permutaciones cíclicas de los vértices. Vale la pena investigar exactamente qué efecto una permutación cíclica.

Considere el triángulo $P$$[P] = ( v_0, v_1, v_2 )$. La correspondiente regular $P_k$ cifras dadas por

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

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

Fácilmente podemos resolver la ecuación para obtener la descomposición

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

Si $P'$ es idéntica a $P$, pero con cíclicamente re-ordenados de vértices, $[P'] = ( v_1, v_2, v_0 )$, luego

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

Observar que $w r_1 [P_1] = r_1 ( w, w^2, 1 )$ de los rendimientos del mismo polígono como $r_1 [P_1] = r_1 ( 1, w, w^2 )$, excepto que sus vértices han sido cíclicamente re-ordenó. De la misma manera por $w^2 r_2 [P_2]$ (e $w^0 r_0 [P_0]$, para el caso). Lo mismo vale para los arbitraria $n$-ágonos.

Por lo tanto, como una familia de formas poligonales, la descomposición en componentes normales es independiente de permutación cíclica, como es el de la correspondencia entre los vértices de los componentes y de los vértices del polígono. Esto es, en nuestro triángulos $P$$P'$,$v_0 = r_0 + r_1 + r_2$, e $v_1 = r_0 + w r_1 + w^2 r_2$, e $v_2 = r_0 + w^2 r_1 + w r_2$, independientemente de donde cada una de las $v_k$ aparece en $[P]$ o $[P']$. Por desgracia, el $R(\cdot)$ vector no es suficiente para capturar esta invariancia; y $C(\cdot)$'s la dependencia de la distinguida vértice no ayudar a los asuntos.

$R(\cdot)$ $C(\cdot)$ no son completamente inútiles, sin embargo. Los módulos, $|r_k|$, que el rendimiento de los radios de las componentes normales, son invariantes para los polígonos.

Edición 2. Tal vez mi $C(\cdot)$ proporciona un instrumento confiable, comparable, caracterización, después de todo ... con la salvedad de que no exigimos igualdad entre $C(P)$ $C(Q)$ para congruentes $P$$Q$, sino, más bien, una adecuada noción de equivalencia.

Incorporar la característica de punto, vamos a suponer que nuestros polígonos se colocan con función de punto de origen; la traslación de componente, $P_0$, entonces se convierte en significativo, por lo que no vamos a suprimir el elemento correspondiente de $C(\cdot)$.

Deje $r = C(P) = \frac{|u_0|}{u_0}(r_0, r_1, r_2, \dots, r_{n-1})$ e $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 $P$, 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 P$, 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)$.)

Con esto, sólo tenemos que determinar la mejor manera de medir el grado de no-equivalencia para la incongruencia de las figuras.

3voto

yoliho Puntos 340

Usted puede explorar la Fréchet Distancia. En cualquier caso, aquí es una útil encuesta de papel:

"La forma de adaptación: medidas de similitud y algoritmos" Remco C. Veltkamp
SMI '01 Actas de la Conferencia Internacional sobre la Forma de Modelado Y Aplicacionesde 2001.

Y aquí hay dos referencias específicamente en polígonos convexos:

"La relación óptima entre polígonos convexos," Pedro de la Cadera, Henri Maitrea, Michel Minouxb y Celso Ribeiro. Patrón De Reconocimiento De Letras Volumen 9, Número 5, Junio De 1989, Páginas 327-334.

"Un algoritmo simple para la caracterización única de polígonos convexos," P. K Harveya. Computers & Geosciences Volumen 7, Número 4, De 1981, Páginas 387-392.

(Veo que el último documento ya fue vinculado por la PEV.)

2voto

Fionnuala Puntos 67259

Tal vez este(artículo sobre la caracterización de polígonos convexos) será de ayuda.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X