Story Transcript
UNIVERSIDAD PONTIFICIA COMILLAS ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA (ICAI) INGENIERO EN INFORMÁTICA
PROYECTO FIN DE CARRERA
t-BUENA ILUMINACIÓN EN EL PLANO
AUTOR: RODRIGO ECHÁVARRI YEPES MADRID, JUNIO DE 2007
Autorizada la entrega del proyecto al alumno: Rodrigo Echávarri Yepes
EL DIRECTOR DEL PROYECTO Santiago Canales Cano
Fdo:
Fecha: .…../….../……
Vº Bº del Coordinador de Proyectos Eduardo Alcalde Lancharro
Fdo:
Fecha: .…../….../…
t-buena iluminación en el plano
“El río anuda al mar su lamento obstinado… …En la infancia de niebla mi alma alada y herida. Descubridor perdido, todo en ti fue naufragio!”… Pablo Neruda
I
t-buena iluminación en el plano
AGRADECIMIENTOS: Ahora, tras tantos caminos hechos, llega por fin la hora de ser conscientes de cómo hemos conseguido lo que una vez nos planteamos.
Los logros nunca se consiguen de manera individual y como en la dirección de una gran orquesta, mi vida siempre ha estado impulsada por dos grandes directores acompañados de una gran solista. Por ello agradezco y quiero hacer partícipes de mis logros a mis padres y de una manera muy especial a mi hermana.
La alegría siempre ha venido de un lado muy concreto, cambian los vientos con ellos, y como en una tempestad incontrolada, mis íntimos amigos siempre me han hecho remolinos de locura. Gracias a todos.
En el plano académico hacer especial mención a la persona que me ha ayudado a que este proyecto se presente. Gracias Santiago Canales, las discusiones geométricas son una salvación causal.
II
t-buena iluminación en el plano
RESUMEN: ¿Cuál es la mejor manera de iluminar una tienda? ¿Cómo iluminar una zona clave para la videovigilancia? ¿Dónde se deben colocar los focos de luz para que los productos estrella del negocio no queden con zonas poco iluminadas? ¿Cómo se puede optimizar la iluminación de una planta industrial con el menor coste?.
Todas ellas son preguntas que debido a la sociedad actual, inmersa en una constante innovación e investigación, pueden ser claves a la hora de optimizar los recursos y ser competitivos en las facetas de costes y de atracción al cliente.
En el presente proyecto se intenta hacer una transferencia tecnológica de unos nuevos conceptos en el estudio de la iluminación. Gracias a los diferentes algoritmos que se implementan, basados todos ellos en La Geometría Computacional, se trata de dar solución a diversos escenarios en lo referente a la iluminación. Teniendo en cuenta la disposición de los focos, en sitios cerrados o con obstáculos que dificulten la propagación de la luz, se debe tener una manera matemática y procedural de poder calcular la calidad de la iluminación.
El planteamiento y objetivo inicial es, además de tener una herramienta de cálculo de la calidad de la iluminación, poder contrastar de una manera fidedigna los resultados obtenidos por los diferentes algoritmos de la t-buena iluminación (entendiendo “t” como una variable que mide la calidad de la iluminación en un punto) desarrollados conceptualmente con los resultados reales de la definición de la t-buena iluminación que a lo largo del proyecto se explicará.
III
t-buena iluminación en el plano
Con dicho planteamiento, se ha desarrollado una herramienta gráfica en lenguaje Java, donde el usuario exponga diferentes escenarios y sea capaz mediante distintos algoritmos calcular las propiedades de iluminación y las regiones iluminadas.
El enfoque final es fundamentalmente llegar a tener una herramienta de investigación útil para los profesionales inmersos en el mundo de las Matemáticas y concretamente La Geometría Computacional. Se obtiene pues un lugar donde los test y las pruebas lleven a comprobar la veracidad o falsedad de los postulados enunciados sobre la calidad de la iluminación.
IV
t-buena iluminación en el plano
ABSTRACT: What would be the best way to iluminate a shop? And a key spot for videosurveillance? Where should the light spots be set in order to avoid placing our business key products in a dark area? How can you optimize the ilumination of an industrial facility with the least cost?
All these questions are product of the society, constantly innovating and investigating, and can be of gret importance when optimizing resources and being competitive in the stage o cost control and custommer winning.
Throughout this project, new ilumination concepts will be transfered to a technological context. Thanks to a group of algorithms that will be implemented, based all in Computational geometry, different scenario illumination problems will be solved. Baring in mind the light spots distribution, in closed spaces or with obstacles that might block the light’s propagation, the application must obtain a mathematical ecuation and a procedure to obtain the quality of the illumination.
The initial objective, in addition to the tool that enables to calculate the quality illumination of a closed space, is to be able to contrast reliably the results obtained by the different algorithms of the t-good illumination (taking ‘t’ as a variable that meassures the quality of the illumination in a spot) developed in a conceptual context with the real results of the definition of t-good illumination that will be explained throughout the project.
Following this approach, a graphic tool has been develoed in Java language, in which the user can create different scenarios and, using different algorithms, calculate the illumination’s properties. V
t-buena iluminación en el plano
The final objective is to implement an investigation tool aimed to professionals from the mathematical world and, more specifically, computational geometry. It will enable us, therefore, to verify the postulates’ enuntiates’ truthness or falseness about the illumination’s quality.
VI
t-buena iluminación en el plano
ÍNDICE:
1.
INTRODUCCIÓN A LA GEOMETRÍA COMPUTACIONAL. .............................................................1 A.
2.
INTRODUCCIÓN A LA VISIBILIDAD. ...............................................................................................................3 INTRODUCCIÓN A LA “T-BUENA ILUMINACIÓN”..........................................................................5
A.
DEFINICIÓN DE “T-BUENA ILUMINACIÓN”. ...................................................................................................6
B.
OBSTÁCULOS EN LA “T-BUENA ILUMINACIÓN”. ...........................................................................................8
C.
REGIÓN “T-BIEN ILUMINADA”. .....................................................................................................................9
3.
CASOS DE ESTUDIO................................................................................................................................10 A.
T-BUENA ILUMINACIÓN DE UNA NUBE DE FOCOS DE LUZ SIN OBSTÁCULOS.................................................10
B.
T-BUENA ILUMINACIÓN EN UN POLÍGONO CERRADO...................................................................................12
C.
T-BUENA ILUMINACIÓN DE UNA NUBE DE FOCOS DE LUZ CON OBSTÁCULOS. ..............................................20
4.
METODOLOGÍA DE DESARROLLO....................................................................................................28
5.
PLANIFICACIÓN TEMPORAL. .............................................................................................................33
6.
RECURSOS A UTILIZAR. .......................................................................................................................34 A.
RECURSOS SOFTWARE. ..............................................................................................................................34
B.
RECURSOS HARDWARE. .............................................................................................................................35
C.
COMUNICACIONES. ....................................................................................................................................36
7.
DISEÑO GLOBAL DEL SOFTWARE. ...................................................................................................37 A.
MODELO DE DOMINIO. ...............................................................................................................................37
B.
DESCRIPCIÓN DEL MODELO DE DOMINIO. ...................................................................................................38
C.
MODELO DE CASOS DE USO. .......................................................................................................................40
VII
t-buena iluminación en el plano
D.
DESCRIPCIÓN DEL MODELO DE CASOS DE USO............................................................................................41
E.
ESTRUCTURA DEL SISTEMA: DIAGRAMA DE PAQUETES..............................................................................63
F.
DESCRIPCIÓN DEL DIAGRAMA DE PAQUETES. .............................................................................................64
8.
DISEÑO GEOMÉTRICO..........................................................................................................................66 A.
9.
DESCRIPCIÓN DEL DIAGRAMA DE CLASES DEL PAQUETE GEOMETRÍA. .......................................................71 DISEÑO DEL INTERFAZ. .......................................................................................................................73
A.
DIAGRAMA DE CLASES DEL PAQUETE INTERFAZ. .......................................................................................74
B.
INTERFAZ.ZONADIBUJO. ............................................................................................................................76
10.
DISEÑO DE LOS ALGORITMOS...........................................................................................................78
11.
ILUMINACIÓN DE UNA NUBE DE FOCOS POR FUERZA BRUTA. ..............................................80
12.
ILUMINACIÓN DE POLÍGONOS POR FUERZA BRUTA.................................................................86
13.
ILUMINACIÓN DE UNA NUBE DE FOCOS CON OBSTÁCULOS POR FUERZA BRUTA. ........93
14.
ILUMINACIÓN DE POLÍGONOS CONVEXOS POR ACHE. ..........................................................100
15.
ILUMINACIÓN DE POLÍGONOS NO CONVEXOS POR ACHE. ...................................................103
16.
ILUMINACIÓN DE UNA NUBE DE FOCOS CON OBSTÁCULO CONVEXO POR ACHE........111
17.
VALORACIÓN ECONÓMICA DEL PROYECTO..............................................................................115
A.
HONORARIOS. ..........................................................................................................................................115
B.
HARDWARE..............................................................................................................................................117
C.
SOFTWARE ...............................................................................................................................................118
D.
PRESUPUESTO TOTAL. ..............................................................................................................................119
18.
CONCLUSIONES.....................................................................................................................................120
19.
BIBLIOGRAFÍA ......................................................................................................................................121
VIII
t-buena iluminación en el plano
20.
GLOSARIO DE TÉRMINOS..................................................................................................................122
ANEXO 1: MANUAL DE USUARIO................................................................................................................127 A.
VENTANA PRINCIPAL ........................................................................................................................128
B.
PANEL LATERAL:................................................................................................................................130
C.
PANEL INFERIOR:................................................................................................................................133
D.
ZONA DE DIBUJO:................................................................................................................................134
E.
PANEL SUPERIOR:...............................................................................................................................135
F.
MENÚ:....................................................................................................................................................138
G.
EJECUCIÓN: ..........................................................................................................................................144
IX
t-buena iluminación en el plano
1. INTRODUCCIÓN A LA GEOMETRÍA COMPUTACIONAL.
En una primera aproximación al campo de desarrollo, se puede entender La Geometría Computacional como la disciplina que se ocupa del diseño y análisis de algoritmos eficientes que resuelven problemas geométricos, donde concurren elementos puramente matemáticos con cuestiones y herramientas de la informática. Es pues, éste un campo muy reciente en el que todavía hay mucho por hacer y cuyas aplicaciones son cada vez más numerosas.
El término “Geometría Computacional” lo introduce M.I. Shamos en el año 1975 aunque en dicha fecha ya existen algunos trabajos previos enmarcados en esta disciplina.
La base fundamental que sustenta La Geometría Computacional es que la potencia de cálculo de los ordenadores hacen resolubles ciertos problemas geométricos hasta la fecha imposibles de solucionar por la gran cantidad de operaciones que se debían realizar. En éstas nuevas reformulaciones de los problemas geométricos, los objetos pasan a ser estructuras de datos, y las metodologías clásicas de resolución de problemas se convierten en algoritmos eficientes que trabajan con dichas estructuras de datos.
En la Figura 1.1 se describen las relaciones que tiene La Geometría Computacional con otras áreas de conocimiento.
1
t-buena iluminación en el plano
GEOMETRÍA CLÁSICA
DESARROLLO HARDWARE
GEOMETRÍA COMPUTACIONAL
ESTRUCTURAS DE DATOS
TÉCNICAS ALGORÍTMICAS
Figura 1.1: Visión global de La Geometría Computacional.
La Geometría Computacional tiene diferentes áreas de aplicación, de las cuales las más significativas son:
o Informática gráfica.
o Reconstrucción de modelos 3D.
o Visión artificial.
o Sistemas de información geográfica.
o Robótica.
o Diseño y fabricación de productos.
o Biología molecular.
o Astrofísica.
2
t-buena iluminación en el plano
a. Introducción a la visibilidad. Uno de los campos más estudiados en la Geometría Computacional es el de la Visibilidad, es decir, el conjunto de problemas que están relacionados con los conceptos de iluminación y vigilancia en su concepción más general. Existe una gran variedad de problemas en este sentido respecto a la zona a iluminar: polígonos convexos, polígonos monótonos, polígonos generales, semiplanos etc., y también respecto a los objetos que iluminan: lucesvértice, luces-punto, luces-lado, etc.
La Visibilidad es una disciplina en la que se combinan la geometría, la informática y la combinatoria y cuyos resultados tienen aplicaciones en multitud de campos como la robótica, planificación de trayectorias, visión por ordenador, gráficos y arquitectura asistida por ordenador.
Básicamente la idea de visibilidad mantiene el concepto clásico del mismo. Dado un conjunto D en Rd se dice que dos puntos x, y pertenecientes a D son visibles en D cuando el segmento que une x e y está completamente contenido en D. El conjunto D se llamará convexo si cualquier par de puntos del mismo se ven. Un conjunto se dice estrellado si existe un punto que ve a todos los demás. El conjunto de puntos con tal propiedad es el núcleo del mismo. Por tanto un conjunto es estrellado si tiene núcleo no vacío.
Se puede entender el concepto de visibilidad de puntos a conjuntos: si U y V son regiones contenidas en D, se dirá que U ve fuertemente a V si todo punto de V es visible desde todo punto de U; se dirá que U ve débilmente a V si todo punto de V es visible desde algún punto de U.
3
t-buena iluminación en el plano
El concepto de visibilidad clásico en el que aparece el segmento que une dos puntos puede generalizarse o variarse cambiando dicho segmento por otros conjuntos. Asimismo una variante importante del concepto de visibilidad es la visibilidad según cadenas de k eslabones, denominada Lk-visibilidad: dos puntos x e y son Lk-visibles en D si existe una poligonal de k lados contenida en D que conecta ambos puntos.
Una parte importante dentro de la Visibilidad es la que se ha venido llamando Galerías de Arte y que se inicia en 1973 con un problema planteado por Víctor Klee: determinar el mínimo número de puntos de un polígono suficientes para ver a todos los demás. Considerando el polígono como planta de una galería de arte y los puntos buscados como guardias o focos, se tiene el nombre de esta importante rama de la Geometría Computacional. Chvátal obtiene la primera respuesta en 1975: [n/3] es el número de guardias a veces necesarios y siempre suficientes para iluminar un polígono P con n vértices. Este resultado se conoce como Teorema de Galerías de Arte y el primer tratado monográfico fue presentado por O’Rourke en 1987.
Por tanto [n/3] luces son siempre suficientes para iluminar un polígono P de n vértices, pero en muchas ocasiones basta con menos. Así tiene sentido plantear el problema algorítmico siguiente: dado un polígono calcular el mínimo número de luces que lo vigilan. Este problema fue estudiado por Lee y Lin.
4
t-buena iluminación en el plano
2. INTRODUCCIÓN A LA “t-BUENA ILUMINACIÓN”.
Uno de los principales problemas que La Geometría Computacional se había encontrado, en su afán por la investigación en los conceptos de iluminación y vigilancia para la resolución de problemas de ingeniería y la física, era que los resultados hasta ahora obtenidos no reflejaban totalmente circunstancias reales, y por tanto no eran normalmente aplicables.
En el intento de buscar unas definiciones más próximas a la realidad en los campos de iluminación y vigilancia, se define el concepto de t-buena iluminación.
La idea de la que parten los postulados de la t-buena iluminación son las de estudiar la iluminación y la calidad de la misma en puntos y áreas del espacio bidimensional, para poder así tener unos conceptos claros de las propiedades de iluminación.
En el mundo real, a la hora de iluminar cualquier cuerpo, no sólo es trascendental el número de focos que lo están iluminando, sino que de una manera significativa, la disposición que tienen los focos que iluminan al cuerpo, determina la calidad de su iluminación [CANA04]. Intuitivamente, un objeto no está bien iluminado si todos los focos que lo iluminan están agrupados a “un lado” del objeto, es decir, si no están en cierta medida bien distribuidos alrededor del objeto. Las siguientes dos figuras muestran dos situaciones claras de este concepto:
5
t-buena iluminación en el plano
Figura 2.1: Mala distribución de los focos.
Figura 2.2: buena distribución de los focos.
De ésta manera, la figura 2.1 tiene una mala distribución de los focos, y por tanto la calidad del punto iluminado en dicho ejemplo es bastante mala. En contraposición, en la figura 2.2 los focos que iluminan al punto se encuentran correctamente distribuidos alrededor de dicho punto, por lo que se dice que la calidad de su iluminación es buena. Se considera pues la siguiente variación del concepto de visibilidad: Un punto p está tbien iluminado por un conjunto de luces o focos F, si cada semiplano con borde en x contiene al menos t elementos de F visibles desde el punto p [CANA04].
a. Definición de “t-buena iluminación”. Sea F = {f1, f2, …., fk} un conjunto de k luces o focos en el plano, y O un conjunto de obstáculos. Un punto p está t-bien iluminado por L, 1≤t≤k/2, si todo semiplano con borde en p contiene al menos t focos de L que lo iluminan [CANA04].
6
t-buena iluminación en el plano
Figura 2.a.1: Punto 1-bien iluminado.
De ésta manera, en la figura 2.a.1 el punto representado está 1-bien iluminado (la variable de iluminación t tiene valor 1), ya que si se pasa por el punto de iluminación los infinitos hiperplanos que lo contienen (marcados algunos de ellos en rojo), los dos semiplanos en que se divide el espacio bidimensional, contienen como mínimo un foco de luz que iluminan al punto.
Semiplano sin ningún foco de luz
Figura 2.a.2: Punto no bien iluminado.
7
t-buena iluminación en el plano
Como ejemplo de elementos de calidad de iluminación mala, en la figura 2.a.2 el punto iluminado tiene una calidad de iluminación mala, ya que se puede encontrar un semiplano que pase por dicho punto que no tiene focos de luz en uno de sus lados. Con el corte de semiplanos, se pueden encontrar zonas del elemento a iluminar que se encuentran en sombra, y por tanto se pueden determinar que no está bien iluminado.
b. Obstáculos en la “t-buena iluminación”. En la definición de la t-buena iluminación, se ha introducido el concepto de obstáculo. Un obstáculo es todo aquel elemento geométrico en el espacio bidimensional que se encuentre entre la trayectoria o línea de visión (recta) entre un foco y un punto que se quiere iluminar, que impida que el haz de luz del foco llegue al punto de iluminación. Los obstáculos en la iluminación juegan un papel decisivo ya que son elementos que impiden que los puntos puedan ser iluminados por ciertos focos.
f2
p1
p2
obstáculo f1
f3
Figura 2.b.1: Obstáculo que modifica propiedades de t-buena iluminación.
8
t-buena iluminación en el plano
La figura 2.b.1 muestra tres focos de luz (f1, f2, f3) dos puntos de iluminación (p1 y p2) y un obstáculo. Se puede observar que el punto p1 sigue manteniendo la 1-buena iluminación (según la definición que se citó anteriormente), pero el punto p2 no, ya que el obstáculo dibujado se encuentra entre la línea de visión de f1 y p2, por lo que f1 no ilumina a p2 y se puede trazar al menos un semiplano que pase por p2 y no contenga ningún foco en uno de sus dos lados.
c. Región “t-bien iluminada”. Al conjunto de los infinitos posibles puntos del plano t-bien iluminados por los focos F, en presencia de un conjunto de obstáculos O, se le denominará región t-bien iluminada por F con respecto a O, y su notación será Wt (F,O). Dicha región evidentemente puede ser no conexa debido a la existencia de obstáculos, y por lo tanto, se hablará indistintamente de las regiones o la región t-bien iluminada por un conjunto F de focos. Está demostrado que si el conjunto O de obstáculos es vacío o ningún obstáculo intersecta al CH (F) (Convex Hull (F) o Cierre Convexo de (F)), entonces la región Wt (F,O) es siempre conexa y convexa [CANA04].
9
t-buena iluminación en el plano
3. CASOS DE ESTUDIO.
El objetivo que se intenta alcanzar con este proyecto, es el de desarrollar una herramienta informática de estudio y análisis en el campo de La Geometría Computacional anteriormente explicado: La t-buena iluminación.
Para realizar dicha herramienta, se plantean diferentes casos de estudio, según la utilización de los elementos posibles: focos de luz sin obstáculos, polígonos cerrados y focos de luz con obstáculos.
a. t-buena iluminación de una nube de focos de luz sin obstáculos. El primer caso de estudio es el cálculo de regiones de buena iluminación en el espacio bidimensional con una nube de focos colocados en él.
En dicho caso, si no hay obstáculos, o los obstáculos no intersectan al cierre convexo de F, CH (F), la región t-bien iluminada coincidirá con el nivel de profundidad t del conjunto F, (también llamados niveles de profundidad de Tukey, (depth levels). [CANA04], [TUKE75].
10
t-buena iluminación en el plano
Figura 3.a.1: 1-buena iluminación de nube de focos.
En la figura 3.a.1 se muestra la región 1-bien iluminada de los 8 focos existentes en el plano. Como se puede observar, y de acuerdo con el primer nivel de profundidad del conjunto F de focos, la región 1-bien iluminada sin obstáculos coincide exactamente con el área inscrita en el cierre convexo, CH (F), de dicho conjunto de focos.
Figura 3.a.2: 2-buena iluminación de nube de focos.
Figura 3.a.3: 3-buena iluminación de nube de focos.
11
t-buena iluminación en el plano
Las figuras 3.a.2 y 3.a.3 muestran las regiones 2-bien y 3-bien iluminadas respectivamente, del conjunto de los 8 focos anteriores. En dichos ejemplos, las zonas resultantes corresponden con los niveles de profundidad 2 y 3. También se observa que, como se dijo antes, las regiones bien iluminadas son siempre conexas y convexas ante la inexistencia de obstáculos en el CH (F). El estudio de la nube de focos en el plano se realiza únicamente por un algoritmo de fuerza bruta, haciendo un barrido de todo el plano y estudiando, punto por punto, las propiedades de cada uno de ellos en lo que a buena iluminación se refiere. Las especificaciones de dicho algoritmo se pueden consultar en el CAPÍTULO 10.
Con dicho algoritmo se podrá estudiar hasta una iluminación de t = 6, pudiendo mostrar los resultados simultáneamente o sólo mostrando una región determinada concerniente a una t especificada.
b. t-buena iluminación en un polígono cerrado. En este segundo caso se considera un polígono P cerrado, con un foco situado en cada uno de sus vértices {v1, v2, …, vn}. Se desea calcular las regiones interiores de P t-bien iluminadas por esos focos. En la resolución de éste problema se toman dos diferentes perspectivas dependiendo de si el polígono P que se está estudiando es un polígono convexo o no.
12
t-buena iluminación en el plano
i. Polígono convexo. Se plantea la búsqueda de un algoritmo para la región t-bien iluminada por un conjunto F de focos situados en los vértices de un polígono convexo, para lo cual es preciso tener en cuenta las dos siguiente siguientes consideraciones: 1. Si P es un polígono convexo de vértices V = {v1, v2, …, vn} y r pertenece a los números enteros naturales tal que 0≤r≤n, llamado r-núcleo de P y se designa por Kerr (P) al conjunto
Kerr (P) =
CH (V \ {v1 ,..., vn }) I {i 1 ,..., in }
donde la intersección recorre los subconjuntos de r elementos de {1, …, n} y CH (A) indica el cierre convexo de A [ABEL92].
Según la definición anterior, la región t-bien iluminada en el interior de un polígono convexo se puede calcular como el Ker
t-1
(P), o lo que es lo
mismo, con la intersección de los cierres convexos. Un punto x de un polígono P está t-bien iluminado por los vértices de P sí y solo sí está contenido en el semiplano de borde vi vi+t que no contiene a vi+1 par todo i = 1, 2, …, n [CANA04].
2. Sea P un polígono convexo con n vértices {v1, v2, …, vn}. La región t-bien iluminada por n focos situados en los vértices de P es Ker t-1 (P) [CANA04].
13
t-buena iluminación en el plano
Figura 3.b.1: 2-buena iluminación de un polígono por intersección de cierres convexos.
La figura 3.b.1 muestra cómo se ha calculado la región 2-bien iluminada del polígono convexo por la intersección de los cierres convexos. La zona pintada en rosa representa la región 2-bien iluminada, es decir, todos los puntos contenidos en esa región están contenidos en el semiplano de borde vi vi+2 que no contiene a vi+1 para todo i = 1, 2, …, n.
En el cálculo, la aplicación será capaz de calcular las regiones t-bien iluminadas hasta un valor de la variable t máximo de 6, y de dos maneras diferentes.
La primera forma de cálculo es un algoritmo de fuerza bruta que hace un barrido completo del plano, identificando la t-buena iluminación de todos los puntos para así calcular las diferentes regiones t-bien iluminadas. Dicho algoritmo viene explicado en el CAPÍTULO 11. Con dicho algoritmo se podrá estudiar hasta una iluminación de t = 6, pudiendo mostrar los
14
t-buena iluminación en el plano
resultados para diferentes valores de t o sólo mostrando una región determinada concerniente a una t especificada.
La segunda forma de cálculo se basa en las teorías de cierres convexos enunciadas anteriormente: algoritmo “ACHE”, explicado en el CAPÍTULO 13.
La complejidad de resolver dicho problema con el algoritmo “ACHE” es de Θ(n).
ii. Polígono no convexo. Si el polígono P no es convexo, el cálculo de las regiones bien iluminadas cambian en gran medida con la resolución de polígonos convexos.
Para dicho caso, se van a estudiar las regiones t-bien iluminadas con t=1 y t=2 con el algoritmo denominado ACHE, y hasta un valor de t=6 para el algoritmo de fuerza bruta.
En el caso de t = 1 para el algoritmo ACHE, la región 1-bien iluminada es la región interior al polígono.
En el caso de t = 2 para el algoritmo ACHE, el método de resolución se basa en dos pasos consecutivos:
1. El primer paso se basa en los algoritmos de cierres convexos ya explicados. Si al realizar el cierre convexo de los vértices vi y vi+2, dichos vértices no son visibles mutuamente, es necesario calcular el camino geodésico que une dichos vértices por el interior del polígono P. Los puntos de la región poligonal Hi determinados por vi, vi+1, vi+2 y el camino geodésico entre vi y 15
t-buena iluminación en el plano
vi+2 no están bien iluminados, por lo que dicha región no pertenecerá a la región 2-bien iluminada. La imagen siguiente muestra dicho caso.
Figura 3.b.2: Región Hi no 2-bien iluminada.
2. El
segundo paso a realizar está directamente relacionado con todos los
vértices cóncavos del polígono P no convexos. Cada uno de dichos vértices tiene asociado un par de triángulos situados a ambos lados, que podrían haber sido parcial o totalmente considerados como zonas 2-bien iluminadas en el primer paso. Es pues necesario, calcular dichos triángulos y eliminarlos de la región 2-bien iluminada calculada anteriormente.
Figura 3.b.3: Triángulos asociados a los vértices cóncavos.
16
t-buena iluminación en el plano
Por cada arista s incidente en el vértice cóncavo x, se elimina una zona no 2-bien iluminada construida del siguiente modo: Prolongando el lado ax hacia el interior del polígono cortará a un lado de P en un punto t. Girando los segmentos at con centro en a y xt con centro en x y en sentidos contrarios, se encuentran los primeros vértices visibles en ambos casos, que se llamarán i y j respectivamente. Si se calcula ahora el punto de intersección d de las rectas xj y ai, se puede construir el triángulo Δ(adx) que es una región no 2-bien iluminada. Lo mismo hay que hacer para el otro vértice incidente en x [CANA04].
Calculando las regiones Hi para cada vértice i, los triángulos asociados a los vértices cóncavos, se tiene la región 2-bien iluminada interior a un polígono P no convexo (ver figura 3.b.4).
Figura 3.b.4: Región 2-bien iluminada de un polígono no convexo.
17
t-buena iluminación en el plano
De una manera formalizada, el algoritmo ACHE de 2-buena iluminación de un polígono no convexo es el siguiente.
___________________________________________________________________________ Algoritmo de 2−buena iluminación en un polígono no convexo
ENTRADA: Un polígono P con n vértices y un conjunto F = {f1, ..., fn} de n focos situados en los vértices de P.
SALIDA: La región 2−bien iluminada en el interior de P por F, W2 (F,P).
1. Construcción de las regiones Hi. Para cada vértice “i” se trazan las diagonales correspondientes al camino geodésico mínimo desde i al vértice “i” + 2. La región comprendida entre el camino y el vértice “i” + 1 no está 2−bien iluminada.
2. Construcción de triángulos asociados a lados cóncavos. Por cada arista “ax” incidente en el vértice cóncavo “x” se elimina una zona no 2−bien iluminada construida del siguiente modo: Prolongando el lado “ax” hacia el interior del polígono cortará a un lado de P en un punto “t”. Girando los segmentos “at” con centro en “a” y “xt” con centro en “x” y en sentidos contrarios, se encuentran los primeros vértices visibles en ambos casos, que se llamarán “i” y “j” respectivamente. Si se calcula el punto de intersección “d” de las rectas “xj” y “ai”, se puede construir el triángulo “Δ(adx)” que es una región no 2-bien iluminada.
3. Eliminación de las regiones no 2−bien iluminadas. Eliminar de P las regiones Hi construidas en el Paso 1 y los dos triángulos adyacentes a cada vértice cóncavo de P, construidos en el Paso 2. ____________________________________________________________________________ 18
t-buena iluminación en el plano
Los algoritmos de resolución implementados para este caso son dos: 1. La primera forma de cálculo es un algoritmo de fuerza bruta que, como en otros casos de estudio anteriores, hace un barrido completo del plano, identificando la t-buena iluminación de todos los puntos para así calcular las diferentes regiones t-bien iluminadas. Dicho algoritmo viene explicado en el CAPÍTULO 12. Con dicho algoritmo se podrá estudiar hasta una iluminación de t = 6, pudiendo mostrar los resultados simultáneamente o sólo mostrando una región determinada concerniente a una t especificada. 2. La segunda forma de cálculo se basa en los dos pasos para la resolución, anteriormente descritos: algoritmo “ACHE”, explicado en el CAPÍTULO 15.
En el estudio de la complejidad del algoritmo “ACHE” para este caso, en primer lugar el coste computacional de cálculo de un camino geodésico es lineal. Por tanto el trazado de todas las diagonales se realiza en O (n2). Para la construcción de los triángulos a eliminar, se necesitan ordenar todos los vértices respecto de todos para encontrar i y j ( coste O (n2)), más la obtención del punto t, (coste O (n)) y el cálculo de los triángulos que se realiza en tiempo constante para cada lado, es decir, O (n2) en total. Finalmente se debe recortar todos los triángulos con el polígono resultante de eliminar todas las regiones Hi de P. Esto puede hacerse en O (n) para cada triángulo, lo que produce un coste final para todos los triángulos de O (n2) [CANA04].
19
t-buena iluminación en el plano
c. t-buena iluminación de una nube de focos de luz con obstáculos. Como último caso de estudio, se consideran una serie de focos de luz distribuidos en el plano y un obstáculo convexo que dificulta la iluminación. Se trata de calcular las distintas regiones t-bien iluminadas del plano teniendo en cuenta que los obstáculos impiden la propagación de la luz a través de ellos. De ésta manera las regiones bien iluminadas pueden ser no conexas, y a diferencia del caso de nube de focos sin obstáculos, dichas regiones también pueden no ser convexas.
Se trata de calcular la zona 1-bien iluminada por k focos exteriores a un obstáculo convexo. El algoritmo que calcula la región 1-bien iluminada, se divide en varios pasos:
1. Determinar las cuñas que producen la prolongación de los lados del convexo y estudiar los focos que pertenecen a cada cuña. Dicho paso se debe realizar tanto en las cuñas hacia la derecha como hacia la izquierda (es decir, cuando se recorre C en sentido derecho e izquierdo).
Figura 3.c.1: Preproceso de ordenación por cuñas.
20
t-buena iluminación en el plano
2. Cálculo de una zona poligonal A, que es la unión de los cierres convexos dinámicos de los subconjuntos de los focos F linealmente separados de C. Para ello se apoya una recta t en el obstáculo y se hace girar en sentido negativo, construyendo dinámicamente la unión de los cierres convexos que irán apareciendo en sentido negativo y desapareciendo en sentido positivo.
Figura 3.c.2: Zona poligonal A de unión de cierres convexos.
3. Hay que completar la región A calculada con determinados sectores internos de buena iluminación Si que no formaban parte de la unión de cierres convexos. Dichos sectores forman parte de la región 1-bien iluminada, pero son fruto de la iluminación de dos vértices que no se ven entre sí, y que por lo tanto no estaban incluidos en los cierres convexos calculados antes. Para ello, hay que, para cada foco fi, construir su recta soporte ri con el obstáculo C y girarla alrededor del obstáculo hasta encontrar el primer foco fj que aparezca. Se construye la recta rj de soporte del foco calculado, y a continuación se añade el sector Si a la zona bien iluminada A. 21
t-buena iluminación en el plano
Ejemplo 3.c.3: Sector interno Si.
De ésta manera ya se tiene calculada la zona 1-bien iluminada de una nube de focos con un obstáculo convexo.
8º / 1º 7º / 3º
9º / 2º
1º / 9º 2º / 8º 3º/ 7º
6º / 4º 5º/ 5º 4º// 6º 4º
Figura 3.c.4: Región 1-bien iluminada con un obstáculo convexo.
22
t-buena iluminación en el plano
El algoritmo de 1-buena iluminación en el plano con un obstáculo convexo es el siguiente:
____________________________________________________________________________
Algoritmo de 1−buena iluminación para un obstáculo convexo.
ENTRADA: Un polígono convexo C con n vértices y un conjunto F = {f1, ..., fn} de n focos exteriores a él.
SALIDA: La región 1−bien iluminada por F, W1 (F,C).
1. Preproceso: Determinar las cuñas que producen la prolongación de los lados del convexo y estudiar los focos que pertenecen a cada cuña. Este preproceso se debe realizar tanto en las cuñas hacia la derecha como en las cuñas hacia la izquierda.
2. Cálculo: El algoritmo consta de dos partes. La primera de ellas consiste en el cálculo de una zona poligonal A, que es la unión de los cierres convexos dinámicos de los subconjuntos de F linealmente separados de C. La segunda parte consiste en completar A con sectores internos de buena iluminación Si, que no aparecen en la unión de los cierres convexos. Así, la zona bien iluminada por los focos de F = {f1, f2, ..., fk} será A Uk Detalladamente estos son los pasos de esta parte de cálculo.
(a) Construcción del primer convexo:
- Trazar una recta t que contiene a un lado cualquiera de C.
- Construir el cierre convexo de todos los puntos exteriores a t.
23
i=1
Si.
t-buena iluminación en el plano
(b) Cálculo de A. Unión de los cierres convexos dinámicos:
- Girar en sentido negativo la recta t y construir de forma dinámica la unión de los cierres convexos que irán apareciendo en sentido negativo y desapareciendo en sentido izquierdo.
(c) Completar con sectores internos Si:
- Para cada foco fi construir su recta soporte ri a C.
- Girar ri en sentido negativo alrededor de C hasta encontrar el primer foco que aparece, fj.
- Calcular lar recta soporte rj de fj a C. - Hallar el sector Si y unirlo a la zona bien iluminada A.
____________________________________________________________________________
En el cálculo de este último caso, la aplicación será capaz de calcular las regiones t-bien iluminadas de dos maneras diferentes.
1. La primera forma de cálculo es un algoritmo de fuerza bruta que hace un barrido completo del plano, identificando la t-buena iluminación de todos los puntos para así calcular las diferentes regiones t-bien iluminadas. Con este algoritmo, se pueden utilizar varios obstáculos incluso no convexos, y las regiones que se pueden calcular son hasta t=6. Dicho algoritmo viene explicado en el CAPÍTULO 13.
24
t-buena iluminación en el plano
Figura 3.c.5: Regiones bien iluminadas con obstáculos por fuerza bruta.
2. La segunda forma de cálculo se basa en los pasos antes enunciados. El denominado algoritmo “ACHE”, sirve para un solo obstáculo convexo, y se calculará únicamente la región 1-bien iluminada. Dicho algoritmo viene explicado en el CAPÍTULO 16.
La complejidad de dicho algoritmo es O ( k (log n + log k) + n ) para el cálculo de la región 1-bien iluminada, donde n es el número de vértices del obstáculo convexo. Este algoritmo precisa de un proceso que ordene angularmente los focos alrededor del convexo con un coste computacional de O (k log k) [CANA04].
25
t-buena iluminación en el plano
Como una opción adicional para todos los algoritmos de fuerza bruta, se puede especificar una distancia máxima a la que la iluminación de un foco llega, que por defecto es total. Si se especifica dicha distancia máxima, la luz llegará únicamente a un radio máximo de dicha longitud.
Figura 3.1: 1-buena iluminación de nube de focos con distancia máxima.
Los algoritmos ACHE en los diferentes casos de uso en los que se va a utilizar, tendrán tres modos de ejecución: 1-
Ejecución simple: El algoritmo se ejecutará sin interrupción y únicamente mostrará sus resultados una vez finalizado.
2-
Ejecución retardada: A cada operación que realiza el algoritmo relacionada con los pasos necesarios antes descritos, hará una pausa temporal especificada por el usuario mostrando los datos hasta dicho momento
26
t-buena iluminación en el plano
calculados y con el apoyo de objetos auxiliares como rectas para una mejor comprensión del usuario. 3-
Ejecución paso a paso: Es muy similar a la ejecución retardada, pero la ejecución no se reanudará hasta que el usuario no lo indique.
27
t-buena iluminación en el plano
4. METODOLOGÍA DE DESARROLLO.
Para abordar el estudio y desarrollo del sistema, se optará por un modelo de ciclo de vida denominado “Prototipado Evolutivo”. Dicho ciclo de vida se basa en sucesivas iteraciones de las cuales se tienen consecutivamente versiones del Software deseado. La elección de este modelo de desarrollo se debe fundamentalmente a:
o Al tratarse de un desarrollo de unos conceptos puramente teóricos, es deseable obtener una primera versión de lo que es el programa tan pronto como sea posible a fin de obtener unos resultados de las teorías enunciadas y contrastar las soluciones de la herramienta.
o Para definir claramente qué es lo que se quiere e incorporar así sugerencias a los cambios necesarios tan pronto como sea posible, es decir, en las etapas tempranas de la construcción.
o El ciclo de vida de “Prototipado Evolutivo” es también muy útil para saber lo antes posible si los desarrolladores están interpretando correctamente las especificaciones y necesidades del usuario, así como los conceptos clave del problema de la buena iluminación que se está tratando.
o La emisión de prototipos es muy favorable a la hora de posibilitar refinamientos en los requerimientos y especificaciones de la herramienta software, a fin de conseguir lo que se desea.
28
t-buena iluminación en el plano
o Se favorece de esta manera la realización de cambios en etapas tempranas y de este modo se evalúa progresivamente el prototipo durante el desarrollo.
Las distintas fases que se van a abordar en el ciclo de vida de “Prototipado Evolutivo”, responden a las versiones sucesivas que se presentarán de la herramienta software.
Gracias a unas descripciones iniciales informales que de manera sucesiva se refinan y revisan, se llegan a unas especificaciones formales de evolución de la herramienta con las que se hace el desarrollo incremental. Dicho desarrollo tiene que pasar por una etapa de validación que contraste los resultados obtenidos de la herramienta con lo que se quiere lograr contrastando con las diferentes teorías de la t-buena iluminación. El desarrollo se puede representar según la figura 4.1
Descripción informal
Especificación
Versión inicial
Desarrollo
Versiones intermedias
Validación
Versión final
Figura 4.1: Metodología de “Prototipado Evolutivo”.
29
t-buena iluminación en el plano
Esta metodología es sin duda la que mejor se adapta a las características de este proyecto. En cada iteración, las etapas de construcción de un nuevo prototipo son:
Definición
Análisis
Diseño
Construcción
Validación
Figura 4.2 Etapas de construcción de prototipos.
Los grupos de iteraciones identificados a priori son:
1.
Introducción y estudio del Sistema: Para poder implementar los algoritmos de iluminación, el desarrollador debe hacer una primera fase que se centre en el estudio de los principios básicos de La Geometría Computacional, profundizando en aquellos puntos concernientes a la iluminación y t-buena iluminación. Será necesario asimilar los conceptos naturales de la geometría básica y trigonometría así como los modelos de algoritmos de resolución.
30
t-buena iluminación en el plano
2.
Modelo global del sistema: Hecha ya una aproximación al Universo de discurso, se trata de hacer un primer modelo de trabajo en el que se identifiquen las necesidades generales, modelos de los conceptos a utilizar, usos de la herramienta, etc.
3.
Modelo geométrico y de visualización: El objetivo principal en esta fase es proporcionar el soporte del lenguaje de programación necesario para acometer el cálculo de los algoritmos en las diferentes casuísticas. Se trata de hacer una estructura robusta en la representación gráfica 2D así como un modelo completo para la representación conceptual de los modelos geométricos (punto, segmento, polígono, foco, obstáculo, …).
4.
Modelo y soluciones de los problemas de t-buena iluminación: La última parte del proyecto se centra en el desarrollo computacional e implementación de los algoritmos de obtención de la t-buena iluminación.
Quedan pues definidos los cuatro grandes grupos de iteraciones a realizar. Cada uno de ellos tendrá internamente diferentes evoluciones y prototipos, al abarcar grandes áreas del proyecto. Por ejemplo en el último grupo existirá un nuevo prototipo por cada algoritmo implementado.
Los 4 grandes grupos están interrelacionados entre sí, ya que el desarrollo de uno depende en gran medida de los resultados obtenidos de los anteriores. A continuación se representa en la figura 4.3 la relación de cada grupo.
31
t-buena iluminación en el plano
Estudio del sistema
Modelo global
Modelo geométrico y de visualización Solución problemas t-buena iluminación
Figura 4.3: Relaciones entre fases del desarrollo.
El desarrollo de los grupos tres y cuatro están muy ligadas entre sí, aunque el tercero tiene que ser anterior al cuarto, hay partes de sus desarrollos que están íntimamente ligados y por consiguiente se harán ciertas iteraciones del “Prototipado Evolutivo” en paralelo.
La herramienta para llevar a cabo el diseño de la aplicación será UML 2.0, tanto para los diferentes Modelos de Dominio, Modelos de Casos de Uso, Diagramas de Clases, etc.
32
t-buena iluminación en el plano
5. PLANIFICACIÓN TEMPORAL.
Distribuidas a lo largo de 8 meses de desarrollo, las actividades han sido desarrolladas en los siguientes periodos de tiempo.
2006 Noviembre Diciembre
2007 Febrero
Marzo
Abril
Mayo
Estudio del sistema Modelo global Modelo geométrico y de visualización Algoritmos t-buena iluminación Documentación
La gestión acompaña a toda la duración del proyecto, mientras que la documentación se ha empezado a elaborar cuando ya se había avanzado en él.
33
t-buena iluminación en el plano
6. RECURSOS A UTILIZAR.
En el desarrollo del proyecto han sido necesarios diferentes recursos específicos, teniendo así diferentes soportes tanto Hardware como Software, que ayudarán a finalizar con éxito el proyecto.
a. Recursos Software. El proyecto consiste en obtener una herramienta desarrollada en Java, para la ejecución de la aplicación en diferentes equipos. Para ello se han utilizado los siguientes recursos software:
•
Sistema operativo Windows XP Professional:
•
Microsoft Office 2003: Utilizado fundamentalmente para la documentación.
•
Java S.E Runtime Environment 6: Lenguaje de ejecución, utilizando la Java Virtual Machine.
•
Java S.E. Development Kit 6: Lenguaje de desarrollo y programación. 34
t-buena iluminación en el plano
•
Netbeans 5.5: Entorno de desarrollo en el que se programará y se diseñará la interfaz final de la aplicación.
•
Acrobat Professional 7.0: Utilizado para leer documentos específicos de apoyo al desarrollo y para la creación de la documentación.
•
Visual Paradigm Project 6.0: Herramienta de creación de los diferentes diagramas UML.
b. Recursos Hardware. Para el desarrollo del proyecto se necesita irremisiblemente un soporte Hardware. El Hardware que se va a utilizar será un ordenador personal portátil Dell Latitude D-610 con las características siguientes:
- Procesador Intel Centrino 1.6, 2 MB de caché L2. - 512 MB de R.A.M. - 60 GB de Disco Duro.
35
t-buena iluminación en el plano
c. Comunicaciones. Adicionalmente se va a disponer de un sistema de comunicaciones para la búsqueda y consulta de documentación para el desarrollo del sistema. Dicho sistema de comunicaciones es una línea ADSL de 2Mb de ancho de banda.
36
t-buena iluminación en el plano
7. DISEÑO GLOBAL DEL SOFTWARE.
En el presente capítulo, se van a representar las bases del diseño del Software. Utilizando la notación UML 2.0, el diseño del Software tiene los siguientes apartados:
a. Modelo de dominio. El modelo de dominio siguiente muestra las entidades fundamentales de estudio y desarrollo geométrico para realizar los diferentes casos de estudio.
Figura 7.a.1: Modelo de dominio.
37
t-buena iluminación en el plano
b. Descripción del modelo de dominio. El modelo de dominio representado en la figura 7.a es una primera aproximación al Universo de discurso. En dicho modelo de dominio se representan las relaciones entre entidades y conceptos de los elementos fundamentales del estudio, que son:
o FocoLuz: Es la clase que representa aquellos puntos en el espacio bidimensional que se corresponden con focos de luz. Dichos focos de luz iluminan los elementos visibles y tienen asociado una degradación de luz, que es la máxima distancia a la que pueden iluminar. Dicha distancia por defecto es infinita, es decir, iluminan todo el espacio bidimensional.
o Polígono: Clase que representa aquellos cierres que tienen asociados a cada vértice un foco de luz, anteriormente descritos. Los polígonos están pues construidos por líneas que unen los vértices consecutivos y siempre son cerrados. Tienen ciertas características similares a los obstáculos del espacio bidimensional y para compartir dichas características, heredan las propiedades de otra clase denominada “Cierre”. Debido a que un polígono tiene como vértices focos de luz, el polígono en la región que delimita tendrá asociadas una serie de regiones de t-buena iluminación, por lo que está relacionada con la clase “RegionTBuenaIluminación” detallada más adelante.
o Obstáculo: Clase que representa aquellos elementos existentes en el espacio bidimensional que impiden la propagación de luz de los focos antes descritos. Los obstáculos están definidos como cierres por lo que heredan todas las propiedades de la clase “Cierre”.
38
t-buena iluminación en el plano
o RegionTBuenaIluminación:
Corresponde
con
una
región
del
espacio
bidimensional de t-buena iluminación, es decir, representa todos aquellos puntos del espacio bidimensional que están t-bien iluminados por una serie de focos de luz.
o Espacio Bidimensional: Es la representación conceptual de todos aquellos elementos que se encuentran en el plano representado. Dicha representación, tiene asociado una serie de focos de luz, de polígonos y de obstáculos, que son los que serán susceptibles de representación y de estudio. Como dicho espacio de estudio es único, sólo puede haber una instancia del concepto, que se implementará, como se verá más adelante, con el patrón de diseño “singleton”. Adicionalmente puede tener asociado una imagen de fondo a representar.
Como se puede observar, dicho modelo de dominio hace referencia únicamente a los elementos geométricos y es concerniente a la segunda iteración del desarrollo software, para crear un modelo global del sistema.
39
t-buena iluminación en el plano
c. Modelo de casos de uso.
Figura 7.b.1: Modelo de casos de uso.
40
t-buena iluminación en el plano
d. Descripción del modelo de casos de uso.
La aplicación interactúa únicamente con el usuario que la maneje, por lo que sólo es utilizada por un actor principal, que a partir de ahora se denominará Usuario.
Usuario: Toda aquella persona que maneje en un momento determinado el sistema a través de su interfaz gráfico.
Los casos de uso definidos son los siguientes: o Crear foco de luz: El Usuario podrá definir y dibujar los focos de luz necesarios en el plano. o Crear obstáculo: En este caso, el Usuario puede crear obstáculos en el plano que impidan la propagación de la luz de los focos. o Crear polígono: El Usuario podrá definir los polígonos de estudio en el plano, tanto convexos como polígonos con vértices cóncavos. Dichos polígonos tendrán en cada uno de sus vértices un foco de luz asociado. o Cálculo de regiones de t-buena iluminación con focos de luz: Con dicho caso de uso, el Usuario interacciona con el Sistema para la resolución del primer caso de estudio definido. Se trata del cálculo de las diferentes regiones bien iluminadas en el plano por una serie de focos de luz sin ningún obstáculo.
41
t-buena iluminación en el plano
o Cálculo de regiones de t-buena iluminación para polígonos convexos: Trata de la resolución del segundo caso de estudio: dado una serie de polígonos convexos definidos en el plano, calcular las regiones t-bien iluminadas interiores asociadas a cada uno de dichos polígonos convexos. o Cálculo de regiones de t-buena iluminación para polígonos no convexos: Trata de la resolución del segundo caso de estudio: dado una serie de polígonos no convexos definidos en el plano, calcular las regiones 1 y 2-bien iluminadas interiores, asociadas a cada uno de dichos polígonos no convexos. o Regiones de t-buena iluminación para nubes de focos de luz con obstáculos: Trata de la resolución del último caso de estudio de t-buena iluminación; dada una nube de focos de luz en el plano y una serie de obstáculos que modifican la propagación de la iluminación de dichos focos, encontrar las diferentes regiones t-bien iluminadas en el plano. o Configuración de degradación de luz: Una de las características de los focos de luz que interviene directamente en el cálculo de las regiones t-bien iluminadas, es la máxima distancia de propagación de su luz. Definida por defecto dicha distancia como infinita, es posible definir nuevos alcances máximos de los focos de luz con éste caso de uso. o Borrar panel de dibujo: En la tónica general de resolución de problemas es posible que sea necesario borrar los elementos creados en el espacio bidimensional para un nuevo estudio. Con éste caso de uso, el Usuario podrá borrar todos los elementos anteriormente definidos.
42
t-buena iluminación en el plano
o Cargar imagen de fondo: El Usuario puede de manera opcional cargar una imagen como fondo en La Zona de Dibujo para su estudio de iluminación. o Guardar resultados: Se trata de dar la posibilidad al Usuario de guardar los resultados obtenidos en La Zona de Dibujo. Dichos resultados se guardarán como una imagen de extensión “jpg”, que visualice el estado actual del espacio de trabajo. o Modificar grosor focos de luz: Para una mejor visualización de los focos de luz en el plano, el Usuario tiene la posibilidad de agrandar o hacer más pequeños los focos de luz definidos. o Modificar situación de foco de luz: Si el Usuario, en vez de borrar todos los elementos definidos, quiere únicamente desplazar los focos de luz definidos, puede redefinir las coordenadas de cualquier foco de luz. o Configurar color de elementos: Se posibilita cambiar el color de todos los elementos definidos, para que el Usuario configure la mejor gama de colores de tal forma que los resultados obtenidos sean, a su gusto, más visibles.
43
t-buena iluminación en el plano
•
Casos de uso: Crear foco de luz:
Actor Principal: o Usuario.
Actores secundarios: o Ninguno.
Precondiciones: o El Sistema de casos de estudio se encuentra en el estado inicial, en el estudio de nube de focos en el plano o en el estudio de nube de focos con obstáculos.
Trigger: o El Usuario selecciona crear un nuevo foco de luz.
Post-condición: o El Sistema queda con el nuevo foco de luz creado.
Flujo principal: 1) El Usuario selecciona el lugar en La Zona de Dibujo donde quiere colocar el nuevo foco de luz. 2) El Sistema guarda en memoria la posición del nuevo foco de luz. 3) El Sistema muestra en La Zona de Dibujo el nuevo foco de luz.
Escenarios secundarios: o No hay.
44
t-buena iluminación en el plano
•
Casos de uso: Crear obstáculo:
Actor Principal: o Usuario.
Actores secundarios: o Ninguno.
Precondiciones: o El Sistema de casos de estudio se encuentra en el estado inicial o en el estudio de nube de focos con obstáculos.
Trigger: o El Usuario selecciona crear un nuevo obstáculo.
Post-condición: o El Sistema queda con un nuevo obstáculo creado.
Flujo principal: 1) El Usuario de manera secuencial marca los puntos en La Zona de Dibujo que corresponden con los vértices del obstáculo. 2) El Sistema guarda en memoria el nuevo obstáculo. 3) El Sistema muestra en La Zona de Dibujo el nuevo obstáculo.
Escenarios secundarios: 3.a- El Usuario no ha marcado más de 2 vértices del obstáculo. 1- El Sistema espera a que el Usuario marque más vértices.
45
t-buena iluminación en el plano
•
Casos de uso: Crear polígono: Actor Principal: o Usuario. Actores secundarios: o Ninguno. Precondiciones: o El Sistema de casos de estudio se encuentra en el estado inicial, en el estudio de polígonos convexos o en el estudio de polígonos no convexos. Trigger: o El Usuario selecciona crear un nuevo polígono. Post-condición: o El Sistema queda con un nuevo polígono creado. Flujo principal: 1) El Usuario marca los vértices en La Zona de Dibujo. 2) El Usuario selecciona cerrar el polígono. 3) El Sistema guarda en memoria el nuevo polígono. 4) El Sistema muestra en La Zona de Dibujo el nuevo polígono. Escenarios secundarios: 3.a- El Usuario no ha marcado más de 2 vértices del polígono. 1- El Sistema espera a que el Usuario marque más vértices.
46
t-buena iluminación en el plano
•
Casos de uso: Regiones de t-buena iluminación para nubes de focos de luz con obstáculos:
Actor Principal: o Usuario. Actores secundarios: o Ninguno. Precondiciones: o El Sistema de casos de estudio se encuentra en el estado de estudio de nube de focos con obstáculos. Trigger: o El Usuario activa comenzar la ejecución del algoritmo de resolución de nube de focos de luz con obstáculos. Post-condición: o El Sistema resuelve el problema de nube de focos de luz con obstáculos. Flujo principal: 1) El Sistema identifica el algoritmo a utilizar: por Fuerza Bruta o por el algoritmo ACHE. 2) El Sistema arranca el algoritmo identificado para la resolución del problema.
47
t-buena iluminación en el plano
3) El Sistema muestra por pantalla las regiones de la t-buena iluminación calculadas. Escenarios secundarios: 2.a- El Usuario elige parar el algoritmo. 1- El Sistema queda en estado parado inicial. 2.b- El Usuario elige pausar el algoritmo. 1- El Algoritmo queda en modo pausado a espera de la reanudación. 2- El Usuario elige reanudar la ejecución del Algoritmo. 3- El Sistema vuelve a 2. 2.c- No existe ningún obstáculo convexo dibujado en La Zona de Dibujo. 1- El Sistema no arranca el Algoritmo de resolución. 2.d- No existe ningún foco de luz dibujado en La Zona de Dibujo. 1- El Sistema no arranca el algoritmo de resolución.
48
t-buena iluminación en el plano
•
Casos de uso: Regiones de t-buena iluminación para polígonos no convexos:
Actor Principal: o Usuario. Actores secundarios: o Ninguno. Precondiciones: o El Sistema de casos de estudio se encuentra en el estado de estudio de polígonos no convexos. Trigger: o El Usuario activa comenzar la ejecución del algoritmo de resolución de polígonos no convexos. Post-condición: o El Sistema resuelve el problema de iluminación de polígonos no convexos. Flujo principal: 1) El Sistema identifica el algoritmo a utilizar: por Fuerza Bruta o por el algoritmo ACHE. 2) El Sistema arranca el algoritmo identificado para la resolución del problema. 3) El Sistema muestra por pantalla las regiones de la t-buena iluminación calculadas. 49
t-buena iluminación en el plano
Escenarios secundarios: 2.a- El Usuario elige parar el algoritmo. 1- El Sistema queda en estado parado inicial. 2.b- El Usuario elige pausar el algoritmo. 1- El Algoritmo queda en modo pausado a espera de la reanudación. 2- El Usuario elige reanudar la ejecución del Algoritmo. 3- El Sistema vuelve a 2. 2.c- No existe ningún polígono no convexo dibujado en La Zona de Dibujo. 1- El Sistema no arranca el Algoritmo de resolución.
50
t-buena iluminación en el plano
•
Casos de uso: Regiones de t-buena iluminación para polígonos convexos:
Actor Principal: o Usuario. Actores secundarios: o Ninguno. Precondiciones: o El Sistema de casos de estudio se encuentra en el estado de estudio de polígonos convexos. Trigger: o El Usuario activa comenzar la ejecución del algoritmo de resolución de polígonos convexos. Post-condición: o El Sistema resuelve el problema de iluminación de polígonos convexos. Flujo principal: 1) El Sistema identifica el algoritmo a utilizar: por Fuerza Bruta o por el algoritmo ACHE. 2) El Sistema arranca el algoritmo identificado para la resolución del problema. 3) El Sistema muestra por pantalla las regiones de la t-buena iluminación calculadas. 51
t-buena iluminación en el plano
Escenarios secundarios: 2.a- El Usuario elige parar el algoritmo. 1- El Sistema queda en estado parado inicial. 2.b- El Usuario elige pausar el algoritmo. 1- El Algoritmo queda en modo pausado a espera de la reanudación. 2- El Usuario elige reanudar la ejecución del Algoritmo. 3- El Sistema vuelve a 2. 2.c- No existe ningún polígono convexo dibujado en La Zona de Dibujo. 1- El Sistema no arranca el Algoritmo de resolución.
52
t-buena iluminación en el plano
•
Casos de uso: Regiones de t-buena iluminación con focos de luz:
Actor Principal: o
Usuario.
Actores secundarios: o Ninguno. Precondiciones: o El Sistema de casos de estudio se encuentra en el estado de estudio de nube de focos en el plano. Trigger: o El Usuario activa comenzar la ejecución del algoritmo de resolución de nube de focos. Post-condición: o El Sistema resuelve el problema de iluminación de nube de focos en el plano. Flujo principal: 1) El Sistema arranca el algoritmo identificado para la resolución del problema. 2) El Sistema muestra por pantalla las regiones de la t-buena iluminación calculadas. .
53
t-buena iluminación en el plano
Escenarios secundarios: 1.a- El Usuario elige parar el algoritmo. 1- El Sistema queda en estado parado inicial. 1.b- El Usuario elige pausar el algoritmo. 1- El Algoritmo queda en modo pausado a espera de la reanudación. 2- El Usuario elige reanudar la ejecución del Algoritmo. 3- El Sistema vuelve a 2. 1.c- No existe ningún foco de luz dibujado en La Zona de Dibujo. 1- El Sistema no arranca el Algoritmo de resolución.
54
t-buena iluminación en el plano
•
Casos de uso: Configuración de degradación de luz:
Actor Principal: o Usuario. Actores secundarios: o Ninguno. Precondiciones: o La opción de degradación de luz está activada. Trigger: o El Usuario elige configurar la degradación de luz. Post-condición: o El Sistema configura la degradación de luz de los focos existentes en La Zona de Dibujo. Flujo principal: 1) El Usuario introduce la distancia máxima de visibilidad de los focos de luz. 2) El Sistema registra la distancia máxima de visibilidad en las variables del Sistema. 3) El Usuario escoge finalizar la configuración de visibilidad de los focos de luz.
55
t-buena iluminación en el plano
•
Casos de uso: Borrar panel de dibujo:
Actor Principal: o Usuario. Actores secundarios: o Ninguno. Precondiciones: o Existen diferentes elementos representados en La Zona de Dibujo. Trigger: o El Usuario elige eliminar todos los elementos creados anteriormente. Post-condición: o La Zona de Dibujo queda limpia y el Sistema sin ningún elemento creado. Flujo principal: 1) El Usuario marca eliminar todos los elementos de La Zona de Dibujo. 2) El Sistema elimina todos los elementos de Dibujo que se encontraban dentro de sus variables.
56
t-buena iluminación en el plano
•
Casos de uso: Cargar imagen de fondo:
Actor Principal: o Usuario. Actores secundarios: o Ninguno. Precondiciones: o Ninguna. Trigger: o El Usuario elige cargar una imagen de fondo. Post-condición: o La Zona de Dibujo queda con una nueva imagen de fondo representada. Flujo principal: 1) El Usuario marca cargar una nueva imagen de fondo. 2) El Sistema muestra el directorio para escoger una imagen. 3) El Usuario escoge una imagen para cargar como fondo. 4) El Sistema carga la imagen como fondo de La Zona de Dibujo. Escenarios secundarios: 3.a- El Usuario cancela la carga de una imagen. 1- El Sistema deja de mostrar el directorio. 57
t-buena iluminación en el plano
•
Casos de uso: Guardar resultados:
Actor Principal: o Usuario. Actores secundarios: o Ninguno. Precondiciones: o Ninguna. Trigger: o El Usuario elige guardar los resultados obtenidos. Post-condición: o Se crea una imagen con extensión .jpg en el directorio con La Zona de Dibujo representada. Flujo principal: 1) El Usuario marca guardar los resultados obtenidos. 2) El Sistema muestra las opciones de la zona del Directorio donde guardar los resultados y el nombre del archivo. 3) El Usuario introduce la dirección del Directorio donde guardar los resultados y el nombre del archivo. 4) El Sistema guarda los resultados en una imagen con el nombre introducido y en la carpeta del Directorio especificada.
58
t-buena iluminación en el plano
Escenarios secundarios: 3.a- El Usuario cancela guardar los resultados obtenidos. 1- El Sistema deja de mostrar la opción de guardar los resultados. 3.b- El Usuario introduce mal la extensión del Directorio. 1- El Sistema no guarda los resultados y deja de mostrar la opción de guardar los resultados. 3.c- El Usuario no introduce ningún nombre de archivo. 1- El Sistema no guarda los resultados y deja de mostrar la opción de guardar los resultados.
59
t-buena iluminación en el plano
•
Casos de uso: Modificar grosor focos de luz:
Actor Principal: o Usuario. Actores secundarios: o Ninguno. Precondiciones: o Ninguna. Trigger: o El Usuario elige configurar el grosor de los focos de luz. Post-condición: o El Sistema configura el grosor de los focos de luz. Flujo principal: 1) El Usuario introduce el nuevo grosor de los focos de luz. 2) El Sistema registra el grosor de los focos de luz en las variables del Sistema. 3) El Sistema muestra en La Zona de Dibujo los focos de luz con el nuevo grosor. 4) El Usuario escoge finalizar la configuración del grosor de los focos de luz.
60
t-buena iluminación en el plano
•
Casos de uso: Modificar situación de foco de luz:
Actor Principal: o Usuario. Actores secundarios: o Ninguno. Precondiciones: o Existen focos de luz en La Zona de Dibujo. Trigger: o El Usuario elige un foco de luz a modificar. Post-condición: o El Sistema modifica las coordenadas del foco de luz. Flujo principal: 1) El Usuario selecciona un foco de luz a modificar su posición. 2) El Usuario define las nuevas coordenadas del foco de luz en La Zona de Dibujo. 3) El Sistema modifica las variables de coordenadas del foco de luz. 4) El Sistema muestra los cambios efectuados en La Zona de Dibujo.
61
t-buena iluminación en el plano
•
Casos de uso: Configurar color de elementos:
Actor Principal: o Usuario. Actores secundarios: o Ninguno. Precondiciones: o Ninguna. Trigger: o El Usuario escoge cambiar las propiedades de color de los elementos. Post-condición: o El Sistema modifica el color del elemento seleccionado. Flujo principal: 1) El Usuario selecciona un tipo de elemento a cambiar su color. 2) El Sistema muestra la paleta de colores. 3) El Usuario escoge un color para ser seleccionado. 4) El Usuario decide cambiar el color del elemento. 5) El Sistema guarda en sus variables el nuevo color seleccionado. 6) El Sistema cambia el color del elemento seleccionado.
62
t-buena iluminación en el plano
e. Estructura del Sistema: Diagrama de paquetes. El siguiente diagrama de paquetes muestra la arquitectura general del sistema y cómo interactúan entre sí los diferentes módulos.
El desarrollo software de t-buena iluminación se divide en tres subsistemas o paquetes, que corresponden con las tres grandes funciones del sistema:
Figura 6.e.1: Diagrama de paquetes.
63
t-buena iluminación en el plano
f. Descripción del diagrama de paquetes. Las relaciones entre los diferentes paquetes son bastante claras. El paquete Interfaz utiliza los elementos de Geometría para la representación en La Zona de Dibujo, y es el encargado de gestionar la ejecución de los Algoritmos.
El paquete de Algoritmos ha de saber qué elementos geométricos están definidos así como sus propiedades y métodos, para su ejecución.
o Paquete Interfaz: Es el paquete relacionado directamente con la representación gráfica y de interacción del Usuario. Dicho paquete se ocupa de la representación de todos los elementos así como de los diferentes componentes de interacción con el Usuario como son botones, menús, etc.
•
En el sub-paquete “Interfaz” se engloban todas aquellas ventanas, menús, botones, etc. definidas, que hace que el Usuario introduzca variables e interaccione con el Sistema.
•
El sub-paquete “Zona Dibujo” es el paquete específico de representación bidimensional de todos aquellos elementos definidos, de sus variables gráficas de representación y de los resultados de los algoritmos de resolución de la t-buena iluminación.
.
64
t-buena iluminación en el plano
o Paquete Geometría: Es el paquete de definición conceptual de todas las clases Geométricas de representación. En él se definen todos los elementos de representación en el plano así como sus propiedades y métodos para el apoyo a la resolución de los problemas de la t-buena iluminación.
El sub-paquete “Geometría” es el paquete específico de representación de los elementos fundamentales de cálculo de la tbuena iluminación.
•
El sub-paquete “Auxiliar” es el paquete de definición de aquellos elementos geométricos auxiliares para la resolución de los problemas de t-buena iluminación, así como para la representación gráfica auxiliar en las ejecuciones retardadas como paso a paso.
o Paquete Algoritmos: Es el paquete que contiene los algoritmos de resolución de los problemas de la t-buena iluminación. Dichos algoritmos corresponden con hilos independientes de ejecución que se encargan tanto de la resolución como de la representación auxiliar en los casos de ejecución retardada.
65
t-buena iluminación en el plano
8. DISEÑO GEOMÉTRICO.
Partiendo del modelo de dominio hecho en el apartado de diseño de software general, hay que crear las diferentes clases y relaciones que consigan representar fielmente los elementos geométricos necesarios para los diferentes casos de estudio de la t-buena iluminación.
Para ello se parte de un paquete desarrollado por Sun Microsystems existente en las librerías generales de java, que es el “java.awt.geom”.
Dicho paquete “java.awt.geom” proporciona clases java 2D para definir y dar operaciones sobre objetos 2D. De dicho paquete, las clases que más importan son las siguientes:
Clase “java.awt.geom.Area”: Clase que sirve para definir y describir áreas cerradas. Dicha clase se utiliza para construir y operar sobre áreas combinándolas con operaciones como intersección, unión, diferencia etc. [API_07].
Figura 8.1: Diagrama de clase “java.awt.Area” [DIAG02].
66
t-buena iluminación en el plano
Clase “java.awt.Point2D.Double”: Clase que sirve par definir la representación de un punto en el espacio bidimensional, representando una localización en las coordenadas (x,y) [API_07].
Figura 8.1: Diagrama de clase “java.awt.geom.Point2D” y sus extensiones [DIAG02].
67
t-buena iluminación en el plano
Clase “java.awt.Polygon”: La clase describe una región cerrada y bidimensional gracias a la definición de una serie consecutiva de pares de coordenadas (x,y), que representan todos los vértices del polígono. Uniendo consecutivamente los pares de coordenadas por segmentos, cerrando el primero con el último par, se obtiene el polígono [API_07].
Figura 8.3: Diagrama de clase “java.awt.Polygon” [DIAG02].
68
t-buena iluminación en el plano
Clase “java.awt.geom.Line2D.Double”: La clase “Line2D.Double” representa un segmento en el plano gracias a dos coordenadas (x, y) o puntos. Por dichos dos puntos se traza un segmento de área nula [API_07].
Figura 8.4: Diagrama de clase “java.awt.geom.Line2D” y sus extensiones [DIAG02].
Partiendo de la existencia de el paquete “java.awt.geom” predefinido en la tecnología Java, se desarrolla un paquete de geometría adaptado a los requisitos del problema de la tbuena iluminación. Dicho paquete de Geometría está representado en el siguiente diagrama de clases:
69
t-buena iluminación en el plano
Figura 8.5: Diagrama de clase del paquete geometría.
70
t-buena iluminación en el plano
a. Descripción del diagrama de clases del paquete Geometría. FocoLuz: Clase que representa todos aquellos focos del plano que están definidos y no pertenecen a un polígono. Representan los elementos de iluminación. Son puntos y por ello heredan todas las propiedades de la clase java.awt.geom.Point2D.Double.
Polígono: Clase que representa el elemento principal del caso de estudio de regiones tbien iluminadas en el interior de un polígono. La clase hereda de “java.awt.Polygon” por lo que hereda todas sus propiedades y está definida por una serie consecutiva de pares de coordenadas (x, y). Dichos pares de coordenadas representan los vértices del polígono y, por lo tanto, en el caso de estudio de la t-buena iluminación representan focos de luz que iluminan única y exclusivamente el interior del polígono. La clase está asociada con diferentes objetos pertenecientes a la clase “AreaTBuenaIluminación”, es decir, un polígono tiene asociadas diferentes áreas o regiones de t-buena iluminación, que corresponden con las regiones bien iluminadas interiores al polígono, iluminadas por los focos de luz que se encuentran en sus vértices.
Obstáculo: Clase que representa aquellos elementos en el plano que interfieren en la propagación de la luz de los focos de luz. La clase hereda de Polígono y por lo tanto de “java.awt.Polygon”, pero sus vértices no representan ya ningún foco de luz.
AreaTBuenaIluminación: Clase que representa las diferentes regiones t-bien iluminadas por una nube de focos. Una instancia de dicha clase representa aquellos puntos del plano que tienen similares propiedades de t-buena iluminación.
Línea: Perteneciente al Paquete “Geometría.Auxiliar”. Representa aquellas líneas auxiliares que se utilizan en la ejecución de los algoritmos para la resolución de problemas de 71
t-buena iluminación en el plano
t-buena iluminación. Es una clase que hereda de la clase “java.awt.geom.Line2D” y por tanto hereda todas sus características. Se utiliza fundamentalmente en la resolución de los algoritmos para unir focos de luz o un foco de luz y un punto del plano, y averiguar a qué lado de la línea se encuentran los demás focos.
Frontera:
Perteneciente
al
Paquete
“Geometría.Auxiliar”.
Representa
líneas
teóricamente infinitas en vez de segmentos que empiezan en un punto y acaban en otro. Dichas líneas se utilizan fundamentalmente para la resolución de los algoritmos en modo retardado o paso a paso, para mostrar al Usuario cuáles son las acciones efectuadas en cada paso del Algoritmo.
ElementosDibujo: Clase que representa todos aquellos elementos existentes en el plano. Se utiliza para guardar los focos de luz, polígonos, obstáculos y regiones de iluminación definidas, así como los objetos auxiliares. Ya que sólo existe un plano definido en el Sistema y sus elementos deben ser los mismos para todo el Sistema, es necesario que la clase se defina según el patrón de diseño “Singleton”, ya que sólo debe haber un objeto de clase, que es a la que accederán todos aquellos elementos que la instancien.
72
t-buena iluminación en el plano
9. DISEÑO DEL INTERFAZ.
La interfaz es una parte fundamental en toda aplicación desarrollada en el campo de La Geometría Computacional.
La interfaz sirve tanto para interactuar con el Usuario en la especificación de sus estudios como para mostrar los resultados obtenidos por los diferentes algoritmos ejecutados.
La interfaz definida en este proyecto, se apoya en dos pilares fundamentales. El primero son todos aquellos elementos de interacción y de definición de variables por parte del Usuario, para que se maneje adecuadamente por las características del programa. El segundo pilar es lo que se ha denominado una “Zona de Dibujo”. En dicha zona es donde aparecen todos y cada uno de los elementos definidos así como los resultados obtenidos por la ejecución. Por lo tanto muestra los focos de luz, los obstáculos y los polígonos, así como las regiones t-bien iluminadas. Adicionalmente en ciertos modos de ejecución de los algoritmos también muestra los elementos auxiliares de guía de ejecución para el Usuario.
Siendo fiel a esta diferencia clara, el paquete Interfaz se ha dividido en dos subpaquetes. El primero es el comúnmente denominado “Interfaz” y el segundo, “Interfaz.ZonaDibujo”, como antes se expuso en el diagrama de paquetes.
73
t-buena iluminación en el plano
a. Diagrama de clases del paquete Interfaz. La aplicación es manejada desde una ventana principal dividida en diferentes paneles que desempeñan funciones concretas. El diagrama de clases de la ventana principal con sus paneles es el siguiente.
Figura 9.1: Diagrama de clase de la ventana principal.
74
t-buena iluminación en el plano
Aparte de la ventana principal de la aplicación, existen diferentes ventanas auxiliares, cada una con una funcionalidad específica.
El diagrama de clases de dichas ventanas auxiliares es el siguiente.
Figura 9.2: Diagrama de clase de las ventanas auxiliares.
75
t-buena iluminación en el plano
b. Interfaz.ZonaDibujo. La clase “ZonaDibujo” es un panel en el que se pintan todos aquellos elementos de estudio. Contiene únicamente aquellos métodos necesarios para dibujar los elementos y aquellos métodos de creación como resultado de interacción con el Usuario por pulsar en la zona.
“ZonaDibujo” es una clase creada con el patrón de diseño “singleton”, ya que sólo se puede hacer una instancia de ella
La clase “PropiedadesDibujo” también está construida según el patrón de diseño “singleton” y contiene todas aquellas propiedades necesarias para que la clase ZonaDibujo dibuje correctamente los elementos. Dichas propiedades son tales como los colores a utilizar, los elementos que hay que dibujar, etc.
76
t-buena iluminación en el plano
Figura 9.3: Diagrama de clase de La Zona de Dibujo.
77
t-buena iluminación en el plano
10. DISEÑO DE LOS ALGORITMOS.
Todos los algoritmos implementados son hilos de ejecución independientes. Esta propiedad facilita que la ejecución de un algoritmo se pueda pausar, reanudar o parar definitivamente.
A continuación se muestra el diagrama de clases del paquete “Algoritmos”.
Figura 10.1: Diagrama de clase del paquete Algoritmos.
78
t-buena iluminación en el plano
Los algoritmos, como resultado de su ejecución, lo único que hacen es definir las regiones de t-buena iluminación a calcular y guardarlas como elementos geométricos, variables existentes en la clase “ElementosDibujo” vista en el diagrama de clases del paquete de geometría.
Para hacer que los algoritmos sean hilos de ejecución independientes y paralelos a la ejecución principal de la aplicación, son clases derivadas de la clase “Java.Thread”. Redefiniendo el método “run()” de dicha clase se consigue una ejecución independiente.
La ejecución de dichos algoritmos es controlada desde la ejecución principal de la aplicación y controlables por el Usuario gracias a la interfaz que se muestra en la ventana principal.
79
t-buena iluminación en el plano
11. ILUMINACIÓN DE UNA NUBE DE FOCOS POR FUERZA BRUTA.
El algoritmo que calcula la iluminación creada por una serie de focos de luz dispuestos en el plano por fuerza bruta, llega a la solución calculando las propiedades de iluminación de cada punto. Para ello hace un barrido de puntos en el plano, con grano muy fino, determinando para cada uno su variable t de iluminación. Gracias al cálculo de la iluminación de cada uno de los puntos existentes, es capaz de definir las regiones del plano con las mismas características de buena iluminación. Los pasos que lleva para ello son:
1. Rectángulo “R” de área mínima que es paralelo al eje de coordenadas y que contiene a todos los focos de luz existentes.
Esto se hace para no calcular la t-buena iluminación de aquellos puntos que ya se sabe que tienen t=0 con lo que se ahorra tiempo de cálculo. Otra manera de obtener ahorro de tiempo habría sido calcular el área inscrita en el cierre convexo de todos los focos de luz y calcular las propiedades de buena iluminación únicamente de aquellos puntos que se encuentran dentro de dicho cierre convexo.
80
t-buena iluminación en el plano
Foco Luz Foco Luz Foco Luz
Foco Luz Foco Luz
Foco Luz
Rectángulo “R”
Zona de Dibujo
Figura 11.1: Rectángulo de área mínima.
2. Barrido matricial de la región inscrita en el Rectángulo R.
Gracias a dos bucles anidados variando la coordenada X y la coordenada Y, se especifican los diferentes puntos “P” de los que calcular las propiedades de t-buena iluminación.
Punto “P de estudio
Rectángulo “R”
Zona de Dibujo
Figura 11.2: Barrido matricial.
81
t-buena iluminación en el plano
a. Para cada foco de luz “F” definido en el plano
i. Crear la recta “L” que conecta a “P” con “F”.
ii. Diferenciar los dos semiplanos creados a cada lado de la recta “L”.
iii. Definir el mínimo número de focos que han quedado a un lado de la recta “L”.
Este paso sirve para identificar la variable t del punto “P”, es decir, sus propiedades de buena iluminación.
1 1 3
Semiplano A
Semiplano B Punto “P”
2
2
Foco “F”
Linea “L”
Rectángulo “R”
Zona de Dibujo
Figura 11.2.a: Número de focos en cada semiplano.
82
t-buena iluminación en el plano
b. Iluminación del punto “P”: “t”= mínimo numero de luces existentes en los todos los semiplanos creados.
t=2
Rectángulo “R”
Zona de Dibujo
Figura 11.2.b: Valor de la variable “t”.
c. Añadir el punto “P” a la región “t” bien iluminada.
Al terminar todo el barrido de los puntos interiores al Rectángulo “R” y quedar definidos sus propiedades de buena iluminación, se obtiene como resultado las distintas regiones bien iluminadas, con lo que el algoritmo ha concluido.
Es responsabilidad del paquete Interfaz, el mostrar las diferentes regiones bien iluminadas, teniendo en cuenta los requerimientos específicos de La Zona de Dibujo que el Usuario ha seleccionado.
En la opción posible a utilizar de degradación máxima de luz, el modo de cálculo se hace midiendo la distancia de cada foco de luz con el punto “P” que se está estudiando en cada momento. Si dicha distancia es superior a la máxima distancia especificada, el foco de luz no se contabilizará como foco existente en el semiplano que ocupa. 83
t-buena iluminación en el plano
FocoLuz 3
El FocoLuz 3 no ilumina al punto “P”, su distancia al punto es superior a la máxima distancia
Punto “P”
Foco “F”
Rectángulo “R”
Linea “L”
Zona de Dibujo
Figura 11.3: Degradación de la iluminación.
A continuación se muestra una imagen ejemplo de las regiones 1 y 2-bien iluminadas por una nube de focos en el plano. Dicha imagen ha sido creada por el algoritmo que se acaba de explicar.
Figura 11.4: Ejemplo de regiones t-bien iluminadas.
84
t-buena iluminación en el plano
A continuación se detalla el diagrama de secuencia del algoritmo:
Figura 11.5: Diagrama de secuencia del algoritmo “NubeFocosFuerzaBruta”.
85
t-buena iluminación en el plano
12. ILUMINACIÓN DE POLÍGONOS POR FUERZA BRUTA.
El algoritmo que calcula la iluminación creada en el interior de un polígono con focos de luz en sus vértices, llega a la solución calculando las propiedades de iluminación de cada punto interior a dicho polígono. Para ello hace un barrido de puntos en el plano, determinando para cada uno su variable t de iluminación. Aquellos puntos que no se encuentran en el interior del polígono los descarta ya que no son el caso de estudio que se trata de resolver en estos momentos. Gracias al cálculo de la iluminación de cada uno de los estudiados, es capaz de definir las regiones interiores al polígono con las mismas características de buena iluminación. Dicho algoritmo calcula las regiones de t-buena iluminación tanto de los polígonos convexos como de aquellos que no lo son. Para calcular la buena iluminación del interior de los polígonos es necesario una numeración y un estudio individual. Para cada uno de ellos se lleva a cabo los siguientes pasos:
1. Rectángulo “R” de área mínima que es paralelo al eje de coordenadas y que contiene al polígono de estudio.
Esto se hace para no calcular la t-buena iluminación de aquellos puntos que ya se sabe que tienen t=0. De esta manera se ahorra tiempo de cálculo.
86
t-buena iluminación en el plano
Polígono “P”
Rectángulo “R”
Zona de Dibujo Figura 12.1: Rectángulo de área mínima.
2. Barrido matricial de la región inscrita en el Rectángulo R.
Gracias a dos bucles anidados variando la coordenada X y la coordenada Y, se especifican los diferentes puntos “p” de los que calcular las propiedades de t-buena iluminación.
a. Comprobar si el punto “p” definido en el barrido se encuentra dentro del polígono.
Ya que los únicos puntos que interesan para el estudio son los interiores al polígono, se descartan todos aquellos en el barrido que se encuentran fuera del mismo.
87
t-buena iluminación en el plano
Polígono “P”
Punto “p”
Rectángulo “R”
Zona de Dibujo
Figura 12.2.a: Barrido matricial.
b. Para cada foco de luz “F” definido en el plano.
i. Crear la recta “L” que conecta a “P” con “F”. ii. Diferenciar los dos semiplanos creados a cada lado de la recta “L”.
Polígono “P”
Semiplano A
Recta “L”
Semiplano B
Rectángulo “R”
Zona de Dibujo
Figura 12.2.b: Definición de semiplanos.
88
t-buena iluminación en el plano
iii. Definir a cada semiplano aquellos focos de luz del polígono que son visibles desde el punto “p”.
Dichos focos de luz son los únicos que iluminan al punto “p”, ya que puede haber otros pertenecientes al polígono que no iluminen al punto “p”, por ser obstaculizados por lados del mismo obstáculo.
Foco no visible
Polígono “P” Foco visible Foco no visible
Focos nos visibles
Foco visible Foco visible
Foco visible
Recta “L”
Foco visible
Rectángulo “R”
Zona de Dibujo Figura 12.2.c: Establecer focos visibles.
Para definir si un foco es visible desde un punto “p”, lo que se hace es unir dichos puntos con un segmento. Si el segmento definido corta en algún punto a un lado del polígono, significa que dicho lado actúa como obstáculo entre los puntos y por lo tanto no son visibles. iv. Definir el mínimo número de focos visibles que han quedado a un lado de la recta “L”. Este paso sirve para identificar la variable t del punto “p”, es decir, sus propiedades de buena iluminación.
89
t-buena iluminación en el plano
v. Iluminación del punto “p”: “t”= mínimo número de luces existentes en los todos los semiplanos creados.
Polígono “P”
t=1
Rectángulo “R”
Zona de Dibujo
Figura 12.2.d: Valor de la variable “t”.
c. Añadir el punto “P” a la región “t” bien iluminada.
Al terminar todo el barrido de los puntos interiores al Rectángulo “R” para todos los polígonos existentes en el plano y quedar definidos sus propiedades de buena iluminación, se obtiene como resultado las distintas regiones bien iluminadas por un polígono cualquiera con focos de luz en sus vértices, con lo que el algoritmo ha concluido.
Es responsabilidad del paquete Interfaz, el mostrar las diferentes regiones bien iluminadas asociadas a cada polígono, teniendo en cuenta los requerimientos específicos de La Zona de Dibujo que el Usuario ha seleccionado.
90
t-buena iluminación en el plano
En la opción posible a utilizar de degradación máxima de luz, el modo de cálculo se hace midiendo la distancia de cada foco de luz del polígono con el punto “p” que se está estudiando en cada momento. Si dicha distancia es superior a la máxima distancia especificada, el foco de luz no se contabilizará como foco existente en el semiplano que ocupa.
A continuación se muestra una imagen ejemplo de las regiones 1, 2 y 3-bien iluminadas en dos obstáculos: uno convexo y otro no. Dicha imagen ha sido creada por el algoritmo que se acaba de explicar.
Figura 12.3: Ejemplo t-buena iluminación en el interior de polígonos.
91
t-buena iluminación en el plano
A continuación se detalla el diagrama de secuencia del algoritmo:
Figura 12.4: Diagrama de secuencia algoritmo “InteriorPoligonosFuerzaBruta”.
92
t-buena iluminación en el plano
13. ILUMINACIÓN DE UNA NUBE DE FOCOS CON OBSTÁCULOS POR FUERZA BRUTA.
El algoritmo que calcula la iluminación creada por una serie de focos de luz dispuestos en el plano con obstáculos por fuerza bruta, llega a la solución calculando las propiedades de iluminación de cada punto del plano.
Para ello hace un barrido de puntos en el plano, con grano muy fino, determinando para cada uno su variable t de iluminación. Gracias al cálculo de la iluminación de cada uno de los puntos existentes, es capaz de definir las regiones del plano con las mismas características de buena iluminación.
Para ello además de tener en cuenta los focos de luz existentes en el plano, también tiene que tener en cuenta los obstáculos existentes que impiden la propagación de la luz por el plano.
Los pasos que lleva para ello son:
1. Rectángulo “R” de área mínima que es paralelo al eje de coordenadas y que contiene a todos los focos de luz existentes.
Esto se hace para no calcular la t-buena iluminación de aquellos puntos que ya se sabe que tienen t=0 con lo que se ahorra tiempo de cálculo. Otra manera de haber
93
t-buena iluminación en el plano
ahorrado más tiempo habría sido calcular el área inscrita en el cierre convexo de todos los focos de luz y calcular las propiedades de buena iluminación únicamente de aquellos puntos que se encuentran centro de dicho cierre convexo.
Foco Luz Foco Luz Foco Luz
Foco Luz Foco Luz
Foco Luz
Rectángulo “R”
Zona de Dibujo Figura 13.1: Rectángulo de área mínima.
2. Barrido matricial de la región inscrita en el Rectángulo R.
Gracias a dos bucles anidados variando la coordenada X y la coordenada Y, se especifican los diferentes puntos “P” de los que calcular las propiedades de t-buena iluminación.
94
t-buena iluminación en el plano
Punto “P”
Rectángulo “R”
Zona de Dibujo Figura 13.2.a: Barrido matricial.
a. Para cada foco de luz “F” definido en el plano.
i. Crear la recta “L” que conecta a “P” con “F”.
ii. Diferenciar los dos semiplanos creados a cada lado de la recta “L”.
iii. Definir el mínimo número de focos que han quedado a un lado de la recta “L”, y que son visibles desde el punto “P”.
Este paso sirve para identificar la variable t del punto “P”, es decir, sus propiedades de buena iluminación.
95
t-buena iluminación en el plano
Semiplano A
Semiplano B
2
Foco no visible
1 Foco no visible
1
Rectángulo “R”
Linea “L”
Zona de Dibujo Figura 13.2.b: Definición de semiplanos.
Para saber si un foco de luz ilumina al punto “P”, se traza un segmento que los una. Si dicho segmento corta a algún obstáculo definido en el plano es que dicho foco no ilumina al punto “P”. El foco no será contabilizado en el número de focos existentes en cada semiplano creado. b. Iluminación del punto “P”: “t”= mínimo número de luces existentes en los todos los semiplanos creados.
96
t-buena iluminación en el plano
t=1
Rectángulo “R”
Linea “L”
Zona de Dibujo
Figura 13.2.c: Valor de la variable t.
c. Añadir el punto “P” a la región “t” bien iluminada.
Al terminar todo el barrido de los puntos interiores al Rectángulo “R”, y quedar definidos sus propiedades de buena iluminación de focos de luz con obstáculos, se obtiene como resultado las distintas regiones bien iluminadas, con lo que el algoritmo ha concluido.
Es responsabilidad del paquete Interfaz, el mostrar las diferentes regiones bien iluminadas, teniendo en cuenta los requerimientos específicos de La Zona de Dibujo que el Usuario ha seleccionado.
En la opción posible a utilizar de degradación máxima de luz, el modo de cálculo se hace midiendo la distancia de cada foco de luz con el punto “P” que se está estudiando en cada momento. Si dicha distancia es superior a la máxima distancia especificada, el foco de luz no se contabilizará como foco existente en el semiplano que ocupa.
97
t-buena iluminación en el plano
A continuación se muestra una imagen ejemplo de las regiones 1 y 2-bien iluminadas de una nube de focos de luz con obstáculos. Dicha imagen ha sido creada por el algoritmo que se acaba de explicar.
Figura 13.3: Ejemplo de iluminación con obstáculos.
98
t-buena iluminación en el plano
A continuación se detalla el diagrama de secuencia del algoritmo:
Figura 13.4: Diagrama de secuencia del algoritmo “NubeFocosFuerzaBruta”.
99
t-buena iluminación en el plano
14. ILUMINACIÓN
DE
POLÍGONOS
CONVEXOS
POR
ACHE.
Este es uno de los algoritmos más sencillos a desarrollar. Se basa en la intersección de cierres convexos explicado con anterioridad en el CAPÍTULO 3.
Los pasos a seguir son bastante sencillos. El algoritmo siempre está orientado a calcular el Ker
t-1
(P), es decir, el núcleo “t-1” del polígono “P”, siendo “t” aquellas
iluminaciones que se quieren calcular.
El algoritmo desarrollado sigue la siguiente secuencia de pasos:
1. Para cada polígono existente se estudia si es convexo o no.
2. Si un polígono “P” es convexo, se calculan todas aquellas regiones t-bien iluminadas internas.
a. En primer lugar, se define la región t-bien iluminada “Rt” interior al polígono “P” como el área inscrita en dicho polígono. A continuación y a lo largo de toda la explicación se va a ejemplificar con gráficas de cálculo de 2-buena iluminación.
100
t-buena iluminación en el plano
1
Polígono P
2 9
Región 2-bien iluminada inicialmente
8
3
7 4
6 5
Figura 14.1: Inicio de la región bien iluminada.
b. Para cada vértice vi de “P”, se crea un polígono auxiliar “P2” que tiene como vértices los vértices vi, vi+1, … , vi+t del polígono “P” original.
1
Polígono P
2 9
3
Polígono P2 auxiliar
8
7 4
6 5
Figura 14.2: Definición de polígono auxiliar.
c. A la región “Rt” en un primer momento definida, se le substrae aquel área inscrita en el polígono auxiliar “P2”. Tras hacer dicho paso con todos los vértices de “P” se tiene la región t-bien iluminada como intersección de cierres convexos.
101
t-buena iluminación en el plano
A continuación se detalla el diagrama de secuencia del algoritmo:
Figura 14.3: Diagrama de secuencia algoritmo “InteriorPoligonosConvexos”.
102
t-buena iluminación en el plano
15. ILUMINACIÓN DE POLÍGONOS NO CONVEXOS POR ACHE.
A continuación se recuerda la descripción esquemática del algoritmo de cálculo de la 2buena iluminación en un polígono no convexo. ___________________________________________________________________________
Algoritmo de 2−buena iluminación en un polígono no convexo
ENTRADA: Un polígono P con n vértices y un conjunto F = {f1, ..., fn} de n focos situados en los vértices de P.
SALIDA: La región 2−bien iluminada en el interior de P por F, W2 (F, P).
1. Construcción de las regiones Hi. Para cada vértice “i” se trazan las diagonales correspondientes al camino geodésico mínimo desde i al vértice “i” + 2. La región comprendida entre el camino y el vértice “i” + 1 no está 2−bien iluminada.
2. Construcción de triángulos asociados a lados cóncavos. Por cada arista “ax” incidente en el vértice cóncavo “x” se elimina una zona no 2−bien iluminada construida del siguiente modo: Prolongando el lado “ax” hacia el interior del polígono cortará a un lado de P en un punto “t”. Girando los segmentos “at” con centro en “a” y “xt” con centro en “x” y en sentidos contrarios, se encuentran los primeros vértices visibles en ambos casos, que se llamarán “i” y “j” respectivamente. Si se calcula el punto de intersección “d” de las rectas “xj” y “ai”, se puede construir el triángulo “Δ(adx)” que es una región no 2-bien Iluminada. 103
t-buena iluminación en el plano
3. Eliminación de las regiones no 2−bien iluminadas. Eliminar de P las regiones Hi construidas en el Paso 1 y los dos triángulos adyacentes a cada vértice cóncavo de P, construidos en el Paso 2.
____________________________________________________________________________
El algoritmo implementado de iluminación de polígonos no convexos por ACHE, calcula únicamente las regiones 1 y 2-bien iluminadas interiores. El cálculo de la región 1-bien iluminada es inmediato ya que coincide con el área inscrita por el polígono no convexo. En el cálculo de la región 2-bien iluminada es algo más complicado. En el CAPÍTULO 3 se explicó detalladamente cómo es el algoritmo de cálculo. A continuación se va a detallar cómo se han resuelto ciertos cálculos en la ejecución del algoritmo explicado.
Recorte geodésico: El recorte geodésico es necesario cuando se quiere eliminar de la región 2-bien iluminada el triángulo que crean los vértices vi, vi+1, vi+2 y los vértices vi, vi+2 no son mutuamente visibles.
Para la eliminación de dicha zona hay que crear un polígono con dichos tres vértices y aquellos que estén contenidos en el recorte geodésico entre los vértices vi, vi+2.
104
t-buena iluminación en el plano
El cálculo de los vértices del polígono no convexo “P”, que están contenidos en el recorte geodésico, se basa en un bucle que recorre los vértices desde el vértice vi+2 en adelante hasta llegar al vértice vi.
V i+1
Vi
V i+2
Figura 15.1: Definir sentido de recorrido.
Cuando encuentra el primer vértice del polígono que es visible desde el vértice vi, se marca como vértice perteneciente al camino geodésico, marca dicho vértice como vértice a visualizar en la siguiente iteración del bucle y vuelve a empezar.
V i+1
Vi
V i+2
Figura 15.2: Agregar nuevo vértice al camino geodésico.
105
t-buena iluminación en el plano
El algoritmo para cuando el vértice añadido al camino geodésico es visible por el vértice vi+2.
V i+1
Vi
V i+2
Figura 15.3: Camino geodésico final.
En éste momento ya se tiene el recorte geodésico, y por tanto también se tiene la región que se había denominado Hi, la cual hay que eliminar de la región 2-bien iluminada.
Triángulos asociados a los lados cóncavos: Una parte fundamental del algoritmo ACHE para los polígonos no convexos, es recortar aquellos triángulos asociados a los vértices no cóncavos. Para ello se siguen una serie de pasos:
1. Recorrer todos los vértices del polígono identificando cuáles son cóncavos.
Para detectar qué vértices son cóncavos se hace uso del producto vectorial. En aquellos casos en que el vértice sea cóncavo, el signo de dicho producto vectorial mostrará que lo es. Así se podrá pues diferenciar entre los vértices cóncavos y los vértices convexos [VILL98].
106
t-buena iluminación en el plano
El producto vectorial en el espacio R3 tiene como fórmula general la siguiente:
Figura 15.4: Fórmula general del producto vectorial en R3 [WIKI07].
En el caso en el que se utiliza, R2, la fórmula que se maneja es:
Figura 15.5: Aplicación del producto vectorial a R2 [WIKI07].
Figura 15.6: Representación gráfica del signo del producto vectorial [WIKI07].
2. Cálculo de los vértices de unión para crear el triángulo asociado.
a) Al vértice justo siguiente al vértice cóncavo se le denomina como Vanterior, y al vértice siguiente a Vanterior como Vsiguiente. Asimismo se traza una recta R que pase por el vértice cóncavo y el vértice anterior a dicho vértice cóncavo.
107
t-buena iluminación en el plano
Recta “R”
Vértice cóncavo Vanterior
Vsiguiente
Polígono “P”
Zona de Dibujo
Figura 15.7: Pasos previos del algoritmo.
b) Mientras Vsiguiente y Vanterior pertenezcan al mismo semiespacio definido por la recta R, se avanzan dichos vértices por el polígono.
c) Cuando Vanterior y Vsiguiente pertenezcan a distintos semiplanos y el punto de corte entre la recta R y la que une Vanterior y Vsiguiente sea visible desde el vértice cóncavo, ya se han conseguido los puntos necesarios para definir el triángulo.
Recta “R”
Vértice cóncavo
Vsiguiente Vanterior
Polígono “P”
Zona de Dibujo
Figura 15.8: Evolución hasta encontrar los vértices idóneos.
108
t-buena iluminación en el plano
d) Se traza una recta que una el vértice cóncavo y Vanterior, otra recta que una el vértice anterior al vértice cóncavo y Vsiguiente. El punto de corte de dichas dos rectas es el tercer punto que define el triángulo no 2-bien iluminado asociado a dicho vértice cóncavo.
Recta “R”
Vértice cóncavo
Vsiguiente
Polígono “P” Vanterior
Zona de Dibujo
Figura 15.9: Cálculo del triángulo asociado.
e) Hay que repetir el paso pero esta vez recorriendo los vértices en el sentido contrario.
109
t-buena iluminación en el plano
A continuación se detalla el diagrama de secuencia del algoritmo:
Figura 15.10: Diagrama de secuencia algoritmo “InteriorPolígonosNoConvexos”.
110
t-buena iluminación en el plano
16. ILUMINACIÓN DE UNA NUBE DE FOCOS CON OBSTÁCULO CONVEXO POR ACHE.
A continuación se recuerda la descripción esquemática del algoritmo de cálculo de la 1buena iluminación de una nube de focos con un obstáculo convexo.
____________________________________________________________________________
Algoritmo de 1−buena iluminación para un obstáculo convexo.
ENTRADA: Un polígono convexo C con n vértices y un conjunto F = {f1, ..., fn} de n focos exteriores a él.
SALIDA: La región 1−bien iluminada por F, W1 (F, C).
1. Preproceso: Determinar las cuñas que producen la prolongación de los lados del convexo y estudiar los focos que pertenecen a cada cuña. Este preproceso se debe realizar tanto en las cuñas hacia la derecha como las cuñas hacia la izquierda.
2. Cálculo: El algoritmo consta de dos partes. La primera de ellas consiste en el cálculo de una zona poligonal A, que es la unión de los cierres convexos dinámicos de los subconjuntos de F linealmente separados de C. La segunda parte consiste en completar A con sectores internos de buena iluminación Si, que no aparecen en la unión de los cierres convexos. Así, la zona bien iluminada por los focos de F = {f1, f2, ..., fk} será A Uk Detalladamente estos son los pasos de esta parte de cálculo.
111
i=1
Si.
t-buena iluminación en el plano
(a) Construcción del primer convexo:
- Trazar una recta t que contiene a un lado cualquiera de C.
- Construir el cierre convexo de todos los puntos exteriores a t.
(b) Cálculo de A. Unión de los cierres convexos dinámicos:
- Girar en sentido negativo la recta t y construir de forma dinámica la unión de los cierres convexos que irán apareciendo en sentido negativo y desapareciendo en sentido izquierdo.
(c) Completar con sectores internos Si:
- Para cada foco fi construir su recta soporte ri a C.
- Girar ri en sentido negativo alrededor de C hasta encontrar el primer foco que aparece, fj.
- Calcular la recta soporte rj de fj a C. - Hallar el sector Si y unirlo a la zona bien iluminada A.
____________________________________________________________________________
112
t-buena iluminación en el plano
Los pasos fundamentales dados a modo de resumen son:
1.
Cálculo de cierres convexos: Girar una recta apoyándose en los vértices del
obstáculo y en los focos de luz, calculando así los diferentes cierres convexos que se encuentran en el semiespacio en donde no está el obstáculo. El algoritmo para calcular el cierre convexo es “QuickHull” [BERG97], que consta de las siguientes iteraciones:
a) Encontrar los cuatro puntos extremos de una nube de puntos (norte, sur, este y oeste) y formar un cuadrilátero con éstos punto como esquinas (aunque podría darse el caso de obtenerse sólo un triángulo e incluso una línea). Todos los puntos que hayan quedado dentro de este cuadrilátero no formarán ya parte de la frontera.
b) Los puntos exteriores al cuadrilátero se encontrarán divididos en cuatro (o menos) zonas no comunicadas. En cada una de éstas regiones se obtendrá el punto más alejado al lado del cuadrilátero adyacente a dicha zona. De esta forma se obtiene una figura de hasta ocho vértices que descartará los puntos interiores como pertenecientes al borde del cierre convexo y dividirá los puntos exteriores en hasta ocho nuevas regiones.
c) Se sigue actuando para cada nueva región según las reglas anteriores hasta que no queden vértices externos a la figura.
113
t-buena iluminación en el plano
2.
Zonas a añadir: Para cada foco de luz, calcular sus rectas soporte. Para cada
recta soporte calcular el foco de luz más cercano que se encontrará cuando se gire dicha recta sobre el obstáculo. Finalmente añadir la zona 1-bien iluminada a la región total como resultado de focos de luz que iluminan una zona pero no se ven entre sí.
A continuación se detalla el diagrama de secuencia del algoritmo:
Figura 16.1: Diagrama de secuencia algoritmo “IluminacionConObstaculosACHE”.
114
t-buena iluminación en el plano
17. VALORACIÓN ECONÓMICA DEL PROYECTO.
En este apartado se detalla la valoración económica de desarrollo del proyecto. Para su realización se ha dividido en tres grandes apartados: Honorarios, Hardware y Software, que a continuación se explican. Al final se detalla el presupuesto total del proyecto.
a. Honorarios. En este apartado se van a contabilizar los costes asociados al personal implicado en el desarrollo del proyecto. De acuerdo con las normas de La Universidad Pontificia Comillas en cuanto a la realización del proyecto final de carrera, el desarrollo es unipersonal realizado por el alumno.
Dicho alumno en el desarrollo ha tenido que adoptar diferentes tipos de perfiles, que son: •
Jefe de Proyecto: Persona encargada de la realización con el cliente durante las distintas fases del proyecto. Es el encargado de que la descripción funcional del cliente se lleve a cabo y que los requisitos sean satisfechos. También es el que dirige y coordina el trabajo para la consecución del proyecto. La estimación de dicho papel en la vida del proyecto es de un 15%.
115
t-buena iluminación en el plano
•
Analista: Dicho rol se ocupa de elaborar el catálogo de requisitos y de trasladar las especificaciones técnicas y funcionales en modelos de clases e interacción de objetos, junto con la elaboración de las especificaciones de las interfaces. Para la consecución de dicho trabajo son necesarios altos conocimientos de las diferentes herramientas de trabajo y es el encargado de realizar las funciones de control técnico. Se estima que la dedicación de este perfil en el total del proyecto es de un 40%.
•
Programador: Es el encargado de desarrollar el código que dará lugar a la aplicación, según las especificaciones e indicaciones técnicas recogidas. La dedicación a este perfil se estima en un 45% del tiempo total del proyecto (desarrollo, pruebas y documentación).
Cada uno de los diferentes perfiles tiene asociado unos honorarios diferentes. Dichos honorarios son los especificados a continuación:
o Jefe de Proyecto: 70 Euros / hora.
o Analista: 55 Euros / hora.
o Programador: 40 Euros / hora.
116
t-buena iluminación en el plano
La duración total del proyecto se ha estimado en 400 horas, que se reparten a lo largo de todo el tiempo de desarrollo. Los honorarios globales del proyecto se muestran en la siguiente figura:
Perfil Porcentaje Jefe de Proyecto 15% Analista 40% Programador 45%
Horas dedicadas Precio / hora 60 horas 70 € 160 horas 55 € 180 horas 40 €
Total Proyecto 4.200 € 8.800 € 7.200 €
TOTAL
20.200 €
b. Hardware. En este apartado se van a valorar todos aquellos dispositivos que han sido necesarios para el desarrollo de la aplicación.
Como ya se dijo en el capítulo de recursos utilizados, se ha necesitado un equipo Dell Latitude D-610 y una conexión a Internet durante un periodo aproximado de 6 meses. A continuación se muestra una tabla con el presupuesto Hardware necesitado.
Concepto Precio unitario Dell Latitude D-610 1.600 € Conexión Internet 38 €
Vida útil 36 meses 1 mes
Tiempo necesitado 6 meses 6 meses TOTAL
117
Precio imputado 270 € 228 € 498 €
t-buena iluminación en el plano
c. Software. En este apartado se van a valorar todas aquellas aplicaciones necesarias que tengan algún cargo de dinero, necesarias para el desarrollo del Software así como para realizar la documentación.
El software principal necesario para la aplicación está formado en su mayoría por software libre, como por ejemplo Java Virtual Machine, el paquete de desarrollo Java 2 Development Kit, así como el entorno de desarrollo Netbeans 5.5.
La aplicación puede funcionar tanto en plataformas Windows como en plataformas Linux de 32 bits.
El precio del software que se necesita licencia para el desarrollo es el siguiente:
Concepto S.O. Windows XP Professional Microsoft Office Acrobat Proffessional Visual Paradigm
Precio unitario 450 € 600 € 550 € 1.000 €
Vida útil 48 meses 36 meses 24 meses 12 meses
Tiempo necesitado 6 meses 6 meses 6 meses 6 meses TOTAL
118
Precio imputado 56 € 100 € 125 € 500 € 781 €
t-buena iluminación en el plano
d. Presupuesto total. El presupuesto total al que asciende el proyecto, como la suma de los costes calculados en los apartados anteriores, es:
Concepto Honorarios Hardware Software
Coste 20.200 € 498 € 781 €
TOTAL SIN IVA
21.479 € IVA = 16%
TOTAL CON IVA
24.916 €
119
t-buena iluminación en el plano
18. CONCLUSIONES.
La informática ha dado una nueva dimensión a la forma de discurrir actual. Las ciencias clásicas como La Geometría han adquirido una dimensión totalmente nueva gracias a las posibilidades que ofrecen las herramientas de la computación.
Es por ésto, que se ha conseguido de una manera sencilla una herramienta capaz de, mediante heurísticas, poder hacer múltiples comprobaciones sobre unas teorías y postulados totalmente nuevos e innovadores. Los algoritmos de resolución de la t-buena iluminación se aplican de una manera satisfactoria, comprobando gracias a las pruebas que sus fundamentos son correctos.
El trabajo no queda aquí; ¿se pueden encontrar algoritmos eficientes de resolución para unos valores de la variable t superiores en el caso de polígonos no convexos? ¿Y en el caso de obstáculos convexos? ¿Cómo aplicar estas teorías en el espacio tridimensional?
Queda pues un largo camino que recorrer hasta que se disponga de unas teorías completas que permitan tener herramientas de alto nivel para el estudio de la iluminación, pero un paso más se ha dado con éste proyecto.
120
t-buena iluminación en el plano
19. BIBLIOGRAFÍA
[CANA04]: Santiago Canales Cano: “Métodos Heurísticos en problemas geométricos. Visibilidad, iluminación y vigilancia”.
[ABEL92]: Abellanas, M; Hernández, G; Lodares, D: “Kernels and Depth of a Convex Polygon”, sixth SIAM Conference on Discrete Mathematics, Vancouver, (Canadá), 1992.
[TUKE75]: Tukey, J.W.: “Mathematics and the picturing of data”, Proceedings of the International Congress of Mathematicians, 2, (1975), pp. 523-531.
[DIAG02]:
Markus
Falkhausen:
“Contributions
to
information
technology”,
http://www.falkhausen.de/en
[API_07]: Sun Microsystems, Inc.: “JavaTM Platform, Standard Edition 6 API Specification”, http://java.sun.com/javase/6/docs/api/
[VILL98]: Agustín de la Villa: “Problemas de álgebra”. 1998.
[WIKI07]: Wikipedia, la enciclopedia libre: http://www.wikipedia.org.
[BERG97]: M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf: "Computational Geometry, Algorithms and Applications". Springer, 1997.
121
t-buena iluminación en el plano
20. GLOSARIO DE TÉRMINOS
o
Algoritmo ACHE: Algoritmos de t-buena iluminación creados que no se basan
en la fuerza bruta. Sus siglas son de los siguientes apellidos: Abellanas, Canales, Hernández y Echávarri.
o
Algoritmo de fuerza bruta: Los algoritmos de fuerza bruta se basan en un
paradigma de diseño que consiste en resolver el problema “rudamente”. Consiste en probar sistemáticamente todas y cada una de las posibles soluciones al problema y confía en la capacidad de cálculo del ordenador para conseguir resolverlo. Los algoritmos de fuerza bruta son una cota superior del tiempo de resolución de un problema.
o
Cierre convexo: Dado un conjunto de puntos en el plano, se define el cierre
convexo como el menor polígono convexo que contiene a todos los puntos y por tanto dado cualquier par de puntos (x, y) pertenecientes al conjunto, se cumple que el segmento xy está contenido en dicho polígono. De una forma intuitiva, es el “contenido de la figura que formaría una banda elástica que rodeara a una nube de punto una vez que se soltara.
Figura 13.1: Definición intuitiva de cierre convexo.
122
t-buena iluminación en el plano
o
Convex hull: Véase cierre convexo.
o
Foco de Luz: En los teoremas de t-buena iluminación, se denomina Foco de Luz
como aquel punto en el plano que emite iluminación en todos los sentidos. Inicialmente su alcance es ilimitado.
o
Geometría Computacional: Es la disciplina que se ocupa del diseño y análisis de
algoritmos eficientes que resuelven problemas geométricos, donde concurren elementos puramente matemáticos con cuestiones y herramientas de la informática.
El término “Geometría Computacional” lo introduce M.I. Shamos en 1975 aunque en dicha fecha ya existen algunos trabajos previos enmarcados en esta disciplina.
La base fundamental que sustenta La Geometría Computacional es que la potencia de cálculo de los ordenadores hacen resolubles ciertos problemas geométricos hasta la fecha imposibles de solucionar por la gran cantidad de operaciones que se debían realizar. En éstas nuevas reformulaciones de los problemas geométricos, los objetos geométricos pasan a ser estructuras de datos, y las metodologías clásicas de resolución de problemas se convierten en algoritmos eficientes que trabajan con dichas estructuras de datos.
o
Hiperplano: Se define un hiperplano como
Se trata de la expresión c1 x1 + c2 x2 + … + cn xn = α, que para el caso de n = 2, se tiene: c1 x1 + c2 x2 = α, ecuación que corresponde a la de una recta del plano. Por tanto un hiperplano es la generalización al espacio n-dimensional del concepto de recta.
123
t-buena iluminación en el plano
En un espacio de una única dimensión un hiperplano es un punto. En un espacio bidimensional un hiperplano es una recta. En un espacio tridimensional un hiperplano es un plano corriente. Este concepto puede ser aplicado a espacios de más de 3 dimensiones.
o
Obstáculo: Cualquier elemento en el plano que afecta y modifica la propagación
de la iluminación de los focos de luz
o
Polígono convexo: Hay muchas maneras de definir si un polígono es convexo.
De una manera intuitiva un polígono convexo es aquel que no tiene “entrantes”, es decir, está todo contenido en el mismo semiplano determinado por cualquier recta que contiene a uno de sus lados. Cualquier línea que contiene un lado del polígono no contiene un punto del interior del polígono. Un polígono convexo es aquel cuyos ángulos internos son todos menores de 180º.
Polígono no convexo Polígono convexo
Figura 13.2: Ejemplo de polígono convexo / polígono no convexo.
o
Semiplano: A partir del concepto de hiperplano, se puede definir el concepto de
semiplano, como el conjunto de punto que verifica que:
o bien:
124
t-buena iluminación en el plano
En el primer caso (1) se denomina semiplano inferior y el segundo caso (2) semiplano superior.
Estas dos definiciones de semiplano se refieren a semiplanos cerrados, ya que las desigualdades son de la forma mayor-igual o menor-igual Si las desigualdades son estrictas, es decir, mayor y menor estrictamente, entonces se dice que se trata de semiespacios abiertos.
Cada hiperplano define dos semiplanos. Gráficamente se trata de la porción del espacio que está por encima del hiperplano (semiplano superior) o por debajo del hiperplano (semiplano inferior).
Figura 13.3: Ejemplo semiespacios generados por un hiperplano.
125
t-buena iluminación en el plano
o
t-buena iluminación: Sea F = {f1, f2, …, fk} un conjunto de k luces o focos en el
plano, y O un conjunto de obstáculos. Un punto p está t-bien iluminado por L, 1≤t≤k/2, si todo semiplano con borde en p contiene al menos t focos de L que lo iluminan.
126
t-buena iluminación en el plano
ANEXO 1: MANUAL DE USUARIO
127
t-buena iluminación en el plano
a. VENTANA PRINCIPAL La ventana principal de la aplicación, desde donde se maneja toda la aplicación y operaciones de t-buena iluminación, es la siguiente.
Panel lateral Panel inferior Zona de Dibujo Panel superior Menú
Dicha ventana principal contiene todos los elementos necesarios para la ejecución de los diferentes algoritmos de t-buena iluminación. Su uso es sencillo y manejable únicamente con el ratón sin necesidad de tener que introducir comandos.
128
t-buena iluminación en el plano
La ventana está dividida en 5 grandes zonas destacadas en la figura anterior. Cada una de dichas zonas tiene un cometido diferente y específico. Sus funcionalidades fundamentales son:
o
Panel lateral: Con el Panel Lateral se controla la definición de los focos de luz, obstáculos y polígonos. Además se especifica con dicho panel el problema que se quiere resolver, el algoritmo a emplear y el modo de ejecución. Por último también se puede controlar la ejecución del algoritmo y ver su estado de ejecución.
o
Panel inferior: En el panel inferior se pueden especificar las coordenadas de dónde es encuentra el ratón, la definición del mallado del dibujo y de los ejes de coordenadas.
o
Zona de Dibujo: En La Zona de Dibujo se muestran los elementos definidos, los elementos auxiliares de la ejecución y los resultados obtenidos por los diferentes algoritmos. Pulsando sobre dicha zona es como se definen los elementos oportunos que se han especificado en el panel lateral.
o
Panel Superior: En el panel superior se encuentran las opciones de cargar una imagen de fondo, guardar los resultados obtenidos en un archivo y borrar todas las definiciones hechas anteriormente sobre La Zona de Dibujo.
o
Menú: En el menú se controlan las opciones de iluminación, como son las regiones t-bien iluminadas a calcular y la degradación de iluminación de las luces. También se pueden modificar las variables que definen el modo de visualizar los elementos, como son los colores, mostrar / ocultar coordenadas, etc.
129
t-buena iluminación en el plano
b. PANEL LATERAL:
CREAR ELEMENTOS Crear foco de luz Crear polígono cerrado Crear obstáculo Cerrar polígono / obstáculo
CASOS DE ESTUDIO Definir problema de t-buena iluminación a resolver Determinar algoritmo de resolución Determinar modo de ejecución del algoritmo
EJECUCIÓN DE ALGORITMOS Ejecutar Parar Pausar
CONTROL DE EJECUCIÓN Porcentaje de ejecución Retardo de los algoritmos
El panel lateral es el elemento fundamental de control de la aplicación. Dicho panel se divide en cuatro grandes zonas:
o Crear elementos: Para definir alguno de los tres elementos que intervienen en el estudio de la t-buena iluminación, hay que especificar cuál de ellos se quiere definir en La Zona de Dibujo. Dicha zona contiene pues tres botones correspondientes con los tres elementos fundamentales de estudio: “Foco Luz”, 130
t-buena iluminación en el plano
“Polígono” y “Obstáculo”. Eligiendo uno de ellos, la aplicación está preparada para que el Usuario defina dicho elemento en La Zona de Dibujo.
El botón “Cerrar” que aparece en dicha zona sirve para cerrar los polígonos y obstáculos que están siendo definidos en La Zona de Dibujo. Cuando se pulsa dicho botón el elemento pasa a estar totalmente definido y es un elemento más del plano.
o
Casos de estudio: Sirve para definir el caso de estudio de la t-buena iluminación que se quiere resolver y cómo hacerlo. Consta de:
o Problema de iluminación: Con el menú que se despliega, el Usuario elige el problema que quiere resolver: t-buena iluminación de una nube de focos, de un polígono convexo, de un polígono no convexo o de una nube de focos con obstáculos.
o Algoritmo: Con el menú que se despliega, el Usuario determina el algoritmo de resolución de dicho problema de iluminación. Según el problema de iluminación determinado anteriormente, aparecerán diferentes algoritmos.
131
t-buena iluminación en el plano
o Modo de ejecución: Con el menú que se despliega, el Usuario determina el modo de resolución de dicho problema de iluminación con el algoritmo especificado. Según el problema de iluminación determinado anteriormente y el algoritmo elegido, aparecerán diferentes modos de resolución.
o
Ejecución de algoritmos: Una vez definidos los elementos, los métodos y opciones de ejecución llega el momento en el que el Usuario decide su ejecución. Con la zona de ejecución de algoritmos el Usuario puede iniciar la ejecución con el botón “Ejecutar”, pausar el algoritmo cuando se está ejecutando con el botón “Pausar” o pararlo totalmente con el botón definido como “Parar”.
o Control de ejecución: Dicha zona del panel lateral muestra información sobre la ejecución del algoritmo en porcentaje, gracias a una barra de progreso (“progressBar”) que se ha denominado “Porcentaje de ejecución”. En los algoritmos que se ejecutan con retardo, el Usuario puede especificar dicho retardo entre pasos consecutivos con una barra situada en la misma zona denominada “Retardo de algoritmos”.
132
t-buena iluminación en el plano
c. PANEL INFERIOR: El panel inferior es un panel auxiliar de La Zona de Dibujo de la aplicación en el cual se definen diversos elementos auxiliares de dicha zona.
MOSTRAR EJES MOSTRAR MALLADO Grano de mallado Selección de mallado
COORDENADAS DE RATÓN Coordenada Y Coordenada X
o Mostrar ejes: Con la checkbox denominada “Mostrar ejes”, el Usuario determina si quiere que en La Zona de Dibujo aparezcan los ejes de coordenadas X=0 e Y=0. El inicio de coordenadas está definido en el centro de la zona de ejecución.
o Mostrar mallado: El mallado consiste en una serie de rectas auxiliares paralelas a los ejes que dividen el plano en diferentes cuadriláteros. El Usuario define si quiere mostrar el mallado y el grano de éste, es decir, el número de cuadrados en los que se divide el plano.
133
t-buena iluminación en el plano
o Coordenadas de ratón: Las etiquetas definidas como “Coordenada X” y “Coordenada Y” muestran al Usuario las coordenadas donde se encuentra el ratón en cada momento sobre La Zona de Dibujo. Las coordenadas que se muestran están referenciadas sobre los ejes de coordenadas iniciales, es decir, sobre el centro de La Zona de Dibujo.
d. ZONA DE DIBUJO:
Polígono Obstáculo Focos de luz
134
t-buena iluminación en el plano
La Zona de Dibujo es un panel donde se muestran todos los elementos definidos (focos de luz, polígonos y obstáculos) así como los resultados de los algoritmos ejecutados y los elementos auxiliares que se utilizan en la ejecución de los algoritmos.
e. PANEL SUPERIOR:
BORRAR ZONA DE DIBUJO CARGAR IMAGEN DE FONDO GUARDAR RESULTADOS
El panel superior tiene únicamente tres botones, cuyas funcionalidades son:
o Guardar resultados: La aplicación hace una copia de La Zona de Dibujo y lo guarda en el sistema de ficheros como una imagen con extensión *.jpg. En dicha imagen aparece exactamente lo que hay definido y visible en ese momento en La Zona de Dibujo, por lo que si se está a mitad de ejecución y se muestran diversas líneas auxiliares, también aparecerán en la imagen guardada.
135
t-buena iluminación en el plano
Para guardar la imagen con las especificaciones deseadas por el Usuario, aparece la siguiente pantalla auxiliar:
En el campo denominado como “Directorio”, se especifica el directorio del árbol de directorios del sistema donde se desea guardar la imagen. En el campo denominado como “Nombre del archivo”, se especifica el nombre de la imagen que se va a guardar, no siendo necesario poner la extensión de dicho archivo, ya que como se dijo antes, la extensión de la imagen va a ser *.jpg
o Cargar imagen de fondo: Con dicha opción, la aplicación genera una nueva ventana de elección de un archivo de tipo imagen. La imagen que escoja el Usuario será cargada como fondo en La Zona de Dibujo, sobre la cual se pintarán todos los demás elementos.
136
t-buena iluminación en el plano
La nueva ventana que aparece es la siguiente:
o Borrar Zona de Dibujo: Con ése botón que aparece en el panel superior, el Usuario puede borrar todos aquellos elementos que se han definido previamente, quedando así La Zona de Dibujo completamente limpia.
137
t-buena iluminación en el plano
f. MENÚ:
El menú de la aplicación se divide en dos grandes ítems, según las opciones que se pueden configurar para la resolución de los diferentes problemas. Estos dos ítems son:
o Opciones de iluminación: Configura todas aquellas variables que afectan a variables de iluminación en la resolución de los diferentes casos de estudio de la t-buena iluminación. Define tanto la variable t, como la degradación de la iluminación de los focos de luz utilizada en los algoritmos de fuerza bruta. Las diferentes opciones que hay en éste menú son:
a. Pintar zonas con t menor: Cuando el Usuario de la aplicación define un valor de t máximo para los diferentes algoritmos de iluminación, tiene la
138
t-buena iluminación en el plano
posibilidad de que se pinten las regiones bien iluminadas con una variable t menor a la que ha definido como máxima.
b. Definir variable t: Para todos los algoritmos de t-buena iluminación, se puede definir la variable t que se quiere estudiar. Dicha variable t estará en el intervalo [1, 6].
c. Degradación de luz: El Usuario tiene la opción de que en los algoritmos de fuerza bruta que se han desarrollado, pueda definir una degradación de luz, es decir, una máxima distancia por la cual si un objeto se encuentra a una distancia de un foco de luz mayor de la máxima, dicho foco de luz no iluminará al objeto.
d. Configurar máxima distancia: Una vez que el Usuario quiere utilizar la opción en algoritmos de fuerza bruta de una degradación de luz, puede definir cuál es dicha distancia máxima. Si se utiliza esta opción, al Usuario le aparece una ventana auxiliar de configuración como la siguiente:
139
t-buena iluminación en el plano
e. Mostrar áreas de iluminación de focos: Si se selecciona dicha opción, aparece para cada foco de luz definido en el plano, una circunferencia que delimita la zona del plano a la que dicho foco de luz ilumina.
f. Crear focos aleatoriamente: Es una opción alternativa a crear los focos pulsando sobre La Zona de Dibujo. Con dicha opción el Usuario puede definir un número determinado de focos que se colocarán aleatoriamente sobre el plano. Si se utiliza dicha opción del menú, aparecerá una ventana auxiliar a la ventana principal de uso de esta opción, como la siguiente:
o Opciones visuales: Configura todas aquellas variables que afectan a la visualización de los diferentes objetos en La Zona de Dibujo. Dichas opciones son fundamentalmente la de configurar los colores de los diferentes elementos dibujados, mostrar la numeración de los vértices de los polígonos u obstáculos que se ha llevado a cabo y la de mostrar las coordenadas en el plano de los focos de luz, vértices de polígonos y vértices de obstáculos.
140
t-buena iluminación en el plano
a. Numeración de polígonos: Muestra en La Zona de Dibujo, la numeración real de los vértices por los que cada polígono se define.
b. Numeración de obstáculos: Muestra en La Zona de Dibujo, la numeración real de los vértices por los que cada obstáculo se define.
c. Coordenadas de focos de luz: Muestra en La Zona de Dibujo las coordenadas en el plano de cada foco de luz definido.
d. Coordenadas de polígonos: Muestra en La Zona de Dibujo las coordenadas en el plano de los vértices que definen a cada polígono
e. Coordenadas de obstáculos: Muestra en La Zona de Dibujo las coordenadas en el plano de los vértices que definen a cada obstáculo.
f. Color regiones de iluminación: Esta opción muestra una ventana auxiliar a la ventana principal que sirve para definir y modificar los colores de cada región de t-buena iluminación. La ventana mostrada es:
141
t-buena iluminación en el plano
g. Color focos de luz: Esta opción muestra una ventana auxiliar a la ventana principal que sirve para definir y modificar los colores de los focos de luz definido. En un principio el color de dichos focos, así como de la etiqueta de sus coordenadas es rojo. La ventana mostrada es:
h. Color de polígonos: Esta opción muestra una ventana auxiliar a la ventana principal que sirve para definir y modificar los colores de las líneas que delimitan un polígono. En un principio el color de los polígonos es azul. La ventana mostrada es:
142
t-buena iluminación en el plano
i. Color de obstáculos: Esta opción muestra una ventana auxiliar a la ventana principal que sirve para definir y modificar los colores de las líneas que delimitan un obstáculo. En un principio el color de los obstáculos es negro. La ventana mostrada es:
143
t-buena iluminación en el plano
g. EJECUCIÓN: Las diferentes opciones de resolución de los problemas de la t-buena iluminación se especifican en el siguiente gráfico.
CASOS DE ESTUDIO
MÉTODO
EJECUCIÓN
Fuerza bruta
NUBE DE FOCOS
Fuerza bruta
Simple Simple
INTERIOR POLÍGONOS CONVEXOS Algoritmo ACHE
Paso a paso Con retardo
Fuerza bruta
Simple Simple
INTERIOR POLÍGONOS NO CONVEXOS Algoritmo ACHE
Paso a paso Con retardo
Fuerza bruta
Simple Simple
NUBE DE FOCOS CON OBSTÁCULOS Algoritmo ACHE
Paso a paso Con retardo
Según este gráfico, hay 13 diferentes modos de ejecución en total para los 4 problemas expuestos.
144
t-buena iluminación en el plano
1. NUBE DE FOCOS: Pasos: a. Marcar “Crear foco de luz” en el Panel Lateral. b. Definir una serie de focos en el plano. c. Escoger “Problema de iluminación Æ Nube de focos” en el Panel Lateral. d. Escoger “Algoritmo Æ Fuerza bruta” en el Panel Lateral. e. Pulsar el botón “Ejecutar” en el Panel Lateral. f. Esperar hasta la resolución total del algoritmo.
2. INTERIOR DE POLÍGONOS CONVEXOS Pasos: a. Marcar “Crear polígono” en el Panel Lateral. b. Definir un polígono convexo en el plano, marcando de manera secuencial sus vértices. c. Escoger “Problema de iluminación Æ Polígonos convexos” en el Panel Lateral. d. Marcar el Algoritmo a utilizar en el Panel Lateral (“Fuerza bruta” o “ACHE”). e. Elegir el modo de ejecución. f. Pulsar el botón “Ejecutar” en el Panel Lateral.
145
t-buena iluminación en el plano
i. Si se escogió “Algoritmo Æ ACHE” y “Modo de ejecución Æ Paso a paso”, el Usuario debe de especificar a la aplicación el avance de la ejecución en cada paso dado. g. Esperar hasta la resolución total del algoritmo. 3. INTERIOR DE POLÍGONOS NO CONVEXOS Pasos: a. Marcar “Crear polígono” en el Panel Lateral. b. Definir un polígono no convexo en el plano, marcando de manera secuencial sus vértices. c. Escoger “Problema de iluminación Æ Polígonos no convexos” en el Panel Lateral. d. Marcar el Algoritmo a utilizar en el Panel Lateral (“Fuerza bruta” o ACHE”). e. Elegir el modo de ejecución. f. Pulsar el botón “Ejecutar” en el Panel Lateral. i. Si se escogió “Algoritmo Æ ACHE” y “Modo de ejecución Æ Paso a paso”, el Usuario debe de especificar a la aplicación el avance de la ejecución en cada paso dado. g. Esperar hasta la resolución total del algoritmo.
146
t-buena iluminación en el plano
4. NUBE DE FOCOS CON OBSTÁCULOS Pasos: a. Marcar “Crear obstáculo” en el Panel Lateral. b. Definir un obstáculo convexo en el plano, marcando de manera secuencial sus vértices. c. Marcar “Crear foco de luz” en el Panel Lateral. d. Definir una nube de focos alrededor del obstáculo. e. Escoger “Problema de iluminación Æ Nube de focos con obstáculos” en el Panel Lateral. f. Marcar el Algoritmo a utilizar en el Panel Lateral (“Fuerza bruta” o “ACHE”). g. Elegir el modo de ejecución. h. Pulsar el botón “Ejecutar” en el Panel Lateral. i. Si se escogió “Algoritmo Æ ACHE” y “Modo de ejecución Æ Paso a paso”, el Usuario debe de especificar a la aplicación el avance de la ejecución en cada paso dado. i. Esperar hasta la resolución total del algoritmo.
147