Aqui se tratan diversos temas de la materia Tópicos Selectos de Algorítmica, donde los alumnos contribuyen con aportaciones interesantes sobre los temas publicados en este weblog
De entre los algoritmos geométricos y sus aplicaciones ¿cuáles te han parecido más representativos, utiles o interesantes? ¿has encontrado algún ejemplo de programas que usen los algoritmos geométricos para resolver algún problema?
posted by Lourdes / Hypatia @ 9:18 p.m.
6 comments
Ingeniera en Computación, egresada de la Facultad de Ingeniería de la UNAM, con una Maestría en Administración de las Telecomunicaciones, del Tecnológico de Monterrey, Campus Ciudad de México. Actualmente profesora de cómputo y colaboradora en sitios de divulgación como http://seti.cl, http://ted.org, http://latierrahabla.seti.org entre otros; también trabajó como ingeniera de software en el Tecnológico de Monterrey, Campus Ciudad de México durante 6 años. Su interés en la astronomía y las ciencias inicio en 1985, al ver por primera vez la serie COSMOS, de Carl Sagan; y aunque no pudo estudiar astronomía como profesión, su interés se ha mantenido durante todos estos años.
6 Comments:
Las aplicaciones que encontramos para este tipo de algoritmos son referentes a las tecnologías CAD (diseño asistido por computadora) por sus siglas en ingles. Mediante ellas realizamos polígonos y figuras que nos ayudan a poder expresar diferentes estructuras dentro de programas como MAYA utilizados en el diseño grafico.
Los nurbs son también estructuras basadas en algoritmos geometricos que nos ayudan a resolver problemas que los poligonos no pueden realizar, mediante ellos podemos sacar figuras que son mas complejas y que son mas parecidas a estructuras reales de personas o casas.
Los algoritmos geometricos son usados en muchos casos principalemente en el diseño por ejemplo en la creación de prototipos de autos en los cuales tenemos que crear figuras que son geometricas pero no necesariamente definidas como las tradicionales.
la verdad son de gran utilidad por que los podemos encontrar dentro de cualquier estructura de la vida comun, por esta razon el simple hecho de poder enlazarlos con las matematicas, fortalece aun mas el poder encontrarlos en cualquier figura geometrica definida.
Lizbeth Meza Gutierrez
Los algoritmos geomtricos que mas me han interesado son los que se aplican para crear figuras geometicas por medio de puntos.
encontre algunas aplicaciones de *algoritmos para diseñar:
*algoritmos Lepp-Delaunay para la generación automática de mallas adaptadas a geometrías complejas.
*algoritmos Lepp-Bisección para refinamiento / desrefinamiento de triangulaciones en dos y tres dimensiones.
*algoritmos para generación de mallas no obtusas en el borde y poco obtusas en el interior, de acuerdo a requerimientos de métodos de volúmenes finitos.
paralelización de los algoritmos Lepp-Bisección.
Mejoramiento de triangulaciones no Delaunay.
Se define un problema geométrico de cálculo: como aquella tarea docente que demanda la realización de determinadas acciones (prácticas o mentales) encaminadas a transformar ciertas relaciones entre los elementos de un ente geométrico y se pide determinar algún o algunos elementos del mismo para lo cual tiene que recurrirse al cálculo como método o procedimiento fundamental; mientras que su vía de solución se obtiene con ayuda de procedimientos algorítmicos o heurísticos.
Los algoritmos geomtricos que mas me han interesado son los que se aplican para crear figuras geometicas por medio de puntos.
encontre algunas aplicaciones de *algoritmos para diseñar:
*algoritmos Lepp-Delaunay para la generación automática de mallas adaptadas a geometrías complejas.
*algoritmos Lepp-Bisección para refinamiento / desrefinamiento de triangulaciones en dos y tres dimensiones.
*algoritmos para generación de mallas no obtusas en el borde y poco obtusas en el interior, de acuerdo a requerimientos de métodos de volúmenes finitos.
paralelización de los algoritmos Lepp-Bisección.
Mejoramiento de triangulaciones no Delaunay.
La generalización tal vez sea el proceso cartográfico más complejo al que deba enfrentarse el cartógrafo. La NCGIA (1989) la define de forma simple como "un grupo de técnicas que permiten mantener la cantidad de información presente en un mapa a pesar de reducir la cantidad de datos".
Es en estos últimos años cuando más interés está tomando esta línea de trabajo, cuando cada vez es mayor la importancia, en distintos ámbitos de nuestra sociedad, de los sistemas cartográficos digitales y sobre todo de los Sistemas de Información Geográfica (S.I.G.). El cartógrafo se sirve de la generalización para enfatizar lo esencial y suprimir lo superfluo, reducir la complejidad del mapa en el proceso de reducción de escala, mantener las relaciones lógicas e inequívocas entre los elementos representados y para preservar la calidad estética, tratando siempre de favorecer la claridad y la comunicación de la información.
Uno de los aspectos negativos de la generalización tradicional o manual que se pretende eliminar con la generalización digital o automatizada es la enorme subjetividad que conlleva. Esta subjetividad viene motivada por la ausencia de unas reglas de generalización "universales", siendo la formación cartográfica de cada operador diferente. Incluso una línea puede aparecer como diferente habiendo sido la misma persona la que ha operado sobre ella, debido a la ausencia de repetitividad. En cambio, el proceso digital ofrecerá siempre el mismo resultado si los datos y parámetros de partida son los mismos, ya que la secuencia de operaciones será siempre la misma. Ahora bien, será necesario incorporar ese conocimiento cartográfico y geográfico que permite la generalización manual en el contexto digital, constituyendo uno de los mayores problemas que se presentan por ahora.
Asímismo, una de las fundamentales ventajas de la generalización automatizada es la creación de bases de datos independientes de la escala. En la actualidad se elabora una base de datos distinta para cada versión de un mismo mapa a distinta escala debido a que los datos procedentes de un mapa a escala mayor son excesivos o a que su propósito es diferente. Esto ocasiona una fuerte pérdida de tiempo y dinero, sobre todo a la hora de proceder a la actualización de los datos, que la sociedad demanda cada vez con mayor rapidez. Una base de datos independiente de la escala ofrece la posibilidad de almacenar una única base de datos con todos los datos necesarios para la elaboración mapas con distinta escala o de temática diferente. Para la elaboración de cada uno de ellos se recurrirá a distintas herramientas de generalización y filtrado, siempre que el resultado sea de calidad.
Por tanto, la actualidad e interés del tema justifica claramente el presente proyecto. Se pretende investigar en el proceso automatizado de la generalización, utilizando diversas técnicas, tanto en el dominio espacial como en el de la frecuencia, evaluando los resultados objetivamente a través de una serie de medidas evaluadoras, además de visualmente sobre el papel
Algoritmos de Douglas-Peucker y Visvalingam
El algoritmo de Douglas-Peucker (1973) es el algoritmo de generalización de líneas más utilizado. Es el único presente en programas comerciales de cartografía digital y S.I.G. como System9 o ArcInfo, además de estar siendo empleado por instituciones cartográficas para disminuir el tamaño de sus bases de datos digitales. Ha sido estudiado, comparado y analizado a fondo por muchos, por no decir todos, los que trabajan en generalización, con unos resultados casi siempre alabados, ya que se acercan, más que los de ningún otro, al producto de una generalización manual. Podemos decir que es el algoritmo "a batir" o la referencia establecida para evaluar los resultados de los nuevos algoritmos que van saliendo a la luz.
Precisamente se ha decidido incluirlo porque hasta la fecha es la mejor referencia para evaluar los resultados que proporcionan el resto de algoritmos.
Hola, a continuación las ligas de la demo que íbamos a checar en la última exposición de los algorítmos geométricos, son algunas páginas de applets de práctica de alguna clase de ingenieria de una universidad de España, espero que se den un tiempecito para echárles un ojo.
http://www.dccia.ua.es/dccia/inf/asignaturas/RG/applets/AppletGC01/appletGC01.html
http://www.dccia.ua.es/dccia/inf/asignaturas/RG/applets/Interseccion/Interseccion.htm
http://www.dccia.ua.es/dccia/inf/asignaturas/RG/applets/Delaunay/Delaunay.html
Gracias
Los algoritmos geométricos y en general lo que se conoce como la "Geometría Computacional" ha permitido que muchos campos de investigación tanto en la ciencia como en la tecnología avancen a pasos agigantados gracias a las excelentes herramientas que éste campo de la ciencia aporta. La resolución de problemas geométricos por medio de computadoras fue uno de los usos principales de los primeros equipos de propósito general en la segunda guerra mundial, para el cálculo de trayectorias balísticas de proyectiles de largo alcance.
Los problemas que pueden resolverse son algunos tan "sencillos" cómo el de averiguar si un punto está del lado izquierdo o derecho con respecto del centro de un segmento de recta dado, o por ejemplo el siguiente problema que es muy común y conocido:
Supongamos que tenemos dos pueblos a y b cercanos a una autopista recta, y una
compañía de tiendas de ferretería (servicios) quiere instalar una sucursal para atender la
demanda de ambos pueblos. ¿ En que punto p de la autopista debe instalarse la tienda,
de tal manera que las distancias de cada pueblo a la tienda sea mínima?
El problema, desde el punto de vista geométrico, consiste en hallar un punto p sobre
la recta l, tal que minimice la expresión:
d(a, p) + d(b, p)
Donde d(x, y) denota la distancia Euclideana entre dos puntos.
Este problema era conocido desde hace varios milenios, y fue resuelto por el matematico
Herón de Alexandría en el año 100 D.C.
Herón no hizo mas que emplear las leyes de reflexión de la luz sobre un espejo, establecidas
por Euclides en su libro Catoptrica. Las dos leyes establecen lo siguiente.
1. El ángulo de incidencia de la luz est´a sobre el mismo plano que el ´angulo de refracción.
2. La medida del ángulo de incidencia es igual a la del ángulo de refracción.
Inspirados en este principio, veremos que la localización del punto p, debe ajustarse a estas
leyes y de esta manera probaremos también que la luz se propaga siguiendo el camino
más corto.
El problema del círculo mínimo
Este es un problema del área de gerencia, cuya versión clásica se puede plantear de la
manera siguiente: Supongamos que tenemos n puntos en el plano representando clientes,
plantas de producción para ser abastecidas, escuelas, hospitales, mercados, pueblos o
cualquier otro tipo de institución. El problema consiste en ubicar un punto X en el plano
representando un servicio (proveedor, transmisor o despachados) de tal forma que la distancia
desde X hasta el punto mas alejado sea mínima. Este criterio es de gran utilidad
para ubicar hospitale, estaciones de policía, bomberos, almacenes de refacciones, antenas de telefonía, puntos de acceso a la red..etc. donde es necesario minimizar el peor de los casos en cuanto a tiempo de respuesta y calidad del servicio.
Problema de la galer´ıa de arte
Uno de los aspectos mas importantes de la geometr´ıa computacional es el de dividir
un polígono en triángulos. Una motivación bastante interesante hacia esta teoría es el
problema de las galerías de arte, propuesto por Klee en 1976.
La siguiente exposición esta tomada del libro Computational Geometry in C de Joseph
O’Rourke. Supongamos que tenemos una galería de arte, cuya planta tiene la forma de
un pol´ıgono de n vértices. La pregunta es la siguiente: ¿ Cuántos vigilantes son necesarios
para proteger la galería?
Cada vigilante se considera como un punto fijo dentro del salón y además, puede visualizar
todo a su alrededor en un ángulo de 360o. Los vigilantes no pueden ver a través
de las paredes. Se supone que los guardianes no bloquean la visión a nadie.
Antes de atacar el problema, necesitamos precisar algunos términos para obtener una
forma rigurosa del planteamiento, desde el punto de vista matemático.
Diremos que un guardián a puede ver el punto p en el polígono (o que p es visible desde
a), si el segmento ap está en el interior del polígono.
Diremos que un conjunto de guardianes cubre el polígono, si todo punto en el polígono es
visible para algún guardián.
Si una galería tiene planta rectangular, entonces un solo guardián es
suficiente para cuidarla. El guardia puede ser colocado en cualquier punto del rectángulo, lo mismo pasa en el caso de que la galería tenga forma de cualquier polígono convexo. Los casos interesantes son entonces aquellos que se presentan cuando la galería tiene forma de polígono no convexo*
Y así la lista de problemas teóricos continúa, así como la aplicación práctica para cada una de las soluciones a estos problemas, las cuales tenemos frente a nosotros y dificilmente nos damos cuenta.
Publicar un comentario
<< Home