Acerca de la subdivisión de aristas

[tabitaCatalan]

Subdivisión de aristas

El paper dice lo siguiente:

The step size S determines the distance a point is moved at each iteration step in the direction of the combined force that is exerted on it. Furthermore, a fixed number of simulation cycles C is performed. A specific number of iteration steps I is performed during each cycle. I0 is the number of iteration steps during the first cycle. After performing a cycle, the number of subdivision points P is doubled and the step size S is halved before initiating the next cycle. The number of iteration steps I per cycle is decreased as well.

No me queda claro cómo hacer la subdivisión.

Opción 1

Mi idea sería hacer un refinamiento de la subdivisión ya hecha, es decir, entre cada nodo intermedio agregar otro. Pros: Es muy fácil saber en qué lugar van los nuevos nodos, incluso si la arista está deformada. Contras: Los cálculos no coinciden con el paper: Si comenzamos con un nodo interior, tras subdividir agregaríamos dos nodos extra: uno a cada subarista. Tendríamos 3 nodos interiores en lugar de 2, y lo mismo pasaría en cada paso.

Opción 2

Recalcular nuevos nuevos, ignorando los ya existentes. Pros: Conserva la cuenta del paper. Contras: No hay una idea intuitiva de cómo hacerlo en las aristas deformadas. Solo les conocemos los nodos, si los desechamos tendríamos que aproximar la forma de la arista, y no parece una buena opción.

Opción 3

Cada vez que se subdivida una arista, eliminarla y crear en su lugar dos aristas hijas, usando el nodo que subdividía antes. ~Esta parece ser la forma que usaron en el código.~ Pros: Al final se tendrán los nodos interiores que dice el paper. Es fácil de ejecutar en teoría. Contras: En realidad no parece ser lo que el paper dice, no me da la impresión de que ellos estén creando más aristas.

[tabitaCatalan]

Algoritmo de subdivisión de aristas

Tras revisar el código, comprobé que la forma implementada es la opción 2, que era la que yo no sabía cómo implementar. Usaron un método que, si uno lo piensa, resulta tener bastante sentido, aunque en el código es más difícil entender qué ocurre. La idea es ubicar los nuevos nodos de manera equidistante sobre la arista deformada. Para eso se usa el siguiente algoritmo:

1. Calcular el largo de la arista deformada L.
2. Calcular el largo del nuevo segmento. Si la nueva arista tendrá P subdivisiones (nodos interiores), entonces el nuevo segmento tendrá largo s_0 = L/(P+1).
3. Enumeramos los nodos que subdividen la arista, siendo 0 el nodo source, 1 el nodo adyacente, etc.
4. Llamamos i=0, nodo_nuevo_actual al nodo source y s = s_0.
5. Comenzando desde nodo_nuevo_actual, intentar avanzar en dirección al nodo i+1 una distancia s. Hay dos opciones:
   1. Si no alcanzamos a llegar al nodo i+1: guardamos el punto donde quedamos y lo actualizamos como nuevo nodo_actual. Actualizamos s=s_0. Volver a 5.
   2. Si nos pasamos de largo del nodo i+1: guardamos la distancia que logramos avanzar l, y actualizamos s = s-l,i=i+1 (si es que aún no hemos llegado al nodo target). Volver a 5.

[tabitaCatalan]

Error del código

El problema con el código está en que en ningún momento se está guardando el nodo_actual, sino que siempre se usa el nodo i. Fue corregido en fc59441e656f1414ba913c431ea3723bd5eddf7b.

Caso test

Se agregó un caso test para verificar que está funcionando bien.

Notar que con la nueva versión del algoritmo, los nuevos nodos se ubican equiespaciados al seguir el trayecto de la arista original.

[tabitaCatalan]

Problema

Al usar el mismo caso test pero con P=4, el algoritmo solo genera 5 nodos (deberían ser P+2 nodos). Creo que esto se debe a un pequeño error de aproximación. Por fortuna, el último nodo es muy fácil de saber: es simplemente el target de la arista. Necesito agregar un nuevo test y actualizar el algoritmo.

Solución propuesta

En el while, en lugar de contar los nodos originales, hacerlo contando los nodos nuevos. El último agregarlo siempre como el target.

[tabitaCatalan]

Hice algunos cambios y parece que ahora sí obtengo buenos resultados. Basta con cambiar la condición while i < len(nodos) por una estructura de la forma do ... until, que en Python puede hacerse

finished = False
while not finished:
    ...
    finished = (number_subdiv_points == P+1)

para finalmente agregar el nodo target al final.

[tabitaCatalan]

Habían problemas al usar P_initial = 1. Aparecía un error al intentar acceder a una lista en un índice que no existía. El problema estaba en que ese caso se estaba tratando de manera diferenciada.