RECTAS DIGITALES MEDIANTE EL ALGORITMO DE EUCLIDES.
GEODÉSICAS CON CONCORDANCIA DE LÍMITES EN EL PLANO.
• José Manuel Castañeda Rodríguez.
• Manuel Israel Chaves Cano.
• Pablo Manuel Enríquez Santos.
• José Luis Espino Lladonosa.
Concepto de rectas digitales
Definición de una recta digital a través del código de
cadenas. Para que una línea sea una recta digital son necesarias las condiciones siguientes:
1) Como máximo dos pendientes aparecen en la cadena, y si hay 2, difieren en 45º.
2) Al menos una de las 2 pendientes aparece en las secuencias de longitud 1.
Concepto de rectas digitales
3) La otra pendiente aparece en secuencias de al menos 2 longitudes (excepto posiblemente en los finales de arco, donde las secuencias pueden estar truncadas), y si hay dos longitudes, difieren en 1.
4) Al menos una de las 2 longitudes aparece en secuencias de longitud 1, la otra aparece en secuencias de cómo máximo de 2 longitudes (excepto en los finales) que difieren en uno.
Algoritmo de Euclides1. ENTRADA: Un pixel (u, v), con u > v > 0 y m.c.d.(u, v) = 1,
2. Sea b = v, a = u - v;
3. Sea M1 = H, M2 = D; ({H, D} es el alfabeto que usaremos)
4. Si b < a entonces
4.1 M2 = M1 + (M2)^-1;
4.2 a = a - b
4.3 Ir al paso 4
5. Si b > a entonces
5.1 M1 = M2 + (M1)^-1
5.2 b = b - a
5.3 Ir al paso 4
6. SALIDA: M2 + (M1)^-1.
Nota: La operación + denota la concatenación de cadenas de palabras del alfabeto {H, D}, y (Mx)^-1 denota la palabra Mx escrita al revés
Demostración del algoritmo
• U=51• V=11• B=11• A=40
• M1=H• M2=D
Demostración del algoritmo
• b < a• A = 29• B = 11
• M1 = H• M2 = HD
Demostración del algoritmo
• b < a• A = 18• B = 11
• M1 = H• M2 = HDH
Demostración del algoritmo
• b < a• A = 7• B = 11
• M1 = H• M2 = HHDH
Demostración del algoritmo
• b > a• A = 7• B = 4
• M1 = HHDHH• M2 = HHDH
Demostración del algoritmo
• b < a• A = 3• B = 4
• M1 = HHDHH• M2 = HHDHHHDHH
Demostración del algoritmo
• b > a• A = 3• B = 1
• M1 = HHDHHHDHHHHDHH• M2 = HHDHHHDHH
Demostración del algoritmo
• b > a• A = 2• B = 1
• M1 = HHDHHHDHHHHDHH• M2 =HHDHHHDHHHHDHHHHDHHHDHH
Demostración del algoritmo
• b > a• A = 1• B = 1
• M1 = HHDHHHDHHHHDHH• M2 =HHDHHHDHHHHDHHHHDHHHDHHHHDHHHDHHHHDHH
Restricciones del algoritmo
Coordenadas no primas entre si: la longitud total de la recta es inversamente proporcional al m.c.d. de las coordenadas u, v del punto destino.
Rectas horizontales ya que tiene que darse u > v > 0.
Rectas diagonales ( porque u = v).
Solo podemos escribir en los primeros 45º no inclusive del primer cuadrante ya que u > v.
Soluciones dadas a las restricciones
Coordenadas no primas entre si: dibujamos la recta tantas veces como el m.c.d. (calculado en a y b) de ambas coordenadas u, v.
Horizontales: Escribimos “H” u veces.
Diagonales: Escribimos “D” v veces.
Para calcular rectas de inclinación de 45º a 90º se calcula la recta con las coordenadas intercambiadas sustituyendo las “H” por “V”.
Las rectas de los cuadrantes restantes se calculan por simetría.
GeodésicasDistancia en la Superficie
Estudio y comportamiento de rectas digitales en las superficies pertenecientes a figuras en el espacio tridimensional.
Definición de distancia 4 adyacente:
D4(p,q) = |x2 – x1| + |y2 – y1|.(esta será la medida de distancia utilizada en esta práctica).
Superficies estudiadas
• Cono
• Cilindro
• Esfera
• Toro
• Banda de Möbius
• Botella de Klein
Cono
Cilindro
Esfera
Toro
Banda de Möbius
Botella de Klein
Demostración de geodésicas
Nuestra aplicación desarrolla dos actividades diferentes en las superficies presentadas:
1) Encuentra la distancia mínima entre dos
puntos en estas superficies.
2) Resolución del problema del explorador en las distintas superficies.
Bibliografía
Enlaces interesantes:
http://interactiva.matem.unam.mx/hjw/ensmat/
http://xtsunxet.usc.es/cordero/miscelanea/
http://www.math.ohio-state.edu/~fiedorow/math655/
http://www.math.harvard.edu/preceptor/surfaces/index.html
