¿Transformar los polígonos en uno con el otro?

Question

Soy consciente de que no debe haber ninguna forma estándar para lograr esto, pero no sé qué se ha hecho hasta ahora. Me siento como que me falta palabras clave para investigar más a fondo.

Tengo dos polígonos 2D $a$$b$, posiblemente cóncava, pero no se cruzan, y que comparten el mismo baricentro.

¿Cómo puedo transformar gradualmente $a$ a $b$, de manera que, para el resultado "de la película" $(c_t)_{t\in[0,1]}$:

• cada una de las $c_t$ "fotograma de la película" es un no-se cruzó de polígono
• $c_0=a\ \&\ c_1 = b$
• el número de vértices en $c_t$ respectos $V(a) \leqslant V(C_t) \leqslant V(b)$ (o al revés) para cualquier $t$
• la cantidad de "ajuste de la zona de" $\int_0^1{A'(t)^2\mathrm{d}t}$ es mínima, donde $A'(t)$ es la derivada de la área de $c_t$ con respecto al $t$. O cualquier cosa que pueda medir "ajuste de la zona". La idea es que, si los trabajadores donde la excavación de material y salida para realizar la transformación, se debe realizar el menor esfuerzo. (no importa donde se pone el material y donde es extraído de)

Soy consciente de que no va a ser discontinuidades si $V(a)\neq V(b)$, pero no me importa. Lo que me interesa más es: ¿qué opciones tengo que hacer? Hay resultados interesantes, que me ayudara a construir un algoritmo de búsqueda de un $c$? Hay lecturas interesantes acerca de la interpolación de los polígonos en uno con el otro?

[ACTUALIZACIÓN:] Como se sugiere por Joseph O'Rourke, esta es una muy buena lectura sobre el polígono de morphing. Basado en el algoritmo de ellos sugieren, además de la restricción debo de usar para la transición a dejar que el área de $c$ variar como pocos como sea posible entre el$A(a)$$A(b)$?

Answer 1

No ha sido algo de un sofisticado trabajo en morphing sin auto-intersección entre dos bastante diferentes polígonos con borde fijo longitudes:

Iben, Hayley N., James F. O'Brien, y Erik D. Demaine. "Replegado planas de los polígonos." Discreto Y Geometría Computacional 41.3 (2009): 444-460. (Autor del enlace.)

---

---

Answer 2

Maurice Aarts et al han hecho realmente un buen trabajo en la aplicación del algoritmo de la citada papel

Iben, Hayley N., James F. O'Brien, y Erik D. Demaine. "Replegado planas de los polígonos." Discreto Y Geometría Computacional 41.3 (2009): 444-460.

Cita de la página:

Replegamiento Plana Polígonos:

En este trabajo se describe una implementación de un algoritmo para el replegado de varios polígonos con una garantía de la no intersección. La aplicación se basa en los resultados previos de único polígono de replegamiento. La intersección de la evitación de la maquinaria está adaptado para manejar varios polígonos sin introducir una complejidad adicional.

El informe está disponible aquí y el proyecto de código fuente está disponible aquí.

Answer 3

No he visto este problema estudiado. En elementos finitos de las implementaciones es a menudo deseable tener transformaciones de la pequeña orden polígonos de "estándar" de los elementos, pero no de las transformaciones que se afín, reversible, y por lo general sólo se aplica a los polígonos como un todo, y no (como aquí) "poco a poco", es decir, en un homotópica-a-la-identidad de la moda.

Dicho esto, me gustaría proponer un esquema para la construcción de la necesaria mapas se basan en la creación de bloques de funciones definidas a trozos afín asigna a través de un mutuo triangulación de dos polígonos convexos. Una generalización para no convexa, pero todavía en forma de estrella de las regiones con respecto al común de "centro" parece posible, sin embargo, la advertencia de que "posiblemente cóncava, pero no se cruzan" puede implicar complicaciones inesperadas.

Vamos a polígonos convexos $A,B$ tiene un baricentro común, que sin pérdida de generalidad nos llevan a ser el origen $(0,0)$. El "marco" [s] de la película" son, en esencia, un homotopy de $id:A\to A$ a algún tipo de transformación $f:A\to B$. Si restringimos la asignación para el límite de $A$, entonces tendríamos la noción usual de un camino homotopy entre el límite de $A$ y el límite de $B$.

Ya que estos son polígonos convexos, no estamos preocupados con "agujeros" en la región. El baricentro común en el origen de ambas regiones son en forma de estrella con respecto al origen. Los rayos desde el origen a los vértices de ambos polígonos se subdividen cada uno de ellos en un número finito de triángulos con vértice común en el origen.

Los triángulos que cubren $A$ son naturalmente vinculado con aquellos que cubren $B$, y podemos considerar que los pares de triángulos en un periódico de la secuencia que rodea el origen en un contador a las agujas del reloj. Tomando el origen se fija en cada triángulo de $A$ permite que el natural afín mapa para el correspondiente triángulo de $B$ a ser, de hecho, una lineal mapa en que la pieza de la mutua de la triangulación, y para obtener la continuidad global asegurando acuerdo de trozos de mapas en los rayos que separan a los triángulos contiguos.

Cálculo con estos mapas, sería bastante fácil, dada la mutua triangulación formado por los rayos desde el origen.