Maximización con técnicas metaheurísticas de la región de visibilidad de un punto en un polígono

Abstract

El proyecto consiste en la creación de un software gráfico para la maximización de la región de visibilidad de un punto interior a un polígono P de n vértices, mediante la aplicación de tres metaheurísticas: Random Search, Simulated Annealing y Algoritmo Genético.

El objetivo principal de este proyecto es generar una aplicación que solucione problemas de visibilidad en una herramienta práctica y visual que permita comprender los métodos heurísticos y metaheurísticos en el campo de la Geometría Computacional. La aplicación se ha desarrollado en Python, un lenguaje de programación de código abierto que permite seguir mejorando el programa. El problema principal que se aborda consiste en minimizar el número de luces interiores a un polígono que lo iluminan por completo y se pretende aportar distintos métodos para la obtención del punto de máxima iluminación dentro de un polígono. Esta aplicación sirve como punto de partida para resolver el problema de mayor complejidad que pretende encontrar k puntos de máxima iluminación interiores a un polígono.

The project consists of the creation of a graphical software for maximizing the visibility region of a point inside a polygon P with n vertices, by applying three metaheuristics: Random Search, Simulated Annealing, and Genetic Algorithm.

The main objective of this project is to generate an application that solves visibility problems in a practical and visual tool that allows understanding heuristic and metaheuristic methods in the field of Computational Geometry. The application has been developed in Python, an open-source programming language that allows for continuous program improvement. The main problem addressed is to minimize the number of interior lights illuminating a polygon completely while providing different methods to obtain the point of maximum illumination within a polygon. This application serves as a starting point for solving the more complex problem that aims to find k points of maximum illumination inside a polygon.