Generalización de Mapas

Puntos de referencia de calidad a través de optimización

Décadas de investigación sobre la generalización han dado lugar a una gran cantidad de algoritmos heurísticos, evaluación del desempeño de los cuales es de vital importancia para elegir el más adecuado para una determinada aplicación. Los métodos apropiados de evaluación, sin embargo, que falta. Se propone un enfoque basado en métodos de optimización adoptadas desde el ámbito de la investigación de operaciones.

Conducir a su destino en vacaciones, usted puede preguntarse por qué el idílico pueblo por el camino no está representado en el mapa. ¿Es porque un cartógrafo decidió omitir el pueblo para mejorar la legibilidad del mapa? Es más probable hoy que un equipo hizo el trabajo, como “generalización”, la decisión sobre el que se detallan a representar en un mapa a escala determinada, se ha convertido en alto grado de automatización. El mapa de la Figura 1, por ejemplo, muestra un pueblo representado por los polígonos de color rojo-marrón. La aplicación de la generalización usando un algoritmo de la región de crecimiento elimina todo el pueblo en el mapa (Figura 2). Esto ocurre porque el algoritmo utiliza una regla de fusión de todos los polígonos más pequeños de 0,4 km2 con su vecino más similar. ¿Es esta una buena regla? Es difícil de decir, incluso teniendo en cuenta los criterios por los que se hace un buen mapa.

c0260
Figura 1 y 2

Requerimientos

Una manera obvia de mejorar el rendimiento de los algoritmos de generalización es aumentar su velocidad. Esto, sin embargo, no aborda el problema de llegar a soluciones satisfactorias. Aquí hay enfoques de optimización del campo de la investigación de operaciones, esto parece apropiado. En general, estos enfoques se basan en un modelo que abarca un conjunto de requisitos que debe cumplir una solución, y una función de costo que debe ser minimizado. Las soluciones obtenidas con este método de optimización se pueden utilizar como puntos de referencia para evaluar la calidad de métodos heurísticos, tales como el algoritmo mencionado en la región de crecimiento.

Para los mapas que consisten en polígonos, las agencias cartográficas nacionales a menudo establecen que el área de cada polígono debe exceder un valor pre-establecido, lo que, al igual que la escala del mapa, puede depender del tipo de objeto que representa. En efecto, este requisito se puede aplicar en un enfoque de optimización. La función de costos es necesaria definir de tal forma que refleje la calidad del mapa generalizado. La medida de calidad del mapa generalizado debería recompensar similitud entre el mapa original y el mapa generalizado y penalizar las diferencias. Esto significa que un cambio en el tipo de objeto de un polígono tiene que ser cargada. El costo de dicho cambio puede ser definido de acuerdo a la zona del polígono. El tipo de cambio también se puede reflejar en la función, por ejemplo, penalizando el cambio de tierras de cultivo en pastizales menos que el cambio de las tierras de cultivo en bosques. La diferencia de costos aquí surge de la similitud semántica entre las tierras de cultivo y pastizales que es mucho mayor que entre las tierras de cultivo y bosque.

Optimización

El problema de la generalización ahora debe ser expresada en una forma legible por una solucion. El problema de la generalización de un mapa de polígonos se puede formalizar como un programa lineal entero, que consta de una función objetivo lineal y un sistema de desigualdades lineales en variables enteras. De esta forma el problema se puede resolver, por ejemplo, aplicando el solucionador comercial CPLEX. Un ejemplo de una solución de generalización utilizando este enfoque de optimización se muestra en la Figura 3. En este mapa el área de cada polígono generalizada es mayor que el límite aplicado y por lo tanto el tipo de objeto de sólo unos pocos polígonos pequeños necesitan modificación. Así vemos que, en contraste con el resultado en la Figura 1, el pueblo todavía está allí. Pero, ¿el mapa representa adecuadamente la situación sobre el terreno? La parte superior del polígono del pueblo muestra un anexo largo y estrecho. Obviamente, con la función de costos aplicados, el costo de convertir el bosque más pequeño (verde) en polígonos de pueblo fue inferior a convertir el polígono pueblo más grande en bosques o tierras de cultivo.

c0261
Figura 3 y 4

No es necesario estudiar los detalles del algoritmo de optimización utilizado por el editor de resolución a fin de comprender cómo se produce como un resultado negativo. CPLEX utiliza un algoritmo exacto, es decir, que garantiza una solución óptima a nivel mundial y por lo tanto puede ser tratado como un cuadro negro. Uno simplemente puede repensar el conjunto de criterios de calidad y los requisitos y reiniciar el algoritmo con un modelo revisado. Para evitar que largas piezas, polígonos alargados, y función de costo fuera modificada por penalizar a los polígonos no compactos. El algoritmo de optimización será reiniciado, dando como resultado un mapa que refleja mejor la situación sobre el terreno (Figura 4). El enfoque de lo que permite a los algoritmos la generalización de mapas a de mejorar en forma incremental.

Puntos de referencia

Como todos los exactos algoritmos resuelven programas lineales enteros tienen en el peor de los casos un tiempo exponencial en ejecución, que puede ser demasiado lento para la generalización de mapas grandes y detallados. Sin embargo, estos exactos algoritmos siguen siendo valiosos, ya que se pueden utilizar para generalizar de manera óptima los mapas de muestras y así evaluar el desempeño de algoritmos heurísticos. El algoritmo de optimización puede hacerse más rápidamente mediante la introducción de la heurística que el rendimiento de las soluciones satisfactorias con respecto a las medidas de calidad. La evaluación de la calidad de estas heurísticas se puede hacer utilizando como puntos de referencia los resultados óptimos obtenidos para muestras pequeñas. Para la generalización de mapas muy grandes, una buena estrategia es diseñar heurísticos que segmenten el problema de la generalización. Los casos que resultan con menor problema pueden ser resueltos de forma independiente. La introducción a la heurística permite la generalización de una hoja de mapa en aproximadamente una hora, mientras que los resultados son similares a las del algoritmo exacto.

Líneas y Edificios

Hemos discutido sobre el caso en el que tanto el mapa original y generalizados consisten en polígonos. Otro problema es la generalización de los polígonos en los elementos de línea. Por ejemplo, en un mapa a gran escala de los ríos están representados como polígonos, en ríos más pequeños las escalas deben ser representados por sus líneas centrales. La generalización puede hacerse calculando el esqueleto recto (Figura 5), pero si esto se puede integrar en un enfoque de optimización que es todavía una cuestión abierta.

c0262
Figura 5

¿Puede el enfoque de optimización anterior aplicarse a los edificios también? Básicamente, la simplificación de construcción se puede lograr mediante la reducción del número de puntos mediante el establecimiento de una tolerancia de errores geométricos y los requisitos que garanticen un mapa topológicamente correcto. El resultado, sin embargo, puede mostrar el resultado de la pérdida de las regularidades de la forma típica de los edificios. Para evitar esto, las medidas que se pueden añadir a las soluciones a favor de ángulo recto, manteniendo el borde de direcciones dominantes de los polígonos de entrada (Figura 6). Un problema abierto es la preservación de las simetrías de un polígono de construcción.

Observaciones finales

La mayor ventaja de nuestro enfoque de optimización es que separa las definiciones de las necesidades de mapa y la calidad de las soluciones algorítmicas. Es de suponer que el desarrollo de nuevos algoritmos automáticos de generalización – continuará siempre y cuando el usuario cambie necesidades. Esto hace que el enfoque de optimización sea prometedor, ya que permite que el problema de generalización sea de manera progresiva al modelo.

c0263
Figura 6

Fuente:

Gim International

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Solve : *
16 × 6 =