Análisis Formal de Conceptos y Aplicaciones a la Geometría Computacional

An´alisis Formal de Conceptos y Aplicaciones a la Geometr´ıa Computacional J. Constantino Benjumea Bellott An´alisis Formal de Conceptos y Aplicaciones a la Geometr´ıa Computacional J. Constantino Benjumea Bellott Memoria presentada como parte de los requisitos para la obtenci´on del t´ıtulo de Grado en Matem´aticas por la Universidad de Sevilla. Tutorizada por Prof. Fernando Sancho Caparrini ´ Indice general Agradecimientos 1 Abstract 3 Resumen 5 Acerca de 7 Presentaci´on del problema 11 I Fundamentos 17 1. Teor´ıa del Orden y Teor´ıa de Ret´ıculos 19 1.1. Teor´ıadelOrden ........................... 20 1.1.1. Definiciones Iniciales . . . . . . . . . . . . . . . . . . . . . 20 1.1.2. Principio de Dualidad . . . . . . . . . . . . . . . . . . . . 31 1.2. Teor´ıa de Ret´ıculos . . . . . . . . . . . . . . . . . . . . . . . . . . 33 1.2.1. Definiciones Iniciales . . . . . . . . . . . . . . . . . . . . . 33 ii an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa 1.2.2. Principio de Dualidad . . . . . . . . . . . . . . . . . . . . 39 1.3. FijandoIdeas ............................. 43 2. An´alisis Formal de Conceptos 45 2.1. Introducci´on.............................. 46 2.1.1. Definiciones Iniciales . . . . . . . . . . . . . . . . . . . . . 46 2.1.2. Primeros resultados . . . . . . . . . . . . . . . . . . . . . . 49 2.1.3. Pseudo-Conceptos . . . . . . . . . . . . . . . . . . . . . . . 53 2.2. Estructura reticular . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.2.1. Definiciones .......................... 56 2.2.2. Teorema B´asico . . . . . . . . . . . . . . . . . . . . . . . . 57 3. An´alisis del Ret´ıculo 63 3.1. Resultados fundamentales . . . . . . . . . . . . . . . . . . . . . . 64 3.2. M´etricas basadas en la forma . . . . . . . . . . . . . . . . . . . . 65 3.3. Complejidad Computacional . . . . . . . . . . . . . . . . . . . . . 69 3.4. Interpretabilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 4. Fundamentos de Geometr´ıa Computacional 75 4.1. Curvas................................. 76 4.1.1. Curvas de B´ezier . . . . . . . . . . . . . . . . . . . . . . . 76 4.1.2. Aproximaci´on poligonal . . . . . . . . . . . . . . . . . . . 78 4.2. Superficies............................... 81 4.2.1. Superficies de Monge . . . . . . . . . . . . . . . . . . . . . 83 ´ INDICE GENERAL iii 4.2.2. Superficies Regladas . . . . . . . . . . . . . . . . . . . . . 84 4.2.3. Superficies Multi-regladas . . . . . . . . . . . . . . . . . . 87 4.2.4. Discretizaci´on de superficies . . . . . . . . . . . . . . . . . 89 5. Implementaci´on 93 5.1. Pre´ambulo t´ecnico . . . . . . . . . . . . . . . . . . . . . . . . . . 94 5.2. TiposdeDatos ............................ 95 5.3. Pasos.................................. 97 5.4. Acotando el n´umero de pasos . . . . . . . . . . . . . . . . . . . . 99 5.5. Casopr´actico ............................. 100 5.6. Patrones................................ 106 6. An´alisis de la Curva Aproximada 107 6.1. Cota del N´umero de Iteraciones . . . . . . . . . . . . . . . . . . . 108 6.1.1. Caso pr´actico . . . . . . . . . . . . . . . . . . . . . . . . . 109 6.2. Problema del N´ Optimo ....................... 111 6.3. Complejidad de Kolmogorov . . . . . . . . . . . . . . . . . . . . . 112 6.3.1. Intuici´on............................ 112 6.3.2. Definici´on ........................... 114 6.3.3. Formalizaci´on . . . . . . . . . . . . . . . . . . . . . . . . . 115 6.4. Complejidad de Kolmogorov y N´ Optimo.............. 116 iv an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa II Aplicaciones 121 7. Experimentaci´on 123 7.1. Curvadeestudio ........................... 123 7.2. Reducci´on del n´umero de segmentos . . . . . . . . . . . . . . . . . 125 7.3. Invarianza frente a transformaciones . . . . . . . . . . . . . . . . . 126 7.3.1. Traslaciones.......................... 128 7.3.2. Rotaciones........................... 128 7.3.3. Escalado............................ 128 7.4. Preguntainicial............................ 129 8. An´alisis del C´odigo 131 8.1. Funciones relevantes . . . . . . . . . . . . . . . . . . . . . . . . . 131 8.2. Algoritmo ............................... 135 8.3. add-ondeBlender .......................... 139 9. Extensi´on a Superficies 145 9.1. Superficies Multi-regladas . . . . . . . . . . . . . . . . . . . . . . 146 9.2. Otrassuperficies ........................... 151 Conclusiones y Trabajo Futuro 157 Agradecimientos El trabajo aqu´ı presentado ha sido posible gracias a la ayuda y apoyo de muchas personas, las primeras, mi familia. En especial, la nuclear. Muchas gracias a mi madre Carla por sus sabias orientaciones. A mi padre Pepe que, sin llegar a entender del todo el contenido, me ha ayudado revisando el texto, y sus sugerencias han permitido tener una mejor presentaci´on del mismo. A mi hermana Dana, por su apoyo y ayudarme a organizar mi tiempo priorizando lo importante, a mis hermanos Fco. Manuel y Carlos que siempre han mostrado inter´es y han opinado sobre la est´etica del trabajo. Gracias a mi tutor Fernando Sancho Caparrini, por su tiempo y dedicaci´on con este trabajo, ponerme los pies en la tierra y guiarme. Quisiera agradecer a quienes han colaborado directamente: A Juan Su´arez Toribio, por la revisi´on del texto y el c´odigo de L A T EX; a Alfonso Carriazo Rubio, por sus ense˜nanzas y consejos, plasmados en la parte de geometr´ıa y su revisi´on de mis propuestas geom´etricas; a Ram´on Flores D´ıaz, por transmitirme su visi´on de las matem´aticas y de la topolog´ıa algebraica, y por haberme facilitado muchas cosas; a Jos´e Garc´ıa De Tejada Delgado, por ense˜narme que las listas de listas no son hashables en Python, y por ayudarme con los errores de c´odigo que no supe c´omo resolver; gracias a Juan Antonio ´ Alvarez Garc´ıa, por introducirme en L A T EXy ense˜narme a c´omo gestionar muchos objetivos a la vez y por apoyarme tanto. Gracias a amigos del laboratorio H1.51, Kike, V´ıctor, Marina, ´ Angel y Jos´e Lu´ıs, por preguntarme por mi trabajo y ense˜narme a citar, buscar bien la bibliograf´ıa, por salvarme y ayudarme en mis inicios con el c´odigo, por 8an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa Formal Concepts from Spatial Sensory Data” [34] y, con el fin de disponer de una herramienta utilizable en el terreno del dise˜no y poder visualizar los resultados de forma atractiva, se ha desarrollado un add-on para Blender [5] (un conjunto de herramientas de creaci´on 3D gratuita y de c´odigo abierto, con el que es posible crear visualizaciones 3D, im´agenes fijas, animaciones 3D y efectos visuales) que esperamos que sirva para mostrar las ventajas y posibles usos de este procedimien- to. A lo largo del trabajo se indicar´a c´omo se han decidido proyectar diferentes construcciones en el add-on, siempre soportadas por las definiciones matem´aticas de forma rigurosa. Al final de la segunda parte se explicar´a parte del c´odigo que implementa las funciones m´as representativas de la soluci´on, y se dar´a una idea de la estructura seguida para la construcci´on del add-on. Se debe tener en cuenta que se ha intentado mantener un equilibrio entre el rigor necesario para un TFG del Grado de Matem´aticas y el objetivo de servir de lectura introductoria para cualquier interesado en las diversas ´areas que aqu´ı hemos intentado mezclar. Esperamos que este objetivo se haya cumplido y no deje a ninguno de los posibles lectores insatisfecho. En ambas partes se tratar´an cuestiones de complejidad relacionadas con el ret´ıculo de conceptos asociado a las propiedades extra´ıdas de los objetos analizados (curvas, principalmente), y se introduce de manera intuitiva y primitiva una primera versi´on de complejidad para curvas que se basa en el proceso de construcci´on de este ret´ıculo. Queda excluido un an´alisis de la complejidad computacional de la implementaci´on del algoritmo. Adem´as, tambi´en se presentar´a una primera aproximaci´on a diferentes estrategias para extender el m´etodo propuesto en [34] para el estudio parcial de superficies. El trabajo acabar´a con un cap´ıtulo de conclusiones acerca de lo que se ha aprendido en la realizaci´on de este trabajo, y algunas ideas para un posible uso de el software desarrollado en aplicaciones de dise˜no gr´afico. Los objetivos principales que se plantearon a la hora de dise˜nar este proyecto, y que han servido de gu´ıa para su realizaci´on se pueden resumir en: Conocer y presentar los fundamentos del An´alisis Formal de Conceptos. Formalizar el trabajo “A Recursive Bateson-Inspired Model for the Genera- acerca de 9 tion of Semantic Formal Concepts from Spatial Sensory Data” [34], como medio alternativo para obtener un ret´ıculo de conceptos que caracterice curvas de forma conceptual. Crear una implementaci´on ´util del algoritmo que se da en ese trabajo. Introducirse en las posibilidades de dar una medida de complejidad de las curvas analizadas por medio del ret´ıculo que proporciona el An´alisis Formal de Conceptos. Todo este trabajo ha intentado ser autocontenido en la medida de lo posible para poder entender de forma adecuada su contenido, desde los fundamentos a su implementaci´on. Esperamos que los ejemplos que se proporcionan ayuden a una mejor comprensi´on de los contenidos presentados. Sin embargo, en algunos ejemplos, se emplear´an estructuras y objetos no definidos en este trabajo que - esperamosquedar´an debidamente referenciados para que puedan ser investigados en profundidad por el lector interesado. Acerca de Blender Debido a que Blender no es una herramienta habitual dentro del curr´ıculo de Matem´aticas, damos aqu´ı una brev´ısima explicaci´on de sus caracter´ısticas fundamentales. En el resto del trabajo lo nombraremos repetidas veces, pero no incluiremos ninguna gu´ıa ni estudio detallado acerca de su funcionamiento, uso, o caracter´ısticas adicionales ya que creemos que se aleja de los objetivos matem´aticos que han guiado este estudio. A pesar de ello, no queremos minimizar su utilidad ni restar valor al papel que ha jugado como pieza fundamental para la g´enesis y desarrollo del mismo. Blender [5] es un software de c´odigo abierto para la creaci´on de gr´aficos y animaciones en 3D. Es una herramienta muy vers´atil que se utiliza en una amplia variedad de aplicaciones, como la creaci´on de pel´ıculas animadas, efectos visuales, arte, modelado 3D, realidad virtual, impresi´on 3D, etc. A continuaci´on, se presentan algunas caracter´ısticas principales de Blender: 10 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa 1. Modelado 3D: proporciona herramientas avanzadas para modelado poligonal, esculpido, y retopolog´ıa. Los usuarios pueden crear modelos 3D detallados y precisos. 2. Animaci´on: permite la creaci´on de animaciones tanto para personajes como para objetos. Incluye sistemas de rigging, cinem´atica inversa, y herramientas de animaci´on para movimientos complejos. 3. Simulaci´on: soporta simulaciones f´ısicas como humo, fuego, fluidos, part´ıculas, cuerpos r´ıgidos y blandos, telas... 4. Renderizado: incluye varios motores de renderizado, como Cycles y Eevee. Cycles es un motor de renderizado avanzado basado en trazado de rayos, mientras que Eevee es un motor de renderizado en tiempo real. 5. Edici´on de V´ıdeo: Adem´as de sus capacidades 3D, tambi´en ofrece un editor de v´ıdeo no lineal completo, permitiendo edici´on de v´ıdeo y composici´on de efectos especiales. 6. Scripting: tiene una API de Python que permite a los usuarios automatizar tareas, crear herramientas personalizadas, y expandir la funcionalidad del software. 7. Texturizado y Pintura: ofrece herramientas para el mapeo UV, creaci´on de texturas, y pintura directamente sobre los modelos 3D. 8. Soporte para RV y RA: tambi´en puede utilizarse para crear contenido para Realidad Virtual (RV) y Realidad Aumentada (RA). Blender es conocido por su comunidad activa y sus frecuentes actualizaciones. Como es de c´odigo abierto, los usuarios pueden contribuir al desarrollo del software, mejorando continuamente sus capacidades y caracter´ısticas. Presentaci´on del problema Figura 1 La figura anterior resume nuestro problema. En principio, podr´ıa pensarse que es una pregunta sencilla si se define bien qu´e se est´a preguntando. El problema es que cuanto m´as se intenta afinar qu´e estamos preguntando, m´as dudas comienzan a aparecer, y la respuesta a la que acabamos llegando en general es un decepcionante “depende” que parece que todo el esfuerzo realizado cae ineludiblemente en el terreno del relativismo. La pregunta planteada en la figura anterior se puede proyectar en nuestra mente como: ¿representan las dos figuras una O?, ¿es 0=0?, ¿son dos circunferencias iguales? La parte de la pregunta por la igualdad no deja lugar a dudas, lo que hace dudar es en qu´e sentido se refiere. Por un lado, no son exactamente el mismo objeto (no son uno un trasladado del otro, simplemente uno a cada lado de la igualdad) pero, por otro lado, hay suficientes similitudes como para exigir una mayor rigurosidad a la hora de plantear la pregunta. 12 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa Si nos restringimos al esp´ıritu geom´etrico de la pregunta: ¿Esos dos objetos geom´etricos son iguales? Hist´oricamente, podr´ıamos ver en la evoluci´on de la Geometr´ıa un proceso de clasificaci´on que hace uso de las herramientas matem´aticas y tecnol´ogicas disponibles para decidir si dos objetos pertenecen a la misma clase de objetos. Hist´oricamente, podemos reconocer dos tipos de clasificaciones fundamentales. En la ´epoca de escuadra y comp´as, podr´ıamos hablar de clases est´aticas. Nos encontramos con clasificaciones geom´etricas basadas en el n´umero de lados del objeto (tipos de pol´ıgonos y poliedros, Fig. 2), en el an´alisis de las proporciones que se mantienen (Teorema de Thales de semejanza de tri´angulos [35]), o en las caracter´ısticas de los ´angulos que aparecen en las distintas partes del objeto (obtusos, agudos). Estos son algunos ejemplos de clasificaciones de esta geometr´ıa a la que hemos llamado est´aticas. Los libros de Euclides [17] o Apolonio [42] son ejemplos de estas primeras aproximaciones, donde el criterio de clasificaci´on de un elemento geom´etrico hace uso de ciertas medidas que puedan ser observadas con los medios (conceptuales y pr´acticos) disponibles en cada ´epoca. Avanzando en Figura 2: Clasificaci´on s´olidos plat´onicos seg´un n´umero de lados. el tiempo, nos encontramos con la generalizaci´on producida por los avances que se producen en cada una de las esquinas de la Matem´atica, como los introducidos presentaci´ on del problema 13 por el ´ Algebra [40], o avances tecnol´ogicos que proporcionan objetos reales como son los compases ajustables [33] o la imprenta [16]. Son los albores de lo que conocemos como Geometr´ıa Anal´ıtica, a la que podr´ıamos llamar, en contraposici´on a la anterior, como una geometr´ıa de clases din´amicas. La introducci´on de herramientas conceptuales matem´aticas, como las variables, y su uso para representar objetos geom´etricos, permiten pasar de entender el Teorema de Pit´agoras como una f´ormula que relaciona magnitudes a verla como una representaci´on abstracta de un objeto completo y m´as complejo como es una circunferencia. En lugar de querer descubrir el valor num´ericos de c, a partir de dos valores prefijados ayb, en a2+b2=c2, pasamos a fijar rcomo par´ametro conceptual (con significado propio) y vemos en x2+y2=r2un conjunto de puntos sobre los que podemos trabajar individualmente y colectivamente (Fig. 3). As´ı, clasificaciones cl´asicas Figura 3: Proyecci´on de un tri´angulo rect´angulo sobre c´ırculo. de objetos matem´aticos basadas en construcciones m´as o menos particulares se trasladan con el ´algebra a la forma de sus representaciones simb´olicas. De esta forma, se estableci´o la correspondencia entre las ecuaciones algebraicas y las curvas geom´etricas en un sistema de coordenadas cartesianas [15]. Ahora y=x2es el “lugar geom´etrico de todos los puntos equidistantes de un punto fijo (el foco) y una l´ınea recta fija (la directriz)” [42]. La aparici´on del C´alculo Infinitesimal lleva a su madurez a la Geometr´ıa 14 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa Anal´ıtica. De repente, aparecen nuevas formas de clasificaci´on, y el reparo griego a trabajar con el infinito alcanza su ant´ıtesis. Ahora se pueden clasificar curvas seg´un su crecimiento, seg´un si se pueden acotar, y seg´un su velocidad (la derivada, uno de los conceptos con m´as carga en el mundo de las Matem´aticas). De esta forma, a˜nadimos el cambio como criterio de clasificaci´on. Despu´es llega una etapa de generalizaci´on desmedida. Empezando por la de espacios donde estudiar los objetos geom´etricos -como con la Geometr´ıa no Euclidiana-, que permitir´ıa clasificar objetos tambi´en por el lugar donde se encuentran [22, 7, 32]. Al introducirse la Geometr´ıa Diferencial [45] se generalizan las propiedades de las superficies a trav´es de las propiedades de las variedades, y aparecen nuevas formas de medir con la introducci´on del concepto de m´etrica que nos libera de la medida f´ısica habitual (Fig. 4). En este ambiente, no pare- Figura 4: Variedades diferenciables estudiables y no estudiables con geometr´ıa eucl´ıdea. ce, pues, antinatural que aparezca la Topolog´ıa Algebraica. Herramientas como las de Topolog´ıa [39] y la Teor´ıa de Grupos [39] permiten, no s´olo generalizar presentaci´ on del problema 15 el entorno de la Geometr´ıa, sino tambi´en ampliar las nociones que normalmente estaban atadas a la idea f´ısica de superficie. Ya podemos decir que una taza y un donut son iguales [52] sin que por ello parezca que nos hemos vuelto locos o hemos cambiado el significado de igualdad de forma enga˜nosa. Formalmente, ya podemos clasificar objetos geom´etricos en base a propiedades tan naturales como su n´umero de agujeros (Fig. 5). Figura 5: Superficies homeomorfas (mismo n´umero de agujeros). Felix Klein -con su Programa de Erlangen [26]- acaba formalizando la idea de clasificaci´on geom´etrica seg´un las propiedades invariantes bajo ciertas transformaciones: en la antig¨uedad podr´ıamos encontrar las proporciones entre sus mediciones como propiedades invariantes; m´as recientemente, se puede empezar a clasificar seg´un las propiedades invariantes tras deformaciones. Volvamos ahora a la pregunta que abr´ıa nuestra presentaci´on. Siguiendo los pasos del Programa de Erlangen acotaremos nuestra pregunta y la transformamos ampliando el sentido de igualdad: ¿pertenecen esas dos figuras a la misma clase de objeto? Como vemos, seg´un en qu´e marco se pregunte, la respuesta puede ser afirmativa (si conseguimos definir una clase adecuada en la que ambas tengan cabida), 16 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa negativa (si ninguna clase donde meter a las dos nos parece adecuada) o pasa por incomparable (si ni siquiera somos capaces de encontrar clases comunes). Intuitivamente, parece que lo m´as l´ogico es pensar que bajo ciertas condiciones normales sean iguales, sean representantes de una misma clase conceptual y m´as abstracta que se puede realizar de distintas formas, al igual que podemos encontrar muchas graf´ıas diferentes de la letra “a”, pero en todas ellas percibimos sus graf´ıas como iguales. Aplicando criterios de la Geometr´ıa Cl´asica no alcanzamos esta igualdad (tal vez ni se pueden considerar elementos geom´etricos cl´asicos). Aplicando criterios anal´ıticos a las formas de los objetos de la figura 1, no ser´ıan iguales, pues las ecuaciones (si existen) que las determinan no coinciden. Tenemos otras gafas menos precisas, como la que nos regala la Topolog´ıa Algebraica, donde los objetos representados s´ı ser´ıan iguales, pero quiz´as esas gafas no son las m´as adecuadas, porque tienen un grano tan grueso que meten en la misma categor´ıa demasiadas curvas que no nos parecen iguales (una “h” no la diferencia de un “punto”). En este recorrido nos encontramos con que un criterio anal´ıtico persigue una excesiva fidelidad de detalle con el objeto concreto, mientras que el criterio del lado contrario de la habitaci´on, el de la topolog´ıa algebraica, parece que se olvida del objeto concreto y obtiene tan pocos detalles que no nos sirve. Nos hace falta un punto intermedio. As´ı pues, perseguimos aqu´ı responder a esta pregunta haciendo uso de las herramientas que nos proporciona la computaci´on y el modelado matem´atico propuesto por el An´alisis Formal de Conceptos, que permitir´a comparar diferentes objetos geom´etricos seg´un las propiedades invariantes que queramos prefijar con distinto nivel de detalle. Concretamente, la propiedad invariante vendr´a dada por la similitud entre los ret´ıculos de conceptos asociados a ciertas propiedades medibles de los objetos. La idea de esta clasificaci´on, para el caso de las curvas, fue propuesta en [34], y se basa en la noci´on de Bateson de reconocer objetos en base a sus diferencias intr´ınsecas [2], dando un algoritmo muy b´asico que usando el m´etodo de diferencias sucesivas extrae los conceptos formales de las curvas y permite un proceso de comparaci´on y clasificaci´on de las mismas. Parte I Fundamentos 24 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa Definici´on. Un subconjunto de (P, ≤) en el que cualquier par de elementos se puede comparar se llama una cadena; y si cualquier par de elementos no se puede comparar se llama una anticadena. El conjunto {1,2,4}es una cadena en (N,|), mientras que el conjunto de los n´umeros primos es una anticadena. El hecho de no ser cadena no implica ser anticadena, pues puede haber pares comparables e incomparables simult´aneamente en el mismo subconjunto de P. El conjunto {1,2,3}no es ni cadena ni anticadena en (N,|). ¿Qu´e pasa si el propio Pes una cadena en su totalidad? En ese caso, todos los elementos de (P, ≤) son comparables, esto es x≤yoy≤x, ∀x, y ∈(P, ≤).Llamamos a esto: Definici´on 1.4 (Relaci´on Orden Total). Una relaci´on binaria, R, en un conjunto Pse llama una relaci´on de orden total (o, simplemente, orden total), si satisface las siguientes condiciones para cualesquiera elementos x, y, z ∈P: 1. Reflexiva: xRx. 2. Antisim´etrica: (xRy)∧(x=y) =⇒ ¬(yRx). 3. Transitiva: (aRb)∧(bRc) =⇒aRc. 4. Total: xRy ∨yRx. Como en el orden parcial, lo habitual ser´a denotar a Rcomo ≤. Corolario 1.1.Si (P, ≤)es un conjunto totalmente ordenado, entonces para cualquier subconjunto A⊆P,(A, ≤)es un poset, es m´as, es un conjunto totalmente ordenado. Un ejemplo ya visto: 1. teor ´ ıa del orden y teor ´ ıa de ret ´ ıculos 25 (R,≤) es un orden total y, por tanto, cualquier subconjunto de Rcon el mismo orden es totalmente ordenado, por ejemplo los subposets: (N,≤), (Z,≤), (Q,≤). ¿Qu´e m´as inter´es tiene definir cadenas y anticadenas? Adem´as de ser ´utiles como categor´ıas para clasificar los distintos tipos de subconjuntos de posets, las cadenas y anticadenas permiten definir un cierto tipo de m´etrica con la que medir el tama˜no del poset. Definici´on. La anchura de un poset (P, ≤) se define como el supremo de los tama˜nos de las anticadenas que contiene: anchura(P) = sup{|A|:A⊆P, A anticadena}. De manera similar, la longitud de (P, ≤) se define como: longitud(P) = sup{|A|:A⊆P, A cadena} − 1. En la definici´on anterior, si Pes finito, los supremos se convierten en m´aximos. En la parte de Teor´ıa de Ret´ıculos veremos que los nombres de anchura y longitud tienen una interpretaci´on muy natural vistas en los ret´ıculos. Adem´as de dar una idea intuitiva del tama˜no del poset, estas m´etricas permiten saber c´omo de lejos pueden llegar a estar dos elementos comparables o incomparables. Cuando dos elementos son comparables podemos hablar de proximidad, y la magnitud de esta proximidad estar´a acotada por la longitud del poset. Esta proximidad se formaliza en la siguiente definici´on. Definici´on. Se define la distancia de proximidad de x, y ∈(P, ≤),y la denotamos como dist(x, y), como el n´umero de elementos que separan en 26 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa una cadena los dos elementos x, y que estamos comparando. Es decir, dist(x, y) := inf{|A|:A⊆P, A cadena , x, y ∈A} − 1. Por definici´on, tenemos que dist(x, y)≤longitud(P)∀x, y ∈(P, ≤). Es interesante destacar los casos extremos. Dados a, b ∈(P, ≤): Si a=b=⇒dist(a, b)=0. Si aybson incomparables =⇒dist(a, b) = −1. En el caso en que Pno sea finito, puede darse un caso curioso como en el siguiente ejemplo: Sea el poset (Q,≤), donde todo elemento es comparable, se trata de un orden total. Tenemos que ∀a, b ∈(Q,≤),con a≤b, dist(a, b) =    ∞si a=b. 0 si a=b. pues entre dos n´umeros racionales siempre podemos encontrar un elemento, como b−a 2.Este hecho es el que origina las diferentes versiones de la famosa paradoja de Zen´on [11, 1]. Una de las m´as conocidas es la de la flecha de Zen´on (Fig. 1.1). 01/2 3/4 . . . 1 Figura 1.1: Flecha de Zen´on. 1. teor ´ ıa del orden y teor ´ ıa de ret ´ ıculos 27 Definici´on. Dado un poset (P, ≤), un elemento xse dice vecino inferior de y(o, equivalentemente, yvecino superior de x), y escribimos x≺y, si (x≤y)∧∄w(x<w<y) o, equivalentemente, si dist(x, y) = 1. Observemos que esta definici´on no implica unicidad, un elemento puede tener varios, incluso infinitos, vecinos superiores o inferiores. Por otro lado, es importante resaltar que, aunque todos los elementos de un conjunto sean comparables y puedan definirse cadenas, no significa que se pueda hablar siempre de vecindad, como es el caso anterior del poset (Q,≤).Adem´as, no es necesario que Psea finito y ni siquiera que sea numerable para que existan vecinos, por ejemplo, (P(N),⊆) es un caso donde Pno es numerable y es posible hablar de vecindad. Definici´on (Diagrama de Hasse).Todo poset finito (P, ≤) puede ser representado por un diagrama de l´ıneas, o diagrama de Hasse, que da una idea visual (en forma de grafo) de las relaciones existentes. En esta representaci´on, los elementos de Pson representados por peque˜nos c´ırculos en el plano, y si x, y ∈Pcon x≤y, el c´ırculo correspondiente a yse representa por encima del c´ırculo correspondiente a x(permitiendo desplazamientos laterales), y los dos c´ırculos se unen por un segmento de l´ınea. En estos diagramas se sobreentiende la reflexividad, y la transitividad se interpreta mediante la composici´on de l´ıneas coincidentes en los c´ırculos. Algunos ejemplos de diagramas son los de la figura 1.2. A partir de estos diagramas podemos leer la relaci´on de orden de la siguiente manera: x≤y⇐⇒ el c´ırculo que representa a yse puede alcanzar mediante una l´ınea ascendente desde el c´ırculo que representa a x. La representaci´on del poset como diagramas de Hasse en Teor´ıa del Orden es igual de ´util que los diagramas de Venn [50] en Teor´ıa de Conjuntos [24], pues permiten pensar y entender la relaci´on entre elementos de manera intuitiva. 28 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa Figura 1.2: Diagramas de Hasse de hasta cuatro elementos. Las siguientes definiciones resultar´an naturales de ver observando el diagrama de Hasse de las mismas. Definici´on (L´ımite inferior/superior de A ⊆P).Sea (P, ≤) un poset y A⊆P. Diremos que p∈Pes un l´ımite inferior de Asi p≤a, ∀a∈A. Los l´ımites superiores de Ase definen de manera an´aloga. Debe indicarse que los l´ımites inferiores o superiores de un conjunto no tienen por qu´e existir, y en caso de que existan no son necesariamente elementos del conjunto. La noci´on del menor elemento queda formalizada gracias al l´ımite inferior antes mencionado. Definici´on (´ Infimo de A⊆P).Llamamos´ınfimo de Aal mayor , si existe, de todos los l´ımites inferiores de A, y se denota por ´ınf A, o VA. An´alogamente se formaliza el mayor elemento con el l´ımite superior. 1. teor ´ ıa del orden y teor ´ ıa de ret ´ ıculos 29 Definici´on (Supremo de A⊆P).Llamamos supremo de Aal menor, si existe, de todos los l´ımites superiores de A, y se denota por sup A, o WA. En la literatura, al ´ınfimo de Atambi´en se le llama meet, pues es el elemen- to com´un, por ello tambi´en se le llama m´ınimo-com´un. Se puede definir una operaci´on binaria ente dos elementos x, y ∈Pcomo x∧y= ´ınf{x, y}. An´alogamente, al supremo de Ase le llama union, o m´aximo-com´un, y de igual forma se puede definir una operaci´on binaria x∨y= sup{x, y}. Estas dos operaciones nos permitir´an entender la relaci´on de contenci´on cuando queramos ordenar dos elementos comparables en la implementaci´on del problema que se plantear´a en cap´ıtulos posteriores. Por ejemplo, el poset (P({a, b, c}),⊆) (Fig. 1.3), cuyo diagrama de Hasse (usamos flechas para ir familiarizando al lector). {a, b, c} {a, b} {a, c} {b, c} {a} {b} {c} ∅ Figura 1.3: (P({a, b, c}),⊆). Veremos lo sencillo que es identificar el supremo e´ınfimo gracias al diagrama de Hasse. •Si A1={{b},{a}}, entonces WA1={a, b}, y VA1={}. 30 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa •Si A2={{a},{a, c},{a, b},{a, b, c}}, entonces WA2={a, b, c}, y VA2={a}. Es importante resaltar que no tienen por qu´e existir ni el´ınfimo ni el supremo, como en los siguientes casos: Subconjuntos no acotados, por ejemplo, Nen (R,≤). Conjuntos cl´asicos como los usados en los cortes de Dedekind [13]: {x∈Q: x2<2}en (Q,≤). Subconjuntos Aque no tengan siquiera l´ımites superiores o inferiores, ya que pueden ser una anticadena y que ninguno de sus elementos sea comparable con otros. Por todo esto, en la siguiente secci´on nos centraremos en los ret´ıculos, estructuras en las que se puede asegurar que siempre existen el ´ınfimo y el supremo. Esta caracter´ıstica ser´a de gran utilidad en el estudio de los conceptos formales. Volvamos ahora a esa semejanza de orden que advert´ıamos en el ejemplo del inicio de este cap´ıtulo entre (B, S) y (D, U) (1.1.1). Como ya comentamos, no es raro que esa semejanza aparezca tambi´en en posets. Es decir, que entre posets se preserve el orden. Por ello, nos interesa centrarnos en aquellas aplicaciones que preserven el orden, ya que es la relaci´on entre elementos que nos interesa conservar. ¿C´omo formalizamos esta idea? ¿C´omo llamaremos a las funciones que preservan el orden? Definici´on. Una aplicaci´on φ:M−→ Nentre dos conjuntos ordenados (M, ≤) y (N, ≤) se dice que preserva el orden si ∀x, y ∈M(x≤y⇒φ(x)≤φ(y)) Si, adem´as, cumple la implicaci´on inversa, φse llama order-embedding (orden reflectante, en la traducci´on en algunos textos en espa˜nol), es decir: ∀x, y ∈M(x≤y⇔φ(x)≤φ(y)). 1. teor ´ ıa del orden y teor ´ ıa de ret ´ ıculos 31 En este caso, φes necesariamente inyectivo. Un order-embedding biyectivo se llama isomorfismo (de orden). Definido ya el isomorfismo sobre el que trabajaremos, es importante destacar que no toda aplicaci´on biyectiva que preserva el orden es un isomorfismo de orden (ya que la biyecci´on s´olo implica un emparejamiento de elementos), como muestra el ejemplo de la Fig. 1.4. {x, z, y} {x, y, z, t} {x, y} {x, y} {y, t} {y} {} {} ψ ψ ψ ψ Figura 1.4: ψelimina el elemento tde los conjuntos. Con el isomorfismo de orden identificamos elementos de distintos conjuntos manteniendo su comportamiento respecto a la estructura de orden. Para demostrar que una aplicaci´on φque ya preserva el orden es, adem´as, un isomorfismo, usualmente se demuestra comprobando si su funci´on inversa φ−1existe y tambi´en preserva el orden. Usaremos esta estrategia para demostrar el Teorema B´asico de AFC (2.1). 1.1.2 Principio de Dualidad Definir el dual es habitual en muchos estudios de matem´aticas. En nuestro caso, nos permitir´a extender muchos resultados y entender con mayor profundidad la relaci´on entre los elementos. 32 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa Definici´on. Si Res una relaci´on en M, definimos la relaci´on dual de R (o relaci´on inversa), que denotaremos R−1, como: ∀x, y ∈M: (x R−1y)⇐⇒ (y R x). En general, notaremos (M, R)d:= (M, R−1). En el caso de los posets, la relaci´on inversa ≥, de una relaci´on de orden ≤, tambi´en es una relaci´on de orden. Se llama el orden dual de ≤. Un diagrama de Hasse del poset dual, (M, ≤)d:= (M, ≥), se puede obtener a partir del diagrama de Hasse de (M, ≤) mediante una reflexi´on con eje horizontal. Definici´on. Si (M, ≤)∼ =(N, ≤)d, se dice que MyNson dualmente isomorfos. Sea P={1,2,3,5,6,15,30}y sea Q={1,7,13,77,91,143,1001}.Definiremos las relaciones: a⊢b:= aes m´ultiplo de bya|b:= a es divisor de b Es evidente que ⊢es el orden dual de |, veremos que los posets (P, |)y(Q, ⊢) son dualmente isomorfos a partir de sus diagramas de Hasse: 30 6 15 2 3 5 1 1 7 13 77 91 143 1001 1. teor ´ ıa del orden y teor ´ ıa de ret ´ ıculos 33 (P, |) (Q, |)d= (Q, ⊢) ∼ = Definimos el dual ya que al entrar en el estudio de conceptos formales, la interpretaci´on de las contenciones ser´a m´as f´acil si lo vemos desde su dual. 1.2 Teor´ıa de Ret´ıculos La Teor´ıa de Ret´ıculos es el marco te´orico que permite trabajar de manera formal los diagramas de Hasse de los posets. En lo siguiente, cambiaremos la notaci´on para precisar. Notaci´on L: Conjunto sobre el que construimos un ret´ıculo. x, y : elementos de L. X: Subconjunto de L. 1L: Elemento unitario de L. 0L: Elemento nulo de L. 1.2.1 Definiciones Iniciales Definici´on (Ret´ıculo).Un poset L:= (L, ≤) es un ret´ıculo si, para cualquier par de elementos x, y ∈L, el supremo,x∨y, y el ´ınfimo,x∧y, siempre existen. Lse dice un ret´ıculo completo si el supremo, WX, y el ´ınfimo, VX, existen para cualquier X⊆L. Si Les un ret´ıculo completo, definimos: ◦Elemento unitario de L:1L=WL. 40 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa Por dualidad, la proposici´on tambi´en se cumple para el supremo. Por tanto, como la implicaci´on contraria se da por definici´on, estamos ante una caracterizaci´on de ret´ıculos completos. M´as ejemplos de ret´ıculos: Para cada conjunto M, el conjunto potencia P(M) est´a ordenado por inclusi´on de conjuntos ⊆y (P(M),⊆) es un ret´ıculo completo. En este caso, las operaciones de ret´ıculo supremo e ´ınfimo son, respectivamente, la uni´on eintersecci´on de conjuntos. Cada intervalo real cerrado [a, b] con su orden natural forma un ret´ıculo completo ([a, b],≤) con el ´ınfimo y el supremo usuales, respectivamente, como operaciones de ret´ıculo. El poset (R,≤), por otro lado, es un ret´ıculo, pero no es completo: por ejemplo, el total no tiene elemento m´aximo y un elemento m´ınimo. A continuaci´on, tras habernos familiarizado con las estructuras que usaremos en nuestro estudio, daremos las definiciones necesarias para demostrar el Teorema B´asico de AFC (2.1) que veremos en la siguiente secci´on. Definici´on. Sea Lun ret´ıculo completo. Para cada v∈Ldefinimos: v−={x∈L|x<v}, v+={x∈L|x>v}. A partir de los l´ımites superior de v−e inferior de v+podemos definir elementos importantes de los ret´ıculos completos. Definici´on. Diremos que ves W-irreducible (supremo-irreducible) si v=Wv−, es decir, si vno puede representarse como el supremo de elementos estrictamente menores. En este caso, Wv−es el ´unico vecino inferior de v. Dualmente, diremos que ves V-irreducible (´ınfimo-irreducible) si v=Vv+. Cuando no estamos en las condiciones anteriores, diremos que ves redu- 1. teor ´ ıa del orden y teor ´ ıa de ret ´ ıculos 41 cible. En este tipo de definiciones vemos lo importante que es tener claro que el supremo de un conjunto no tiene que pertenecer al conjunto. Veamos un ejemplo gr´afico (Fig. 1.9). El elemento denotado por aes supremo-reducible, mientras que bes supremoirreducible. •Indicamos de color morado a−, y vemos que Wa−=a. •Indicamos de color verde b−, y vemos que Wb−=b. b a Figura 1.9: Ejemplo de elementos reducibles e irreducibles. Como ya dijimos, en muchos casos, dado un ret´ıculo se podr´an conocer propiedades particulares de ´este conociendo ´unicamente su representaci´on como diagrama de Hasse. Denotaremos por S(L) el conjunto de todos los elementos W-irreducibles y por I(L) el conjunto de todos los V-irreducibles. Es f´acil dar ejemplos de ret´ıculos completos que no contienen elementos ni W-irreducibles ni V-irreducibles como, por ejemplo: [0,1] ⊆R, con el orden total natural, ya que no existen vecinos superiores ni inferiores. Los vecinos superiores del elemento nulo son siempre W-irreducibles (si existen). Estos se llaman ´atomos del ret´ıculo. Los co´atomos, es decir, los vecinos 42 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa inferiores del elemento unidad, son siempre V-irreducibles. Un ret´ıculo completo en el cual cada elemento es el supremo de ´atomos se llama at´omico-reducible. (P({a, b, c}),⊆) es un ret´ıculo at´omico-reducible, es f´acil comprobarlo a partir de su diagrama (Fig. 1.3). Definici´on. Un conjunto X⊆Lse llama denso-supremo en Lsi cada elemento de Lpuede representarse como el supremo de un subconjunto de X y, dualmente, denso-´ınfimo si v=V{x∈X|v≤x}para todo v∈L. Las definiciones de denso-supremo y denso-´ınfimo pueden comprobarse f´acilmente al tener el diagrama de Hasse de un ret´ıculo. La siguiente proposici´on nos permitir´a ver en el diagrama qu´e elementos son supremo-reducibles o ´ınfimoreducibles: Proposici´on 1.2. Un elemento vde un ret´ıculo finito es , _-irreducible ⇐⇒ tiene exactamente un vecino inferior, ^-irreducible ⇐⇒ tiene exactamente un vecino superior. Todos los elementos de subconjunto denso-supremo son _-irreducibles, y todos los elementos de un subconjunto ´ınfimo-denso son ^-irreducibles. Por el contrario, en un ret´ıculo finito F, el conjunto S(F)es denso-supremo y I(V)es denso-´ınfimo. Demostraci´on. Dado v, es W-irreducible, si y solo si Wv−=v. Por otro lado, esto es equivalente a que Wv−es el mayor elemento menor que v, es decir, en particular, es el ´unico vecino inferior de v. Para los elementos V-irreducibles se concluye de manera dual. La segunda afirmaci´on de la proposici´on es trivial. La tercera se prueba inductivamente: Todo elemento vque no es W- irreducible por s´ı mismo, es el supremo de elementos estrictamente m´as peque˜nos. Si estos son supremos de elementos W-irreducibles, entonces vtam- 1. teor ´ ıa del orden y teor ´ ıa de ret ´ ıculos 43 bi´en lo es. □ Con esta proposici´on podemos ver por qu´e en los ret´ıculos lineales finitos s´olo hay elementos irreducibles. 1.3 Fijando Ideas Se propone pensar las definiciones presentadas como la generalizaci´on de conceptos del An´alisis Matem´atico en la Teor´ıa del Orden. N´otese que (R,≤) es un conjunto con orden total y sobre Cno es dif´ıcil poder definir un orden parcial a trav´es del m´odulo de sus elementos. En primer lugar, estamos trasladando las nociones topol´ogicas m´as b´asicas de espacios m´etricos, definiendo una distancia dist(·,·), a partir de la cual podemos empezar a hablar de vecindad entre elementos. Una vez hecho esto, definimos l´ımites superiores e inferiores, y nos encontramos con el mismo problema que en el an´alisis cl´asico, donde no tienen por qu´e ser ´unicos. De todos estos, nos centramos en la m´ınima cota en el caso del l´ımite superior y en la mayor cota en el caso del l´ımite inferior. Las aplicaciones que nos interesan pueden verse como una generalizaci´on de las funciones continuas, que preservan la proximidad de sus elementos. Al entrar en Teor´ıa de Ret´ıculos, nos estamos centrando en el estudio de conjuntos acotados, inferior y superiormente. En el caso de ret´ıculos completos, todo subconjunto est´a acotado. Al hablar de reducibilidad estamos hablando de convergencia, ya que v−yv+ no dejan de ser sucesiones hacia v, si ves W-irreducible estamos diciendo que no existe una sucesi´on de elementos menores que converja a v, si ves V-irreducible estamos diciendo que no existe una sucesi´on de elementos mayores que converja av. Para terminar de ver esta generalizaci´on, el mismo nombre de densidad se refiere a la noci´on hom´onima de espacios topol´ogicos. Un conjunto X⊆Lser´a 44 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa denso-supremo/denso-´ınfimo si podemos llegar a cualquier elemento v∈Lcon sucesiones v−ov+de X. Finalmente, la ´ultima proposici´on nos permite entender por qu´e la distributividad est´a relacionada con la linealidad del ret´ıculo, ya que al final se trata de la unicidad en el l´ımite. Veremos esto de nuevo en la secci´on de complejidad con las medidas de linealidad y distributividad de los ret´ıculos. 2 An´alisis Formal de Conceptos El An´alisis Formal de Conceptos (AFC, por sus siglas en ingl´es, Formal Concept Analysis) es un m´etodo interdisciplinario que se origin´o en las d´ecadas de 1960 y 1970 en los campos de la l´ogica, las matem´aticas, la psicolog´ıa cognitiva y la inform´atica, y que busca proporcionar una metodolog´ıa para derivar una jerarqu´ıa de conceptos (como una ontolog´ıa, una red de datos que define las relaciones existentes entre los conceptos de un dominio o ´area del conocimiento) a partir de una colecci´on de objetos y las propiedades que verifican. Cada concepto de la jerarqu´ıa obtenida representa, simult´aneamente, un conjunto de objetos que comparten los mismos valores para cierto conjunto de propiedades, y dicho conjunto de propiedades. Su desarrollo inicial se atribuye a los trabajos pioneros de Rudolf Wille y su colaborador Berhard Ganter en la Universidad T´ecnica de Darmstadt, en Alemania[21]. Para la elaboraci´on de esta memoria se ha decidido seguir directamente el trabajo de los autores originales introduciendo algunos cambios que presentan autores posteriores. El AFC es un m´etodo id´oneo para el an´alisis de datos con aplicaciones en los campos de Inteligencia Artificial, Miner´ıa de Datos y Recuperaci´on de Informaci´on en distintos ´ambitos. El AFC se utiliza para explorar estructuras de datos complejas, identificar patrones, clasificar informaci´on y descubrir conocimiento impl´ıcito en conjuntos de datos, y se ha mostrado especialmente ´util en la organizaci´on y comprensi´on de grandes vol´umenes de informaci´on en diversas disciplinas, como la Biolog´ıa, la Sociolog´ıa, la Ling¨u´ıstica y la Ingenier´ıa. Ser´a la herramienta que usaremos para poder comparar y clasificar nuestros elementos geom´etricos en cap´ıtulos posteriores. 46 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa Se basa en la Teor´ıa de Conjuntos y usa resultados de la Teor´ıa de Ret´ıculos, que presentamos en la secci´on anterior, para analizar relaciones entre conjuntos de objetos y atributos. Notaci´on G: Conjunto de objetos. M: Conjunto de atributos. I: Relaci´on de incidencia. K: Contexto formal (G, M, I). L(K) : Ret´ıculo de conceptos de K. C= (A, B): Concepto formal de L(K) con A⊆GyB⊆M. 2.1 Introducci´on 2.1.1 Definiciones Iniciales ¿Por d´onde empezar para entrar en contexto? Empecemos con el marco de trabajo de los conceptos formales, el contexto formal. Sobre esta estructura posteriormente estableceremos una relaci´on de orden parcial para poder dotarla de estructura de poset y poder utilizar la Teor´ıa de Ret´ıculos anteriormente introducida. Definici´on (Contexto Formal).Un contexto formal K= (G, M, I) consiste en dos conjuntos GyM, y una relaci´on Ientre GyM(llamada tambi´en relaci´on de incidencia de K). Los elementos de Gse llaman objetos y los elementos de Mse llaman atributos del contexto. La notaci´on gIm, ´o (g, m)∈I, se interpreta como “el objeto gtiene el atributo m”. Como antes, cuando (g, m)/∈Ilo podemos escribir como g  Im. Los contextos formales suelen representarse mediante su tabla de incidencias, que no deja de ser una matriz binaria donde las filas representan los objetos, las 2. an´ alisis formal de conceptos 47 columnas los atributos, y un 1 en una posici´on representa que la fila y la columna correspondientes est´an relacionadas, por lo que existe ese par como elemento del contexto formal, y 0 en caso contrario. En el ´ambito de AFC es com´un representar estas tablas usando el s´ımbolo ×para representar 1 y su ausencia (el espacio en blanco) para representar 0. La Tabla 2.1 representa la misma informaci´on que el contexto formal de la Fig. 2.1). Par Impar Primo Compuesto Cuadrado Perfecto 0× × 1× × × 2× × . . .. . .. . .. . .. . .. . .. . . 8× × 9× × × 10 × × Cuadro 2.1: Tabla de incidencias de n´umeros naturales y algunas propiedades              1 0 0 0 1 0 0 1 0 0 1 1 1 0 1 0 0 0 . . .. . .. . .. . .. . .. . . 1 0 0 1 0 0 0 1 0 1 1 0 1 0 0 1 0 0              Figura 2.1: Matriz de Incidencias de la tabla 2.1 Definiremos ahora una operaci´on fundamental en el AFC que permitir´a, dado un objeto, conocer qu´e atributos posee, y dado un atributo, conocer qu´e objetos lo poseen: 48 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa Definici´on (Operaci´on Derivaci´on).Para A⊆G, definimos A′:= {m∈M|(g, m)∈Ipara todo g∈A} De forma similar, para B⊆M, definimos B′:= {g∈G|(g, m)∈Ipara todo m∈B}. Estos operadores se llaman operadores de derivaci´on uoperadores formadores de conceptos para el contexto K= (G, M, I). Es decir, A′es el conjunto de atributos que comparten los objetos de A, mientras que B′son los objetos que tienen todos los atributos de B. En nuestro problema, estas operaciones nos permiten elegir un segmento, o conjunto de segmentos, de una curva y ver sus atributos, y, simult´aneamente, dado un atributo, o conjunto de atributos que describen propiedades de la curva, ver qu´e intervalos de la curva lo poseen. Estamos ya en disposici´on de definir los objetos que queremos comparar al estudiar los objetos geom´etricos y sobre los que impondremos nuestra relaci´on de orden: Definici´on (Concepto Formal).Un concepto formal de un contexto formal K= (G, M, I) es un par (A, B) con A⊆G,B⊆M, verificando A′=B yB′=A. Son las condiciones A′=ByB′=Alo que termina de formalizar la idea de conceptos como un par de (objetos, atributos) Esta definici´on establece que cada concepto formal tiene dos partes, a saber, su extensi´on y su intensi´on. Esto sigue una antigua tradici´on de la L´ogica de Port Royal (1662), y est´a en l´ınea con la Norma Internacional ISO 704 que formula la siguiente definici´on: “Se considera que un concepto es una unidad de pensamiento constituida por dos partes: su extensi´on y su intenci´on.” 2. an´ alisis formal de conceptos 49 Definici´on (Extensi´on e intensi´on).Los conjuntos AyBse llaman la extensi´on (extent) y la intensi´on (intent) del concepto formal (A, B), respectivamente. El conjunto de todos los extents de (G, M, I) a veces se denota como U(G, M, I). La letra Use utiliza posiblemente como una abreviatura de Universum. Para el conjunto de todos los intents escribimos J(G, M, I).La letra Jpodr´ıa estar relacionada con la idea de “conjunto” o “join”, ya que en AFC se analizan las relaciones de inclusi´on entre los conjuntos de atributos (intents) y los conjuntos de objetos (extents). En su representaci´on como tabla, los elementos de U(G, M, I) y de J(G, M, I) son subconjuntos de las filas y columnas de ´esta. Los conceptos formales son subconjuntos de K. 2.1.2 Primeros resultados Vamos a analizar algunas propiedades de la operaci´on de derivaci´on. Su comportamiento recuerda al de las reglas de De Morgan [12]: Proposici´on 2.1 (Propiedades Derivaci´on).Sea (G, M, I)un contexto formal. Si A, A1, A2⊆GyB, B1, B2⊆Mentonces: 1. A1⊆A2⇒A′ 2⊆A′ 1 2. A⊆A′′ 3. A′=A′′′ (por lo tanto, A′′′′ = A′′) 4. (A1∪A2)′=A′ 1∩A′ 2 1’. B1⊆B2⇒B′ 2⊆B′ 1 2’. B⊆B′′ 3’. B′=B′′′ (por lo tanto, B′′ = B′′′′) 4’. (B1∪B2)′=B′ 1∩B′ 2 5. A ⊆B′⇔B⊆A′⇔A×B⊆I 56 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa 2.2.1 Definiciones Definici´on (Subconceptos y superconceptos).Dados dos conceptos (A1, B1) y (A2, B2) de un contexto K, la relaci´on subconcepto-superconcepto se define como (A1, B1)≤(A2, B2) si y solo si A1⊆A2(equiv. B2⊆B1). N´otese que el orden de contenci´on permitir´a entender su ret´ıculo asociado al leerlo de arriba a abajo como contenciones de atributos y de abajo a arriba como contenciones de objetos, es decir, el dual (2.2.2). Esto solo es posible gracias a las condiciones A′=ByB′=Aque definen a los conceptos formales. Definici´on. El conjunto de todos los conceptos formales de un contexto K= (G, M, I) junto con la relaci´on de orden ≤forma un ret´ıculo completo, llamado ret´ıculo de conceptos de K, y se denota por L(K). Dada una tabla de incidencias de Kpodemos obtener L(K), pero al rev´es no, ya que no todos los elementos de Kson conceptos formales. Es sencillo comprobarlo, ya que a una tabla de incidencias podr´ıamos a˜nadir columnas redundantes con las anteriores o sus complementarias y seguir´ıamos obteniendo el mismo ret´ıculo de conceptos. ¿Qu´e clase de ret´ıculo es L(K)?¿Tiene algo de especial este ret´ıculo frente a otros? Responder a estas preguntas forma parte del Teorema B´asico del AFC 2.1. Pero antes de poder responderlas habr´a que seguir proyectando las nociones adquiridas de Teor´ıa de Ret´ıculos a este caso en particular. Como vimos en la secci´on dedicada a ret´ıculos (1.1.1), se pueden definir su meet y su union como operadores entre conceptos. ´ Estos vienen dados por: Definici´on. Para cada par de conceptos formales (A1, B1) y (A2, B2) de un cierto contexto formal, su supremo se define como: (A1, B1)∧(A2, B2)=(A1∩A2,(B1∪B2)′′). 2. an´ alisis formal de conceptos 57 Por la proposici´on anterior vemos que se trata de un concepto, pues es (B1∪ B2)′,(B1∪B2)′′). El ´ınfimo de (A1, B1) y (A2, B2) se define como: (A1, B1)∨(A2, B2) = ((A1∪A2)′′, B1∩B2). Razonando de manera equivalente vemos que se trata de un concepto. Como dijimos, para dar una idea m´as intuitiva, hagamos una analog´ıa con los n´umeros enteros y su m´aximo com´un divisor y su m´ınimo com´un m´ultiplo. Hablar de supremo es hablar de “m´aximo com´un subconcepto”, y hablar de ´ınfimo en lugar de “m´ınimo com´un superconcepto”. Es f´acil ver que son el supremo y m´ınimo del ret´ıculo de conceptos por ser la intersecci´on de los extents y de los intents respectivamente. Veremos una generalizaci´on del supremo e ´ınfimo para cualquier conjunto de ´ındices de Ken la demostraci´on del Teorema B´asico 2.1. 2.2.2 Teorema B´asico El Teorema B´asico del An´alisis Formal de Conceptos que veremos a continuaci´on define no solo el supremo e ´ınfimo de conjuntos arbitrarios de conceptos, tambi´en responde la pregunta de si los ret´ıculos de conceptos tienen alguna propiedad especial. De hecho, la respuesta es “no” ya que cada ret´ıculo de conceptos es (isomorfo a alg´un) ret´ıculo completo. Es decir, se puede componer un contexto formal K= (G, M, I) de tal manera que el ret´ıculo completo original sea isomorfo a L(K).Aunque el teorema no responde c´omo se puede construir dicho contexto, sino que describe todas las posibilidades para hacerlo. Teorema 2.1.Teorema B´asico del An´alisis Formal de Conceptos ([Wille 1982],[Ganter, Wille 1996]) Si K= (G, M, I)es un contexto formal, entonces el ret´ıculo de concep- 58 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa tos L(K)es un ret´ıculo completo. Para conjuntos arbitrarios de conceptos formales: {(Aj, Bj)|j∈J} ⊆ L(K) su ´ınfimo y supremo se dan de la siguiente manera: ^ j∈J (Aj, Bj)=(\ j∈J Aj,([ j∈J Bj)′′), _ j∈J (Aj, Bj) = (([ j∈J Aj)′′,\ j∈J Bj). Adem´as, un ret´ıculo completo V, es isomorfo a un ret´ıculo L(K)si y solo si existen funciones γ:G→Vyµ:M→Vtales que γ(G)es denso-supremo en L,µ(M)es denso-´ınfimo en V, y gIm es equivalente a γg ≤µm para todo g∈Gy todo m∈M. En particular, Ves isomorfo a L(V, V, ≤). Demostraci´on. En primer lugar, veamos la f´ormula del ´ınfimo. Siendo Aj= B′ jpara cada j∈J, (\ j∈J Aj,([ j∈J Bj)′′), por la proposici´on anterior podemos transformarlo en : (([ j∈J Bj)′,([ j∈J Bj)′′), es decir, tiene la forma (X′, X′′) por lo que es un concepto. Que esto s´olo puede ser el ´ınfimo, es decir, el m´aximo-com´un-subconcepto de los conceptos (Aj, Bj), se sigue inmediatamente del hecho de que la extensi´on de este concepto es exactamente la intersecci´on de los extents de (Aj, Bj).La f´ormula para el supremo se justifica de manera an´aloga. As´ı, adem´as de demostrar las f´ormulas hemos demostrado que L(G, M, I) es un ret´ıculo completo. Ahora probamos, primero para el caso especial V=L(G, M, I), la existencia de las aplicaciones γyµcon las propiedades deseadas. Centr´emonos 2. an´ alisis formal de conceptos 59 en un concepto concreto (A, B).Definimos γ(g) := ({g}′′,{g}′) para g∈G, µ(m) := ({m}′,{m}′′) para m∈M. Elegimos la notaci´on γpara denotar a la funci´on generadora de conceptos a partir de los elementos de Gyµpara los de M. Es decir, γ(g) es el m´ınimo concepto que se puede generar con g∈Gyµ(m) es el m´ınimo concepto que se puede generar con m∈M. Como se ha afirmado, tenemos γ(g)≤µ(m) ⇔ {g}′′ ⊆ {m}′⇔ {m}⊆{g}′⇔m∈ {g}′⇔gIm. As´ı, por las f´ormulas probadas anteriormente, _ g∈A ({g}′′,{g′})=(A, B) = ^ m∈B ({m}′,{m}′′), para cada concepto (A, B), es decir, γ(G) es denso-supremo y µ(M) es denso-´ınfimo en L(G, M, I).M´as generalmente, si V∼ =L(G, M, I) y φ: L(G, M, I)→Ves un isomorfismo de ret´ıculos completos, definimos γyµ por γ(g) := φ({g}′′,{g}′) para g∈G, µ(m) := φ({m}′,{m}′′) para m∈M. Las propiedades exigidas para estas aplicaciones se demuestran de manera similar al caso anterior. Si Ves un ret´ıculo completo y γ:G→V, µ :M→V son aplicaciones con las propiedades indicadas anteriormente, entonces definimos φ:L(G, M, I)→Vpor φ(A, B) := _{γg |g∈A}. 60 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa Evidentemente, φpreserva el orden. Siguiendo la estrategia comentada anteriormente (1.1.1), para probar que φes un isomorfismo, tenemos que demostrar que φ−1existe y tambi´en preserva el orden. Por lo tanto, definimos ψx := ({g∈G|γg ≤x},{m∈M|x≤µm}), para x∈Vy demostramos que ψx es un concepto de (G, M, I): h∈ {g∈G|γg ≤x} ⇔ γh ≤x ⇔γh ≤µn para todo n∈ {m∈M|x≤µm} ⇔hIn para todo n∈ {m∈M|x≤µm} ⇔h∈ {m∈M|x≤µm}′. La segunda condici´on sigue de manera correspondiente. Hemos definido ψ: V→L(G, M, I), y podemos ver directamente desde la definici´on que ψ preserva el orden, pues si x≤yen Ventonces ψ(x)≤ψ(y) , es decir, pues {g∈G|γg ≤x}⊆{g∈G|γg ≤y} y {m∈M|y≤µm}⊆{m∈M|x≤µm} Ahora probemos que la funci´on definida es la inversa buscada, es decir, φ= ψ−1.Tenemos φψx =_{γg |g∈G, γg ≤x}=x, ya que γ(G) es denso-supremo en V.Por otro lado, φ(A, B) = V{µm |m∈ B}, ya que µ(M) es denso-´ınfimo en V, y por lo tanto ψφ(A, B) = ψ^{µm |m∈B} ={g∈G|γg ≤^{µm |m∈B}},{. . .}′ = ({g∈G|γg ≤µm para todo m∈B},{. . .}′) = ({g∈G|gIm para todo m∈B},{. . .}′) = (B′, B′′)=(A, B). 2. an´ alisis formal de conceptos 61 Por lo que φ=ψ−1.Si elegimos para un ret´ıculo completo Vespec´ıficamente G:= V, M := V, I :=≤con γas´ı como µcomo la identidad de V, obtenemos V∼ =L(G, M, I). □ El lector interesado puede consultar el libro de Ganter&Wille sobre AFC [19] para m´as detalles y ejemplos. Las aplicaciones γyµque aparecen en el Teorema B´asico indican c´omo se puede identificar el contexto en el ret´ıculo de conceptos. Esto se consigue con la siguiente definici´on, caso particular de la derivaci´on: Definici´on. Para un objeto g∈G, escribimos g′:= {m∈M|gIm}en lugar de {g}′para el intent del objeto g. Correspondientemente, m′:= {g∈G|gIm}es el extent del atributo m. Manteniendo los s´ımbolos utilizados en el Teorema B´asico, escribimos γg para el concepto de objeto (g′′, g′) y µm para el concepto de atributo (m′, m′′). Como L(K) es un ret´ıculo completo, si nos centramos s´olo en los intents, podemos definir el ret´ıculo de intents LI=L(J(K)) que hereda la estructura anterior y se trata de un ret´ıculo completo. Centrarnos en LInos permitir´a estudiar la complejidad de L(K). Al centrarnos en los intents, diremos que dos conceptos formales, (A1, B1), (A2, B2) de dos ret´ıculos de conceptos isomorfos mediante φ, son iguales si : A1= φ(A2) y B1=B2.Por extensi´on, diremos que ambos ret´ıculos son el mismo, pues s´olo cambian los extents. Principio de Dualidad para Ret´ıculos de Conceptos Sea (G, M, I) un contexto. Entonces (M, G, I−1) tambi´en es un contexto, de hecho, L(M, G, I−1)∼ =L(G, M, I)d, 62 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa y (B, A)7−→ (A, B) es un isomorfismo. Es f´acil ver que es biyectiva, preserva el orden y order-embedding pues la relaci´on gIm pasa a ser mI−1g. En otras palabras: si intercambiamos los roles de los objetos y los atributos, obtenemos su ret´ıculo de conceptos dual. As´ı, el Principio de Dualidad se extiende a los ret´ıculos de conceptos. 3 An´alisis del Ret´ıculo La Complejidad Algor´ıtmica estudia las t´ecnicas que permiten ponderar la cantidad de recursos (entre otros, temporales) que necesita un algoritmo para resolver un problema, dando de esa forma una medida de la eficiencia de dicho algoritmo. Cuando el algoritmo est´a dise˜nado para resolver el problema en una variedad de instancias posibles, es habitual que los recursos necesarios dependan de las caracter´ısticas de cada instancia concreta (que pasar´ıa a ser el dato de entrada al algoritmo). En nuestro caso, nos interesa conocer cu´an complicado es crear el ret´ıculo de conceptos a partir de los elementos del contexto. Para ello, veremos distintas aproximaciones al problema. Por otro lado, una vez creado el ret´ıculo, aparece una nueva complicaci´on, que es la de interpretar los datos obtenidos. Entenderemos como “interpretable” dentro de un ret´ıculo, a entender c´omo se relacionan los elementos ordenados en t´erminos de su significado o interpretaci´on dentro de esa estructura. Notaci´on Elementos de AFC K: Contexto formal (G, M, I). L(K) : Ret´ıculo de conceptos de K. LI: Ret´ıculo de intents de K. C= (A, B): Concepto formal de L(K) con A⊆GyB⊆M. |X|: N´umero de elementos del conjunto X. 64 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa 3.1 Resultados fundamentales El tama˜no del ret´ıculo L(K) es un factor clave en el an´alisis de costos de los algoritmos de AFC. Debido a la compleja relaci´on entre el tama˜no del ret´ıculo L(K) y los par´ametros del contexto K, no existe una aproximaci´on simple y eficiente para determinar el n´umero total de conceptos K[28]. Sin embargo, como veremos, se han presentado propuestas que nos permitir´an entender mejor la complejidad del ret´ıculo L(K). La primera aproximaci´on natural es intentar acotar el n´umero de conceptos a partir de la relaci´on de incidencia, I. Para ello, denotaremos por: DEN(K) : el n´umero promedio de atributos relacionados con un objeto arbitrario (densidad del contexto), K: n´umero de conceptos generados. El primer resultado relacionado fue presentado por Ganter y Wille en [20], mostrando que el tama˜no de L(K) puede aumentar exponencialmente en los par´ametros |G|y|M|. Adem´as de los par´ametros |G|y|M|, tambi´en la densidad del contexto DEN(K) juega un papel importante en el an´alisis de la complejidad: “Un contexto con valores grandes de |G|y|M|, pero con un Idisperso, produce un conjunto de conceptos peque˜no” [30]. Idisperso significa que hay pocos elementos relacionados, es decir, que |I|es peque˜no, que se puede comprobar por medio de la matriz del contexto, que debe ser dispersa. Uno de los primeros resultados anal´ıticos en contar los conceptos se puede encontrar en la tesis doctoral de Sch¨utt [47]. El trabajo proporciona la siguiente cota superior para el valor de K: Proposici´on 3.1 (Cota n´umero de conceptos).La cota del n´umero de con- 3. an´ alisis del ret ´ ıculo 65 ceptos Kcuando |I|>2: K≤3 2p2|I|+1 −1. M´as tarde, Kuznetsov demostr´o que el algoritmo de c´alculo para el n´umero total de conceptos pertenece a la clase de problemas NP-completos [30, 29]. Aunque no vamos a entrar aqu´ı en las definiciones y resultados b´asicos de la Teor´ıa de la Complejidad, recordemos que un problema est´a en la clase NP si puede ser resuelto en tiempo polinomial por una m´aquina no determinista. Es decir, si se da una soluci´on, se puede comprobar que esta soluci´on es correcta en un tiempo polinomial respecto al tama˜no de la entrada [44]. La propuesta del algoritmo [34] que veremos m´as adelante permite reducir los costes de la generaci´on de conceptos asociados a una curva mediante un proceso de limpieza iterativo previo a la generaci´on del ret´ıculo de conceptos (5.3). As´ı, aunque veremos que, bajo ciertas condiciones, puede ser m´as eficiente que los algoritmos de construcci´on generales, es simplemente por el hecho de que est´a trabajando en unas condiciones m´as restrictivas y simplificadas. 3.2 M´etricas basadas en la forma Por su parte, Kuznetsov propone entonces estudiar la complejidad del ret´ıculo en base a su forma. Como mencionamos en secciones anteriores, la forma del ret´ıculo puede aportar mucha informaci´on acerca de ´este, en particular, acerca de su complejidad. Muchas veces ser´a igual de ´util saber qu´e tipo de forma no tiene para saber qu´e complejidad no tiene. Ante esta problem´atica, para medir la “complejidad del ret´ıculo” Kuznetsov propone dos medidas relacionadas con la linealidad ydistributividad del ret´ıculo [9]. De esta forma, Kuznetsov presenta estas dos formas alternativas de definir la complejidad de un conjunto de datos y c´omo pueden medirse en el ret´ıculo de conceptos relacionado que puede computarse a partir de este conjunto de datos. 72 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa Entonces, obtenemos el mismo factor O(|G| × |M|), como en el caso de calcular nuestros ´ındices de distributividad DIST y NL.DIST, y podemos decir que calcular los ´ındices de distributividad seg´un nuestras definiciones en tiempo O(K2× |G|×|M|) puede ser mucho m´as r´apido en la pr´actica que calcular el ´ındice de distributividad en tiempo O(K3× |G|×|M|) [9]. 3.4 Interpretabilidad Interpretar datos, ir´onicamente, es una expresi´on muy interpretable. En esta parte hablaremos de ciertas ideas desde un punto de vista intuitivo, sin llegar a pretender dar una aproximaci´on formal. Entenderemos como “interpretable” dentro de un ret´ıculo, a entender c´omo se relacionan los elementos ordenados en t´erminos de su significado o interpretaci´on dentro de esa estructura. La interpretabilidad de cualquier an´alisis de datos es una de las prioridades de las personas investigadoras al hacer cualquier estudio. Con ella se puede tener nociones intuitivas que permiten trabajar m´as r´apidamente, ya que, de ser una interpretaci´on v´alida (usamos “v´alida” en el lenguaje de la l´ogica formal), se conoce con mayor profundidad las entidades de estudio. Decimos “interpretaci´on v´alida”, ya que no toda interpretaci´on mantiene la coherencia con el verdadero comportamiento de las entidades de estudio. Por ello, la otra cara de la gran ventaja que supone tener una interpretaci´on adecuada es que es dif´ıcil dar con una, y en general, no saber -a´un teni´endola- si es la m´as adecuada. Ese es el esp´ıritu de la investigaci´on cient´ıfica, construir modelos para poder buscar “contraejemplos” y volver a construir modelos m´as generales que expliquen ese “contraejemplo”, un proceso central en la metodolog´ıa de Karl Popper[1902- 1994] para construir y refinar teor´ıas cient´ıficas [43]. Los ´ındices antes presentados permiten conocer c´omo se relacionar´an los elementos del ret´ıculo, en promedio. El ´ındice de linealidad nos da mucha informaci´on de la comparabilidad global 3. an´ alisis del ret ´ ıculo 73 de los atributos. Sin embargo, este ´ındice no mide directamente qu´e tan bien interpretable es el ret´ıculo. Una de las principales propiedades de interpretabilidad es el tama˜no de algunos conjuntos particulares, como el tama˜no y la estructura de la base de implicaci´on, la base de Duquenne-Guigues. Entonces, la estructura m´as simple que soporta la base de implicaci´on se puede encontrar en ret´ıculos distributivos. En consecuencia, el “´ındice de distributividad” mide qu´e tan cercano est´a un ret´ıculo de ser un ret´ıculo distributivo. En nuestro caso, si consideramos la interpretabilidad del ret´ıculo, usaremos la noci´on de Buzmakov de patr´on. Donde, la expresi´on patr´on se refiere a subconjuntos interesantes de atributos en un sentido amplio [9]. Es decir, un patr´on ser´a un conjunto de atributos a los que dotaremos de contenido sem´antico (interesantes “a priori”) o ser´an interesantes tras ver sus relaciones en el ret´ıculo (interesantes “a posteriori”). Entonces, el tama˜no de los patrones a interpretar y su n´umero son definitivamente elementos importantes a tener en cuenta. Estos patrones pueden coincidir o no con intents, ya que son conjuntos interesantes dependientes de la subjetividad de quienes est´en investigando. “En un caso ideal, se prefiere un peque˜no n´umero de patrones (interesantes) para facilitar la interpretaci´on, y su distribuci´on determina la forma que adquirir´a el ret´ıculo final. De hecho, un peque˜no n´umero de reglas con pocos atributos en las premisas y en las conclusiones es m´as sencillo de interpretar que cientos de reglas con m´as de diez atributos en las premisas y conclusiones. Por lo tanto, es natural estudiar c´omo se distribuye el n´umero de patrones con respecto a su tama˜no. En la mayor´ıa de los casos, un gran n´umero de patrones est´a asociado con la complejidad computacional. Entonces, controlar el tama˜no y el n´umero de patrones es tambi´en una forma de controlar la complejidad computacional” [9]. Como comentamos anteriormente, esa interpretabilidad se consigue con las bases DG y los pseudo-intents.“Los pseudo-intents son las premisas en las implicaciones usando las bases DG” [9]. Adem´as, es m´as f´acil estudiar patrones interesantes con pseudo-intents que con intents, ya que estos primeros son elegibles seg´un interese, sin dejar de tener relaci´on con los conceptos del contexto, 74 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa que es justamente lo que nos interesa a la hora de definir patrones. Teniendo esto en cuenta, podemos generar nuevos ret´ıculos de conceptos incluyendo pseudo-conceptos y ret´ıculos de intents y de pseudo-intents, para estudiar la relaci´on entre conceptos y atributos con mayor riqueza. Esto permite tambi´en tener una estructura con m´as aristas, lo que facilita la integraci´on de m´etricas utilizadas en Teor´ıa de Grafos para estudiar nuestros nuevos ret´ıculos. En conclusi´on, los pseudo-intents permiten una puerta a trav´es de la cual objetivizar la b´usqueda subjetiva de la interpretabilidad. 4 Fundamentos de Geometr´ıa Computacional Introduciremos ahora ciertas nociones de geometr´ıa anal´ıtica para familiarizar al lector con los t´erminos que usaremos para nuestro estudio posterior. Nuestro objetivo es clasificar curvas a partir del ret´ıculo de conceptos formales generado. Apoyaremos las ideas aqu´ı presentadas con im´agenes del add-on de Blender [18] que se ha construido para este trabajo. En estas im´agenes se ver´a c´omo utilizar nuestras herramientas geom´etricas te´oricas de forma pr´actica en el entorno de Blender. Notaci´on Elementos de R3 P,Q: Puntos de R3. α, β : Curvas de B´ezier. π:Poly-curve (curva Poligonal). ¯α, ¯ β: Aproximaci´on de las curvas de B´ezier α, β, por poly-curves. Conjuntos relevantes B3: Conjunto de curvas de B´ezier de R3. Π3: Conjunto de poly-curves de R3. 76 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa Cotas n: N´umero de puntos de control de una curva de B´ezier α. N: N´umero de segmentos de la aproximaci´on ¯α. M: N´umero de u-curves menos uno que queremos obtener. Operaciones δN: Operaci´on que discretiza una curva de B´ezier por una poly-curve de N segmentos de manera uniforme. ∆N: Operaci´on que discretiza una superficie multi-reglada por una multireglada formada por poly-curves de Nsegmentos de manera uniforme. γ: Operaci´on que genera una superficie reglada a partir de dos curvas. Γ : Operaci´on que genera una superficie multi-reglada a partir de un conjunto de curvas. ∆M N: Operaci´on que discretiza una superficie de Monge por una multireglada formada por poly-curves de Nsegmentos de manera uniforme en OX y por Msegmentos en OY. 4.1 Curvas 4.1.1 Curvas de B´ezier Las curvas en las que nos centraremos ser´an las curvas de B´ezier [38], que reciben su nombre del ingeniero franc´es Pierre B´ezier [1910-1999], quien las desarroll´o en la d´ecada de 1960 mientras trabajaba para el fabricante de autom´oviles Renault para dise˜nar y modelar carrocer´ıas de autom´oviles. Este desarrollo llev´o a importantes avances en el campo del dise˜no asistido por computadora (CAD), del dibujo vectorial y del modelado 3D, ya que con solo unos pocos puntos de control, las curvas de B´ezier pueden representar una amplia variedad de formas, desde l´ıneas rectas hasta curvas complejas y org´anicas. 4. fundamentos de geometr ´ ıa computacional 77 Definici´on (Curva B´ezier).Dado un conjunto de puntos {Pi}0≤i≤n⊆R3, definimos la curva de B´ezier,β: [0,1] −→ R3, que los interpola como: β(t) = n X i=0 bi,n(t)Pi,0≤t≤1 donde: bi,n(t) = n iti(1 −t)n−i, i = 0, . . . , n son conocidos como polinomios de Bernstein[6] de grado n. Denotaremos por B3al conjunto de curvas de B´ezier de R3. Podemos ver un ejemplo de una curva de B´ezier en la figura 4.1. Figura 4.1: Curva de B´ezier con cuatro puntos de control. Corolario 4.1.Las curvas de B´ezier son curvas continuas y diferenciables. A los puntos {Pi}0≤i≤nse les suele llamar puntos de control, ya que permiten modificar la curva f´acilmente. Gracias a lo controlables que son, las curvas de B´ezier son un est´andar en el uso de CAD. Por ello, ser´an las curvas que usaremos para aproximar las curvas en la experimentaci´on. A partir de ahora, salvo que se diga lo contrario, trabajaremos siempre con curvas de B3. 78 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa Se pueden crear curvas de B´ezier con el add-on que acompa˜na a este trabajo por medio del bot´on Add Bezier Curve (ver Fig. 4.2), que generar´a por defecto una curva de B´ezier con dos puntos de control. En la parte pr´actica entraremos en m´as detalle de c´omo a˜nadir m´as puntos de control. Figura 4.2: Visualizaci´on de la generaci´on de una curva de B´ezier en el add-on A partir de una curva de B3, podemos generar curvas poligonales que la aproximan. Para ello, introducimos algunas definiciones habituales de geometr´ıa b´asica. 4.1.2 Aproximaci´on poligonal Definici´on (Segmento entre PyQ).El segmento entre los puntos P,Q∈ R3parametrizado por λes: PQ(λ) = (1 −λ)P+λQ,con λ∈[0,1] A partir de los segmentos, se construye una poly-curves como la sucesi´on de segmentos entre puntos sucesivos de la curva original: 4. fundamentos de geometr ´ ıa computacional 79 Definici´on (Curva Poligonal o Poly-Curve).Dado un conjunto de puntos {Pi}0≤i≤N, y una partici´on 0 = t0< ... < tN= 1 de [0,1], definimos la curva poligonal (poly-curve)como π(t) = N−1 X i=0 ((1 −λi(t))Pi+λi(t)Pi+1)·I(ti≤t < ti+1), donde λi(t) = t−ti ti+1 −ti . Denotaremos por Π3el conjunto de curvas poligonales. De esta forma, las curvas poligonales est´an definidas por medio de parametrizaciones en el intervalo [0,1]. Usaremos las curvas poligonales como aproximaci´on de las curvas de B´ezier, dada una curva de B´ezier α, notaremos por ¯αa la poly-curve que usaremos para aproximarla. Una de las maneras habituales de elegir los puntos de soporte es decidir previamente con cu´antos segmentos queremos aproximar α∈B3y elegir los puntos de manera equidistante. Si queremos usar Nsegmentos, se considera una partici´on uniforme de [0,1], 0 = t0< ... < tN= 1, con ∆t:= ti+1 −ti=1 N. En determinadas situaciones convendr´a dividir αpor zonas, y en las zonas con m´as detalle adaptar el paso, como se muestra en la figura 4.3. En el add-on esto se ha implementado como opci´on. Debido al uso que haremos de la operaci´on anterior a lo largo del texto, definimos el siguiente operador: Definici´on (Funci´on discretizadora de Nsegmentos).Dada una curva de B´ezier α: [0,1] −→ R3y dado N∈N, con N≥2, definimos δN:B3−→ Π3 α7−→ ¯αN 80 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa Figura 4.3: Adaptaci´on de segmentaci´on seg´un detalle de la curva. Donde ¯αNes la poly-curve definida sobre los puntos {α(ti)}0≤i≤Nen la partici´on N-uniforme de [0,1]. En el add-on, el operador δNse aplica sobre una curva de B´ezier (como la generada en la figura 4.2) a trav´es del bot´on Curve to poly, como vemos en la figura 4.4. Figura 4.4: Aplicaci´on del operador δen el add-on 4. fundamentos de geometr ´ ıa computacional 81 Para simplificar la notaci´on, en general omitiremos el super´ındice Nde ¯αNal hablar de la aproximaci´on de α, y muchas veces daremos las poly-curves por medio de los segmentos que define: ¯α:= {sj}1≤j≤N, donde sj= ((1 −λj−1(t))Pj−1+λj−1(t)Pj), t ∈ [tj−1, tj] y con 1 ≤j≤N. Abusando de la notaci´on, hablaremos de aplicar δNtambi´en a conjuntos de curvas de B3: {αi}0≤i≤M δN −→ {δN(αi)}0≤i≤M 4.2 Superficies El objetivo es extender algunas de las metodolog´ıas que desarrollemos sobre curvas a superficies. Al igual que hemos decidido restringir nuestro trabajo a curvas de B´ezier, no trabajaremos con cualquier tipo de superficie, ya que resultar´ıa excesivamente complicado y general. En su caso, trabajaremos con superficies que podamos definir y manipular de forma similar a una curva, o a un conjunto parametrizado sencillamente por curvas. Definici´on (intuitiva).Una superficie es codificable si existe una manera de reconstruir la superficie a partir de una, o varias, curvas. No toda superficie podr´a ser tratada de esta manera, por lo que nos restringiremos a tipos de superficies que s´ı se ajustan a esta condici´on. Por ello, en esta secci´on trabajaremos con superficies que son f´acilmente codificables y veremos c´omo aproximar algunas superficies por otras que son codificables. Definici´on (Superficie).Diremos que Xes una superficie si existen U, V abiertos conexos y Xi:R2−→ R, i = 1,2,3, funciones continuas, tales que: X:U⊆R2−→ V⊆R3 (u, v)−→ X(u, v)=(X1(u, v), X2(u, v), X3(u, v)) En la pr´actica, y desde un punto de vista computacional, UyVno ser´an abiertos cualesquiera, sino aquellos que podemos manipular sencillamente por 88 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa podemos extender el operador de cierre a sucesiones finitas de curvas como: Γ : C⊂B3−→ R3 Γ(C) = [ i∈{0,...,M−1} γ(αi, ui, αi+1, vi), con ui∈[ai, bi], vi∈i M+1,i+1 M+1, para 0 ≤i≤M. Vemos que esta uni´on garantiza una superficie continua, ya que los diversos cierres generados por γse unen por los bordes (4.2.2). La figura 4.12 muestra un ejemplo de aplicaci´on de este operador sobre un conjunto formado por 4 curvas. (a) Conjunto C={α0, α1, α2, α3}(b) Superficie multi-reglada S= Γ(C) Figura 4.12: Aplicaci´on del operador Γ Todas las definiciones que hemos visto siguen siendo v´alidas en el caso de curvas de Π3y, como en el caso del cierre de curvas, γ, podemos extender la definici´on de Γ al caso discreto. Si S= Γ(C) es una superficie reglada, ¯ S= Γ( ¯ C) con ¯ C={¯αiN}es su superficie poligonal asociada donde cada ¯αiNtiene N+ 1 puntos de control. Podemos ver la versi´on discretizada del ejemplo de la figura 4.12 en la figura 4.13. 4. fundamentos de geometr ´ ıa computacional 89 Figura 4.13: Superficie multi-reglada poligonal ¯ S 4.2.4 Discretizaci´on de superficies Si tenemos la superficie generada por C={αi}1≤i≤m, i.e. Γ(C), podemos obtener su dicretizada a partir de las discretizaciones de las curvas, ¯ C={¯αi}1≤i≤m. Para ello: Definici´on. Sea C={αi}1≤i≤m⊂B3, definimos la superficie discretizada de Γ(C) como ∆N(Γ({αi})) := Γ({δN(αi)}). La acci´on de definici´on se representa por el diagrama de la figura 4.14. Ahora, ya estamos en condiciones para poder definir de manera expl´ıcita una funci´on que, dada una superficie cualquiera, la discretice. La siguiente definici´on puede definirse para cualquier tipo de superficie X, sin embargo, nos centraremos en las que est´an definidas en [0,1] ×[0,1] ⊂R2por motivos de simplificaci´on en la definici´on. 90 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa Figura 4.14: Diagrama de discretizaci´on 4. fundamentos de geometr ´ ıa computacional 91 Definici´on. Dada la superficie Xdefinida en [0,1] ×[0,1], el mallado de la superficie con M×Ncuadr´ıculas (que representar´an Nsubdivisiones en OX yMsubdivisiones en OY) viene dado por: ∆M N(X(u, v)) := ∆N(Γ{X(u, 0 M), X(u, 1 M), ..., X(u, M M)}) O, lo que es equivalente, ∆M N(X(u, v)) := ∆N(Γ(UM(X(u, v)))}) Es decir, dada X(u, v) en [0,1] ×[0,1] obtenemos sus u-curves seccionando el segundo [0,1] en Msegmentos (aplicar δMa [0,1]) y, a continuaci´on, discretizamos las M+ 1 u-curves {X(u, 0 M), X(u, 1 M), ..., X(u, M M)}con δN, definiendo una superficie con Γ a partir de las polycurves. El razonamiento se visualizar´a en el diagrama de la figura 4.15. X(u, v) {X(u, v0), ..., X(u, vM)} Γ({X(u, vj)}0≤j≤M){δN(X(u, vj)}0≤j≤M Γ({X(u, vj)N}0≤j≤M) UM ΓδN ∆NΓ Figura 4.15: Diagrama de discretizaci´on de una superficie X. Hasta ahora, hemos definido nuestros objetos y nuestras herramientas b´asicas para poder empezar a construir las herramientas de nuestro problema. Nuestro 92 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa objetivo era poder discretizar superficies de tal manera que la informaci´on de ´estas pueda estar contenida por medio de curvas. En el add-on que acompa˜na este trabajo volvemos sobre nuestra superficie de Monge T(Fig. 4.5) para discretizarla fijando los valores NyM(n´umero de subdivisiones en el eje OX y en el eje OY respectivamente). En la figura 4.16 se muestra un ejemplo con N=M= 10. Figura 4.16: Superficie de Monge discretizada. 5 Implementaci´on Recordemos que nuestro problema era poder comparar diferentes elementos geom´etricos, curvas en este caso. Para hacerlo queremos extraer su ret´ıculo de conceptos. El siguiente algoritmo permite extraer los conceptos formales a partir de un conjunto de datos con operaciones elementales. Notaci´on Elementos α: Curva de B´ezier a estudiar. ¯α: Aproximaci´on de αpor una poly-curve. si: segmento i-´esimo de ¯α. cj: Caracter´ıstica j-´esima a medir. aij : Caracter´ıstica medida cj, del segmento si. Cad(n) : son las cadenas de hasta ns´ımbolos que no admiten dos s´ımbolos sucesivos iguales. Operaciones ⊕: Concatenaci´on con eliminaci´on de repetidos. σm: C´omputo simb´olico en la m-´esima iteraci´on. ´ Indices y cotas N: N´umero de segmentos de ¯α. 94 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa k: N´umero de caracter´ısticas a medir. END : N´umero de iteraciones del algoritmo. 5.1 Pre´ambulo t´ecnico Antes de dar el algoritmo es importante definir ciertas herramientas para trabajar con s´ımbolos. Nuestros atributos ser´an conjuntos de cadenas de s´ımbolos y nuestros objetos ser´an intervalos de R. Definici´on. Fijado un alfabeto, V, Cad(n) son las cadenas de hasta n s´ımbolos consecutivos sin repeticiones sucesivas (es decir, no se admiten elementos sucesivos iguales), usando un conjunto Vde s´ımbolos dado. Corolario 5.1.Fijado V, se cumple que Cad(m)⊆Cad(n)⇐⇒ m≤n. Por ejemplo, si consideramos el conjunto de s´ımbolos {♠,♡,♣,♢}, entonces: ♡ ∈ Cad(2) ♢♣ ∈ Cad(2) ♣♣ /∈Cad(2) ♠♢♣ /∈Cad(2) Definici´on. Definimos el operador ⊕entre cadenas como: ⊕: Cad(m)×Cad(n)−→ Cad(m+n),(a, b)7−→ a⊕b que concatena ambas cadenas eliminando s´ımbolos iguales consecutivos. En otras palabras, compara el ´ultimo s´ımbolo de acon el primer s´ımbolo de by, en caso de coincidir, elimina uno de ellos. Siguiendo con el conjunto de s´ımbolos {♠,♡,♣,♢}, tenemos que: 5. implementaci´ on 95 ♠♢ ⊕ ♢♠=♠♢♠ ♠♢♣ ⊕ ♢♣=♠♢♣♢♣ En lo que queda de cap´ıtulo fijaremos V={<, =, >}.Tras estas operaciones b´asicas, podemos detallar cada uno de los pasos del algoritmo: 5.2 Tipos de Datos Nuestros objetos a estudiar son segmentos de curvas de B´ezier (es una simplificaci´on impuesta por motivos computacionales, tanto para facilitar su representaci´on num´erica como visual), y nuestros datos ser´an mediciones de distintas caracter´ısticas sobre dichos objetos. Como vimos en cap´ıtulos anteriores, aproximamos una curva de Bezi´er, α, por su poly-curve, ¯αN, definida a partir de Nsegmentos. Cada uno de estos segmentos ser´a denotado por los elementos de una sucesi´on {si}i∈{1...N}.De esta forma, identificaremos ¯αN={si}1≤i≤N. Por otro lado, de cada segmento obtendremos kcaracter´ısticas tras una medici´on, que pueden ser ´angulo respecto a cada eje, ´angulo respecto al segmento anterior, longitud del segmento, color del segmento, etc. Denotaremos las distintas caracter´ısticas medidas como la estructura {c1, ..., ck}. Una estructura puede ser {longitud, ´anguloX, ´anguloY ,m´oduloV N}donde, para cada segmento, medimos su longitud, su rotaci´on respecto a los ejes cartesianos, y el m´odulo de su vector normal. As´ı, para cada segmento sitenemos asociado un vector de datos (ai1, ..., aik)∈Rk con sus kcaracter´ısticas medidas asociadas, donde aij es el valor de cjpara si, con 1 ≤i≤Ny 1 ≤k. Para el segundo segmento, s2, podr´ıamos tener, seg´un la estructura anterior, los datos (2, π/4, π, 2). 96 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa Por lo que los datos de una poly-curve podr´ıa quedar representados en una matriz de datos (aij)∈RN×M:         a11 a12 a13 · · · a1k a21 a22 a23 · · · a2k a31 a32 a33 · · · a3k . . .. . .. . ..... . . aN1aN2aN3· · · aNk         donde la fila icontiene las kcaracter´ısticas medidas del segmento si, y cada columna jcontiene el valor de la caracter´ıstica cjdel segmento si.Ser´a a partir de las filas de donde obtendremos nuestros extents y a partir de las columnas nuestros intents. En nuestro caso, aij ∈R, si bien se podr´ıan considerar valores no reales (como s´ımbolos, vectores o n´umeros complejos), en esta primera aproximaci´on nos centraremos ´unicamente en valores reales [34], ya que es m´as f´acil establecer una relaci´on de orden. Aplicando un m´etodo de diferencias sucesivas, compararemos cada caracter´ıstica cjde los segmentos consecutivos siysi+1 y le asignaremos un s´ımbolo comparador de V={<, =, >}, con su sem´antica habitual para n´umeros reales. Tras ello, aplicaremos un procedimiento de limpieza con el que obtendremos las cadenas de s´ımbolos que definir´an los atributos. Es importante destacar que estos comparadores son mutuamente excluyentes y abarcan todas las posibles relaciones entre los valores de los atributos. Es decir, para cualquier par de valores posibles en los atributos solo se puede aplicar uno de los comparadores [34]. El algoritmo que analizamos en este cap´ıtulo consta de una fase de generaci´on de extents y otra de intents. Damos sus pasos de forma detallada a continuaci´on. 5. implementaci´ on 97 5.3 Pasos Step 0. Preprocesamiento — Preprocessing Para cada ien 1 ≤i≤N, construimos el intervalo [i−1, i], que est´a asociado al segmento si(intuitivamente, representa el segmento entre el punto i−1 y el punto ide la curva). A cada segmento I=sile asociamos el vector de caracter´ısticas ¯σ0(I) := (σ0(I, 1), ..., σ0(I, k)), donde: σ0(I, j) :=          <si aij < ai+1,j, = si aij =ai+1,j, >si aij > ai+1,j obteniendo as´ı los pares ([i−1, i],(σ0(i, 1), ..., σ0(i, k))) para cada icon 1 ≤i≤N. Donde podemos observar c´omo var´ıa cada caracter´ıstica cjcualitativamente en cada segmento si. Denotaremos a estos pares iniciales (I0,Σ0) := {(I, ¯σ0(I)) : I∈ {si}1≤i≤N}. El conjunto de intervalos se denotar´a en adelante por I0. Step 1. C´omputo simb´olico de intervalos contiguos — Symbolic Computing Definici´on. Dos intervalos son contiguos si I1= [a, b] e I2= [b, c]. Para cada par de intervalos contiguos I1, I2, se crea un nuevo intervalo a partir de su uni´on: I1∪I2= [a, c]. Usemos la notaci´on J:= I1∪I2. De forma similar, a este intervalo se le asigna un vector (σ1(J, 1), ..., σ1(J, k)), donde σ1(I1∪I2, j) := σ0(I1, j)⊕σ0(I2, j).Obteniendo, de nuevo, un par del tipo (intervalo, caracter´ısticas): (J, (σ1(J, 1), ..., σ1(J, k))), donde para cada caracter´ıstica cj, su cadena de s´ımbolos σ1(J, j) en el intervalo Jviene dada por la siguiente tabla : 104 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa el intervalo [0,1] es redundante con [0,2], pues el segundo lo contiene como intervalo y tienen el mismo atributo. ([0, 1], [<, <, =]), ([1, 2], [<, <, =]), ([2, 3], [<, <, =]), ([3, 4], [<, <, =]), ([4, 5], [<, >, =]), ([5, 6], [<, >, =]), ([6, 7], [<, >, =]), ([7, 8], [<, >, =]), ([8, 9], [<, >, =]), ([9, 10], [<, >, =]), ([10, 11], [<, >, =]), ([11, 12], [<, >, =]), ([0, 2], [<, <, =]), ([1, 3], [<, <, =]), ([2, 4], [<, <, =]), ([3, 5], [<, <>, =]), ([4, 6], [<, >, =]), ([5, 7], [<, >, =]), ([6, 8], [<, >, =]), ([7, 9], [<, >, =]), ([8, 10], [<, >, =]), ([9, 11], [<, >, =]), ([10, 12], [<, >, =]), ([11, 12], [<, >, =]) Repitiendo 4 veces, acabamos llegando al concepto que define la curva en su totalidad: Lista de conceptos (('<', {'<', '>', '<>'}, '='), [ ]), (('<', '<', '='), [[0, 4]]), (('<', '>', '='), [[4, 12]]), (('<', '<>', '='), [[0, 12]]) Lista de Pseudo-Conceptos ((' ', ' ', '='), [[0, 12]]), ((' ', '<', ' '), [[0, 4]]), ((' ', '<', '='), [[0, 4]]), (('<', ' ', ' '), [[0, 12]]), (('<', ' ', '='), [[0, 12]]), (('<', '<', ' '), [[0, 4]]), (('<', '<', '='), [[0, 4]]), ((' ', '<>', ' '), [[0, 12]]), ((' ', '<>', '='), [[0, 12]]), (('<', '<>', ' '), [[0, 12]]), (('<', '<>', '='), [[0, 12]]), ((' ', '>', ' '), [[4, 12]]), ((' ', '>', '='), [[4, 12]]), (('<', '>', ' '), [[4, 12]]), (('<', '>', '='), [[4, 12]]) El ret´ıculo generado ser´a: 5. implementaci´ on 105 ((’<’, {’<’, ’>’, ’<>’}, ’=’),[]) ((’<’, ’<’, ’=’), [[0, 4]]) ((’<’, ’>’, ’=’), [[4, 12]]) ((’<’, ’<>’, ’=’), [[0, 12]]) Como extra, el add-on tiene incorporado un visualizador de conceptos y pseudoconceptos. Introduciendo en el cuadro rojo el intent opseudo-intent, se generar´a en la curva una estructura que muestra (con un color aleatorio, esta vez verde) el derivado del intent opseudo-intent deseado. En este ejemplo, deseamos obtener los intervalos que tengan el atributo (<, < ,=); por lo anterior, sabemos que ese concepto es ((<, <, =),[[0,4]]), en la curva queda se˜nalado [0,4] (5.6). Figura 5.6: Visualizaci´on del concepto ((<, <, =),[[0,4]]) sobre la curva 106 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa 5.6 Patrones Es dif´ıcil definir el concepto de patr´on para que se ajuste a la intuici´on con que lo usamos en diferentes contextos. En el ´ambito de este trabajo (y del uso posterior que podr´ıa hacerse de este trabajo en el terreno del dise˜no) los patrones son conjuntos interesantes de atributos. Por ejemplo, pueden ser los atributos relacionados con la idea de redondez de una circunferencia, pues son patrones m´as interesantes para estudiar la relaci´on entre conceptos en L(K) que otros subconjuntos de atributos. Concretamente, si consideramos el concepto donde la terna representa los cambios en el ´angulo de rotaci´on: (Segmentos, (RotEjeX, RotEjeY, RotEjeZ)) : ([0,629],(=,=, <)) conseguimos reflejar la idea de la redondez de una circunferencia (cos(t), sin(t),0), t ∈ [0,2π), con una aproximaci´on de 628 segmentos (Fig. 5.7), ya que el atributo (=,=, <) muestra que ´unicamente se producen cambios en el ´angulo de rotaci´on del EjeZ, mientras que en el EjeXyEjeYno se produce ning´un cambio. As´ı, cuando estemos ante una caracter´ıstica de tipo RotEje y vemos un s´ımbolo <o>, estamos ante un patr´on que se asocia con un giro. Figura 5.7: (cos(t), sin(t),0), t ∈[0,2π) 6 An´alisis de la Curva Aproximada En este cap´ıtulo estamos interesados en poder establecer un criterio para clasificar las curvas seg´un su “complejidad”. Al no ser sencillo definir la complejidad de una curva, empezaremos intentando acotar el n´umero de iteraciones que dar´a nuestro algoritmo seg´un el n´umero de segmentos que consideremos en su aproximaci´on, N. Tras ello, encontraremos un noci´on intuitiva de complejidad que relacionaremos con la Complejidad de Kolmogorov, estableciendo intuitivamente qu´e considerar´ıamos por una curva “compleja”. Nos basaremos en estos puntos para luego responder a una pregunta fundamental en cualquier experimento, ¿necesitamos m´as datos para nuestro modelo? Notaci´on Elementos de AFC K: Contexto formal (G, M, I). L(K) : Ret´ıculo de conceptos de K, del ingl´es Lattice. Cα(N) : Concepto supremo del ret´ıculo L(K) para ¯αN. END : N´umero de iteraciones en llegar a Cα(N) con el algoritmo. ENDMAX : N´umero m´aximo de pasos que puede llegar a dar el algoritmo para calcular Cα(N). END∗: N´umero de segmentos con los que se describe la totalidad de la curva α. 108 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa 6.1 Cota del N´umero de Iteraciones La cuesti´on de la eficiencia en las aproximaciones ¯αpuede convertirse en una tarea fundamental en muchas aplicaciones de este estudio. A nivel de recursos, interesa ejecutar el algoritmo el menor n´umero de veces obteniendo la mayor informaci´on posible en cada iteraci´on. Empecemos formalizando ciertas nociones que nos facilitar´an el trabajo. Definici´on. Llamaremos concepto supremo de L(K¯αN), y lo denotaremos por Cα(N), al supremo del ret´ıculo de conceptos de ¯αN. Denotaremos por END el n´umero de iteraciones en las que llega el algoritmo al concepto supremo. Aunque este valor depende de la curva αy de N, no reflejaremos esta dependencia para no sobrecargar la notaci´on, ya que en lo que sigue trabajaremos sobre una curva prefijada). Como vimos en el cap´ıtulo anterior (5.4), pudimos acotar END en funci´on del n´umero de segmentos de la curva ¯αN: END ≤ ⌈log2(N)⌉ Si denotamos por ENDmax al m´aximo de iteraciones que puede llegar a hacer el algoritmo para llegar al concepto supremo, sin tener en cuenta la curva a estudiar y ´unicamente teniendo en cuenta el N, ENDmax es el peor END que puede suceder antes de ejecutar el programa. Esta ser´ıa nuestra cota superior. Corolario 6.1.Dada una poly-curve, ¯αN,ENDmax =⌈log2(N)⌉. En particular, si α∈B3y¯αNes una aproximaci´on suya con N= 2l, l∈N+, entonces ENDmax =l. Seguiremos la estrategia de elegir N= 2lcon l∈N+, por lo que END ≤l. As´ı, maximizamos la informaci´on que podemos conseguir haciendo el mismo n´umero m´aximo de iteraciones. 6. an´ alisis de la curva aproximada 109 Representando gr´aficamente log2(N) podemos definir los distintos tipos de aproximaciones de αseg´un su n´umero de iteraciones. Podemos ver esta clasificaci´on en la figura 6.1 junto a su tabla asociada 6.2. Donde podemos ver, gr´aficamente, porqu´e es buena idea escoger N≥2 como potencias de 2. 248 16 32 64 128 0 1 2 3 4 5 6 7 N log2(N) Regiones del n´umero m´aximo de iteraciones Figura 6.1: log2(N) para 2 ≤N≤128 con regiones (2m−1, 2m] coloreadas. Reg ENDmax 2 iters 3 iters 4 iters 5 iters 6 iters 7 iters Figura 6.2: Tabla de regiones seg´un ENDmax . En los siguientes ejemplos, cambiaremos el orden habitual (objeto, atributo) por su dual (atributo, objeto), con el fin de facilitar la lectura de los conceptos. Para interpretar mejor los intents, el conjunto de caracter´ısticas a estudiar de la curva ¯αNser´a {EjeX, EjeY, EjeZ}. 6.1.1 Caso pr´actico Vamos a presentar una aproximaci´on de una curva ¯αNcon N= 2l,1≤l≤6 en la figura 6.3. Tras una peque˜na experimentaci´on, comprobaremos en la tabla 6.1 que END ≤l= ENDmax . 110 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa Figura 6.3: Aproximaci´on de una curva αcon 2lsegmentos, l∈ {1...6}. La aplicaci´on del algoritmo en la curva de ejemplo proporciona los resultados mostrados en la tabla 6.1. N l = ENDmax END Cα(N) 64 6 2 ((<, <><, =), [[0, 64]]) 32 5 2 ((<, <><, =), [[0, 32]]) 16 4 2 ((<, <><, =), [[0, 16]]) 8 3 2 ((<, <><, =), [[0, 8]]) 4 2 2 ((<, <><, =), [[0, 4]]) 2 1 1 ((<, <, =), [[0, 2]]) Cuadro 6.1: Experimentaci´on asociada a la figura 6.3. Interpretaci´on de la tabla 6.1: El concepto supremo es Cα(32) = ((<, <><, =), [[0, 32]]) Su extent es [0, N] = [0,32], y su intent es (<, <><, =), que se interpretar´a como: “Es una curva que crece en el EjeX, primero sube y luego baja para volver a subir en el EjeY , mientras no cambia en el EjeZ”. Viendo la imagen 6.3 vemos 6. an´ alisis de la curva aproximada 111 que es una buena descripci´on de la curva ¯α32, l = 5. Vemos tambi´en que es una buena descripci´on para el resto de aproximaciones, salvo para N= 2. Esta breve experimentaci´on permite verificar que se cumple la desigualdad END ≤ENDmax .Adem´as, aunque el valor Nde ¯αNsea alto, una vez alcanzado el concepto supremo Cα(N), aumentarlo m´as no generar´a nuevos conceptos (de ah´ı el nombre de concepto supremo). La tabla 6.1 muestra adem´as algo m´as: cuando l= 1 no se llega a alcanzar el mismo concepto supremo que en los casos anteriores, esto significa que no todos los Ndescriben con la misma precisi´on la curva α. Cabe aclarar que, en el caso de la figura 6.3 y de su tabla 6.1, estamos seguros de haber llegado al concepto supremo ya que en este caso es f´acil comprobar si el concepto supremo describe la totalidad de la curva. Seg´un la naturaleza de la curva, esta comprobaci´on no siempre ser´a posible. 6.2 Problema del N´ Optimo El ejemplo anterior nos permite ver que, seg´un el valor Nde la aproximaci´on, no siempre se podr´a describir el comportamiento de la curva en su totalidad. Supongamos que tenemos un or´aculo que nos dice el m´ınimo Nque describe la curva α, que denotaremos por END∗. Recordemos que el algoritmo se detiene cuando un extent de intervalos es igual al intervalo [0, N], en END pasos del algoritmo. Imaginemos ahora que eliminamos esta condici´on y que el algoritmo siempre har´a ENDmax iteraciones. As´ı, ocurre que Cα(END) = Cα(ENDmax).Veamos qu´e ocurre con END∗: Si ENDmax >END∗, entonces se han hecho pasos innecesarios, pues Cα(n) = Cα(END∗),∀n≥END∗ 112 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa Si ENDmax <END∗, entonces no se llega a describir α, pues Cα(n)⊊Cα(END∗),∀n < END∗ Es evidente tambi´en que END∗≥END. Como sabemos, en END pasos llegamos a un concepto supremo que depende del n´umero de segmentos N. El concepto supremo obtenido en END∗pasos, es el supremo de todos los conceptos supremos. Es decir, Corolario 6.2. Cα(END∗) = _ N∈N (Cα(N)). Por lo tanto, nuestro problema se resume en la pregunta: ¿Hemos pasado ya a END∗?Que es equivalente a preguntarse si es in´util seguir aumentando Nbuscando m´as precisi´on. O lo que es lo mismo, ¿aparecer´an nuevos conceptos aumentado N? Para responder a esta pregunta, partiremos de la clasificaci´on de ¯αNseg´un ENDmax que hicimos anteriormente para intentar guiar nuestras acciones respecto a aumentar N. 6.3 Complejidad de Kolmogorov 6.3.1 Intuici´on Empezaremos por una noci´on de complejidad de relevancia hist´orica. Podr´ıamos decir que la complejidad de Kolmogorov propone “medir la complejidad de un objeto seg´un c´omo de complicado sea describirlo”. Esta idea intuitiva nos permite introducir esta medida de complejidad. La idea de la complejidad de Kolmogorov [27], propuesta por el matem´atico sovi´etico Andrei Kolmogorov [1903- 1987] en la d´ecada de 1960, se refiere a un 6. an´ alisis de la curva aproximada 113 concepto fundamental en la Teor´ıa de la Informaci´on y Teor´ıa de la Computabilidad. La complejidad de Kolmogorov busca medir la complejidad de un objeto o secuencia en t´erminos de la longitud m´as corta de un programa (instrucciones de un lenguaje formal) que puede generar esa secuencia. En t´erminos m´as simples, la complejidad de Kolmogorov se relaciona con cu´anta informaci´on es necesaria para describir un objeto o una secuencia. Si una secuencia es muy regular o predecible, como una secuencia de n´umeros repetitivos, su complejidad de Kolmogorov ser´a baja, ya que se puede describir con un programa inform´atico muy corto. Por ejemplo, 4 en binario es 1002, La fracci´on 1 3en binario es: 0.01012. Si una secuencia es altamente aleatoria o ca´otica, su complejidad de Kolmogorov ser´a alta, ya que se requerir´a un programa m´as largo para describirlo. Por ejemplo, La f´ormula del algoritmo de Chudnovsky [10] para calcular πes: 1 π= 12 ∞ X k=0 (−1)k(6k)!(545140134k+ 13591409) (3k)!(k!)36403203k+3 2 . Hay que aclarar que la complejidad de Kolmogorov es un concepto te´orico que, en la pr´actica, no se puede calcular de manera exacta para la mayor´ıa de los objetos o secuencias reales. Sin embargo, es una noci´on que proporciona una forma intuitiva de pensar la complejidad y la informaci´on. Mezclando diversas aproximaciones a esta complejidad, la complejidad de Kolmogorov tambi´en puede describirse de manera aproximada como “el tama˜no comprimido de un archivo”. Sin embargo, existen algunas diferencias. En lugar de archivos (secuencias de bytes), consideramos cadenas de bits (secuencias de ceros y 120 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa 1 2 0 0.2 0.4 0.6 0.8 1 0.5 0.5 k P(L=k) N= 2 123 0 0.2 0.4 0.6 0.25 0.5 0.25 k P(L=k) N= 3 1 2 3 4 0 0.2 0.4 0.125 0.375 0.375 0.125 k P(L=k) N= 4 12345 0 0.1 0.2 0.3 0.4 0.5 0.0625 0.25 0.375 0.25 0.0625 k P(L=k) N= 5 Figura 6.7: Distribuciones Binomiales para N= 2,3,4,5 con p= 0.5. Parte II Aplicaciones 7 Experimentaci´on En este cap´ıtulo usaremos el add-on y someteremos una curva algunas variaciones a diferentes pruebas. El conjunto de caracter´ısticas que usaremos ser´a el habitual, {EjeX, EjeY, EjeZ}.El objetivo de esta parte es mostrar la efectividad del algoritmo propuesto en [34] para la descripci´on total y parcial de curvas. 7.1 Curva de estudio Hemos definido la curva αmostrada en la figura 7.1, ya que es una curva que presenta cambios interesantes en todos los ejes. Podemos ver sus proyecciones en los planos XY (Fig. 7.2), XZ (Fig. 7.3) y en Y Z (Fig. 7.4). En lo siguiente, para hacer coincidir la notaci´on mostrada con la que usa esta versi´on de Blender, empezaremos numerando los puntos por 1, as´ı, el segmento siser´a [i, i + 1] en lugar del [i−1, i] visto hasta ahora. Empezaremos con una aproximaci´on de αpara N= 71, con ¯α71.Sabemos que log2(71) ≃6.14, por lo que ENDmax = 7, sabemos que el algoritmos parar´a en no m´as de 7 iteraciones (algo asumible por nuestro equipo). El algoritmo para en 4 iteraciones, obteniendo el concepto supremo: Cα(71) = ((><><, ><><, =<=>=<), [[1, 72]]) Interpret´emoslo: EjeX:><>< es “izquierdaderecha -izquierda - derecha” como puede verse en la figura 7.2. 124 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa Figura 7.1: αen perspectiva Figura 7.2: αvista desde EjeZ Figura 7.3: αvista desde EjeY 7. experimentaci´ on 125 Figura 7.4: αvista desde EjeX EjeY :><>< es “izquierdaderecha -izquierda - derecha” como puede verse en la figura 7.2. EjeZ:=<=>=< es “permanecesube -permanece- baja -permanece -sube” como puede verse en la figura 7.3. Podemos ver que, efectivamente, Cα(71) = Cα(END∗). Para m´as claridad, aprovechemos y marquemos el pseudo-intent ( , , =), lo que nos permitir´a leer mejor el cambio =<=>=< del EjeZ (Fig. 7.5 y 7.6). 7.2 Reducci´on del n´umero de segmentos Nos interesa saber ahora el m´ınimo de intervalos necesarios para definir la curva manteniendo las mismas propiedades de cambio. Sabemos que END = 4, por lo que podemos partir de una segmentaci´on N= 24= 16. Tras la experimentaci´on sigue apareciendo Cα(71) hasta N= 11: ((><><, ><><, =<=>=<), [[1, 12]]) 126 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa Figura 7.5: Intervalos donde zno var´ıa (I). Con N= 10: ((><><, ><><, =<=>=), [[1, 11]]) Lo que implica que el concepto supremo Cα(10) no es el que describe a la curva. Podemos asegurar que Cα(11) = Cα(END∗), ya que es el m´ınimo Npara el que se describe la curva en su totalidad. Podemos mostrar una comparaci´on de un concepto de ¯α11 y ¯α71 en la figura 7.7. 7.3 Invarianza frente a transformaciones Es f´acil imaginar que trasladar no influye en nada a los conceptos generados por la estructura {EjeX, EjeY, EjeZ}.En el caso de las rotaciones no se conservan respecto a las coordenadas globales. Veremos con m´as detalle el caso del 7. experimentaci´ on 127 Figura 7.6: Intervalos donde zno var´ıa (II). 128 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa Figura 7.7: Comparaci´on de la capacidad de describir conceptos con N= 11 y N= 71. escalado, que adem´as de ser m´as interesante visualmente, es una transformaci´on global que se asemeja m´as a las transformaciones que podemos hacerle a una curva para modificar sus medidas sin cambiar el comportamiento de sus segmentos. 7.3.1 Traslaciones No afectan al ret´ıculo, indirectamente lo hemos visto en los ejemplos anteriores. 7.3.2 Rotaciones Respecto a los ejes relativos a la curva, s´ı mantienen el ret´ıculo de conceptos, pero respecto a las coordenadas globales evidentemente no lo conservan. 7.3.3 Escalado Aplicaremos diferentes escalados y tras comparar la lista de conceptos generada, marcaremos un intervalo para ilustrarlo. 7. experimentaci´ on 129 El escalado a lo largo de los diferentes ejes mantiene el ret´ıculo de conceptos de la curva, tiene sentido pues si aplicamos el escalado : (EjeX :a, EjeY : b, EjeZ :c) en las diferencias finitas (∆x,∆y,∆z) obtenemos (∆ax,∆by,∆cz) = (a∆x, b∆y, c∆z), podemos verlo en las figuras 7.8 y 7.9. Figura 7.8: Mismo concepto marcado para diferentes escalados (I). 7.4 Pregunta inicial Ahora, podemos responder a la pregunta inicial. Podemos importar en Blender el dibujo con el que empieza este trabajo (Fig. 7.10). Mediante t´ecnicas avanzadas de CAD podemos reducir ese dibujo a un par (curva de B´ezier, grosor). Aplicando el algoritmo ´unicamente a la curva de B´ezier en ambos casos, nos queda como concepto supremo: ((<>, <><, =), [[1, 47]]) Por lo que la respuesta es s´ı, son iguales... al menos, para {EjeX, EjeY, EjeZ}. 136 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa change ="=" atributo.append(change) intervals.append(([j, j+1], atributo)) return intervals Step 1: C´omputo Simb´olico. Para este paso se divide la tarea en distintas partes, que para una mejor comprensi´on se ha definido en diferentes funciones: Dado dos atributos (cadenas de comparadores), verificamos si el ´ultimo s´ımbolo del primer atributo es igual que el primer s´ımbolo del segundo atributo: def son_atributos_compatibles(atributo : list,otro_atributo: list)->bool: # ['-↑↑↑↑↑'],[↑↑↑↑↑↑↑↑↑-'] --> True # ['-↑↑↑↑↑'],[-↑↑↑↑↑↑↑↑-'] --> False return atributo[0][-1]== otro_atributo[0][0] Para unir ambos atributos y eliminar los s´ımbolos contiguos iguales definimos: def reducir_cadena(cadena): # ['-↑↑↑↑↑↑↑↑↑↑↑↑↑↑-'] --> '-↑-' resultado =[] for char in cadena: # Si el ´ultimo car´acter en el resultado no es igual al car´acter actual, agr´egalo al resultado if not resultado or char != resultado[-1]: resultado.append(char) return ''.join(resultado) def combinar_atributos(intent1: list,intent2: list)->list: # ['-↑↑↑↑↑'],[↑↑↑↑↑↑↑↑↑-'] --> '-↑-' n=len(intent1) # numero de caracter´ısticas medibles b=[] for iin range(n): b.append(reducir_cadena(''.join([intent1[i],intent2[i]]))) 8. an´ alisis del c´ odigo 137 Con estas funciones es sencillo recorrer todos los pares aplic´andolo. Step 2: Eliminar redundancias. Para este paso, la ordenaci´on con una funci´on an´onima sorted(., key =lambdax :x[0]) ha posibilitado mejorar y reducir el n´umero de funciones a definir. def eliminar_intervalos_contenidos_con_mismo_atributo(intervalos): # a iguales atributos, nos quedamos con # la tupla con el mayor objeto intervalos =sorted(intervalos, key=lambda x: x[0]) tuplas_seleccionados =[] for objeto, atributo in intervalos: contenido =False for otra_tupla in intervalos: if atributo == otra_tupla[1]and objeto != otra_tupla[0] : if otra_tupla[0][0]<= objeto[0]and otra_tupla[0][1]>= objeto[1]: contenido =True break if not contenido: tuplas_seleccionados.append((objeto, atributo)) return tuplas_seleccionados Step 3: Recursi´on. Debido a que las listas no son objetos hashables en Python, para este paso nos vimos forzados a definir una funci´on que eliminara los elementos repetidos en un conjunto de datos para poder repetir la ejecuci´on del c´odigo: def eliminar_repetidos(data): res=[] for data_p in data: if data_p not in res: 138 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa res.append(data_p) return res Tras esto, basta implementar el proceso en un bucle hasta ENDmax =math.log(N,2) + 1. Para ordenar y presentar los conceptos usamos un diccionario una vez generados: def metodo(): preprocesado =step_0(angulo_global_from_poly()) print("\n Step o: Preprocessing\n",preprocesado) limpiado =preprocesado computado =limpiado for iin range(math.floor(math.log(len(limpiado),2))+1): computado += step_1(limpiado) #computado = eliminar_tuplas_repetidas(computado) print("\n Iteraci´on", i+1, " Step 1: Compute Symbolic Differences\n",computado) print("Hay ",len(computado),"elementos") limpiado =step_2(computado) limpiado =eliminar_repetidos(limpiado+preprocesado) limpiado =sorted(limpiado, key=lambda x: x[0]) #limpiado = eliminar_tuplas_repetidas(computado) print("\n Iteraci´on", i+1," Step 2: Removed Redundances\n",limpiado) print("Hay ",len(limpiado),"elementos") #### Parte de unir los intervalos diccionario = unir_intervalos_tras_clasificacion( clasificar_por_segunda_componente_b(limpiado)) print("\n Veamos la clasificacion unida \n") print("En este caso habr´ıa que comprobar que para los atributos puros <,=,>se puedan unir sin contencion") for iin diccionario.items(): print(i) print("Hay ",len(clasificar_por_segunda_componente_b(limpiado)) 8. an´ alisis del c´ odigo 139 ,"elementos") # Combinar claves y valores en una lista de tuplas, lo transformamos para poder buscar dentro de ´el diccionario_como_lista =[(clave, valor) for clave, valor in diccionario.items()] print("\n Lista combinada: \n", diccionario_como_lista) return diccionario_como_lista 8.3 add-on de Blender Para la creaci´on del add-on se han consultado diferentes fuentes. La principal ha sido la propia documentaci´on [4] que proporciona la Blender Foundation [5]. En ella se ha podido acceder a la estructura b´asica para crear el panel de la UI y la llamada a las funciones. El add-on empieza con un bloque de informaci´on: bl_info ={ "name":"trabajo Cons", "author":"Constantino Benjumea Bellott", "version": (0,0,3), "blender": (2,80,0), "location":"3D Viewport > Sidebar > My Custom Panel category", "description":"Add-on realizado para trabajo", "category":"Development//Learning", } La gesti´on de variables se gestiona desde la librer´ıa bpy de Blender, con la estructura bpy.props. En esta parte guardamos el concepto a destacar en una variable llamada nombre dentro de la escena de trabajo: 140 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa bpy.types.Scene.nombre= bpy.props.StringProperty(name="Concepto", default="") A la hora de definir los operadores se han creado clases como la siguiente, donde se incluye la funci´on a llamar. Se han seguido recursos en l´ınea, optando por seguir la estructura de los tutoriales de Olav3D [3], y de Default Cube [14]. class CURVE_OT_bezier_to_poly(bpy.types.Operator): bl_idname ="curve.bezier_to_poly" bl_label ="To poly" bl_options ={"REGISTER","UNDO"} def execute(self, context): bezier_to_poly() return {"FINISHED"} Para usar los operadores antes definidos, se ha aprendido a usar la estructura habitual en Python, basada en definir las funciones register() yunregister(); en este caso s´olo aparece para el bot´on Bezier to poly, en el resto de botones se ha hecho lo mismo: # register the panel with Blender def register(): bpy.utils.register_class(VIEW3D_PT_my_custom_panel) bpy.utils.register_class(CURVE_OT_bezier_to_poly) def unregister(): bpy.utils.unregister_class(CURVE_OT_bezier_to_poly) bpy.utils.unregister_class(VIEW3D_PT_my_custom_panel) 8. an´ alisis del c´ odigo 141 if __name__ == "__main__": register() Finalmente, para el dise˜no de la UI con la que el usuario final interactuar´a, se ha seguido un curso online de Olav3D [41] que ha permitido poder crear el panel con los botones y la entrada de texto deseada. Para poder usar esa entrada de texto es para lo que previamente definimos la propiedad nombre: class VIEW3D_PT_my_custom_panel(bpy.types.Panel): row =self.layout.row() row.operator("curve.primitive_bezier_curve_add", text="Add Bezier Curve") row =self.layout.row() self.layout.separator() # Agregar una entrada de texto layout.label(text="Intent or Pseudo-Intent:") layout.prop(context.scene, "nombre") row =self.layout.row() row.operator("object.foo", text="foo") self.layout.row() row.operator("curve.create_u_curves", text="Create u-curves") row =self.layout.row() row.operator("object.borrar_objetos", text="Borrar todo") row =self.layout.row() 142 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa row.operator("object.delete", text="Borrar individual") Como menci´on especial, se presenta la parte que permite marcar los conceptos seg´un un intent proporcionado, ya que esta parte result´o ser un reto a la hora de construir elementos geom´etricos con la librer´ıa bpy en base a nuestros datos: def marcar_intervalos(lista_intervalos): # New Collection my_coll =bpy.data.collections.new(f"({bpy.context.scene.nombre})") # Add collection to scene collection bpy.context.scene.collection.children.link(my_coll) bpy.context.object.data.bevel_depth = 0.01 curva_original =bpy.context.object # bpy.context.object.data.bevel_depth = 0.01 # Valor de bevel_depth que se aplicar´a dentro de cada intervalo bevel_depth_deseado = 4 # Color rojo (RGBA) color_rojo =(random(),random(),random(), 1.) # Selecciona la curva original en Blender # Accede a los v´ertices de la curva original vertices_original =curva_original.data.splines[0].points # Itera sobre cada intervalo en la lista for intervalo in lista_intervalos: inicio_intervalo, fin_intervalo =intervalo 8. an´ alisis del c´ odigo 143 # Crea una nueva curva duplicando la original bpy.ops.object.select_all(action='DESELECT') curva_nueva =curva_original.copy() curva_nueva.data =curva_original.data.copy() curva_nueva.name =f"[{inicio_intervalo},{fin_intervalo}]" bpy.context.collection.objects.link(curva_nueva) # Selecciona la curva nueva bpy.context.view_layer.objects.active =curva_nueva curva_nueva.select_set(True) # Cambia al modo de edici´on bpy.ops.object.mode_set(mode='EDIT') # Accede a los v´ertices de la curva nueva vertices_nueva =curva_nueva.data.splines[0].points # Itera sobre los v´ertices en el intervalo especificado y actualiza su bevel_depth for iin range(inicio_intervalo, fin_intervalo + 1): vertices_nueva[i].radius =bevel_depth_deseado # Vuelve al modo de objeto bpy.ops.object.mode_set(mode='OBJECT') # Crea un nuevo material rojo # lo creamos dentro del for para poder marcarlo si se quiere material_rojo =bpy.data.materials.new(name="MaterialRojo") material_rojo.diffuse_color =color_rojo # Asigna el material rojo a la curva nueva if curva_nueva.data.materials: 144 an´ alisis formal de conceptos y aplicaciones a la geometr ´ ıa curva_nueva.data.materials[0]=material_rojo else: curva_nueva.data.materials.append(material_rojo) # Agregamos el objeto de curva a la escena my_coll.objects.link(curva_nueva) bpy.context.collection.objects.unlink(curva_nueva) curva_original.data.bevel_depth = 0.03 Hasta aqu´ı hemos definido las funciones que se han considerado destacables, la implementaci´on del algoritmo y la construcci´on del add-on. 9 Extensi´on a Superficies En este cap´ıtulo se propondr´a una generalizaci´on parcial del algoritmo. Veremos que el algoritmo para curvas sigue siendo efectivo para ciertos tipos de superficies, pero tambi´en veremos que es muy sensible, ya no s´olo a la elecci´on de caracter´ısticas, sino a c´omo se pasar´an los datos de la superficie al algoritmo. De ahora en adelante, todas las superficies que presentemos ya estar´an aproximadas por su superficie multi-reglada poligonal, a menos que se diga lo contrario. Notaci´on: Elementos de R3 P,Q: Puntos de R3. α, β : Curvas de B´ezier. ¯α, ¯ β: Aproximaci´on de las curvas de B´ezier α, β, por poly-curves. Conjuntos relevantes B3: Conjunto de curvas de B´ezier de R3. Π3: Conjunto de poly-curves de R3. Cotas n: N´umero de puntos de control de una curva de B´ezier α. N: N´umero de segmentos de la aproximaci´on ¯α.