La colocación automática de etiquetas , a veces denominada colocación de texto o colocación de nombre , comprende los métodos informáticos de colocación automática de etiquetas en un mapa o gráfico. Esto está relacionado con el diseño tipográfico de dichas etiquetas .
Las características típicas que se representan en un mapa geográfico son las características lineales (por ejemplo, carreteras), las características de área (países, parcelas, bosques, lagos, etc.) y las características puntuales (pueblos, ciudades, etc.). Además de representar las características del mapa de una manera geográficamente precisa, es de vital importancia colocar los nombres que identifican estas características, de manera que el lector sepa al instante qué nombre describe cada característica.
La colocación automática de texto es uno de los problemas más difíciles, complejos y que más tiempo requieren en la elaboración de mapas y en los SIG (sistemas de información geográfica) . Otros tipos de gráficos generados por ordenador (como cuadros , gráficos , etc.) también requieren una buena colocación de las etiquetas, por no hablar de los dibujos de ingeniería y los programas profesionales que producen estos dibujos y cuadros, como las hojas de cálculo (por ejemplo, Microsoft Excel ) o los programas informáticos (por ejemplo, Mathematica ).
Las etiquetas colocadas de forma ingenua se superponen excesivamente, lo que da como resultado un mapa difícil o incluso imposible de leer. Por lo tanto, un SIG debe permitir unas pocas ubicaciones posibles de cada etiqueta y, a menudo, también una opción para cambiar el tamaño, rotar o incluso eliminar (suprimir) la etiqueta. Luego, selecciona un conjunto de ubicaciones que genere la menor superposición y tenga otras propiedades deseables. Para todas las configuraciones, excepto las más triviales, el problema es NP-hard .
Los algoritmos basados en reglas intentan emular a un cartógrafo humano experimentado. A lo largo de los siglos, los cartógrafos han desarrollado el arte de la elaboración de mapas y la colocación de etiquetas. Por ejemplo, un cartógrafo experimentado repite los nombres de las carreteras varias veces para las carreteras largas, en lugar de colocarlos una sola vez, o en el caso de Ocean City representada por un punto muy cerca de la costa, el cartógrafo colocaría la etiqueta "Ocean City" sobre el terreno para enfatizar que es una ciudad costera. [1]
Los cartógrafos trabajan según convenciones y reglas aceptadas, como las que detalló el cartógrafo suizo Eduard Imhof en 1962. [2] Por ejemplo, la ciudad de Nueva York, Viena, Berlín, París o Tokio deben aparecer en los mapas de los países porque son etiquetas de alta prioridad. Una vez que se colocan, el cartógrafo coloca la siguiente clase de etiquetas más importante, por ejemplo, carreteras principales, ríos y otras ciudades grandes. En cada paso se aseguran de que (1) el texto esté colocado de manera que el lector lo asocie fácilmente con la característica, y (2) la etiqueta no se superponga con las que ya están colocadas en el mapa.
Sin embargo, si un problema particular de colocación de etiquetas puede formularse como un problema de optimización matemática, usar las matemáticas para resolver el problema suele ser mejor que usar un algoritmo basado en reglas. [3]
El algoritmo voraz más simple coloca etiquetas consecutivas en el mapa en posiciones que resultan en una superposición mínima de etiquetas. Sus resultados no son perfectos ni siquiera para problemas muy simples, pero es extremadamente rápido.
Los algoritmos un poco más complejos se basan en la optimización local para alcanzar un óptimo local de una función de evaluación de ubicación: en cada iteración, la ubicación de una sola etiqueta se mueve a otra posición y, si mejora el resultado, se conserva el movimiento. Funciona razonablemente bien para mapas que no están demasiado densamente etiquetados. Las variaciones un poco más complejas intentan mover 2 o más etiquetas al mismo tiempo. El algoritmo finaliza después de alcanzar un óptimo local.
Un algoritmo simple ( recocido simulado ) produce buenos resultados con un rendimiento relativamente bueno. Funciona como la optimización local, pero puede mantener un cambio incluso si empeora el resultado. La probabilidad de mantener dicho cambio es , donde es el cambio en la función de evaluación y es la temperatura . La temperatura se reduce gradualmente de acuerdo con el programa de recocido . Cuando la temperatura es alta, el recocido simulado realiza cambios casi aleatorios en la colocación de la etiqueta, pudiendo escapar de un óptimo local . Más tarde, cuando se espera que se haya encontrado un óptimo local muy bueno, se comporta de manera similar a la optimización local. Los principales desafíos en el desarrollo de una solución de recocido simulado son elegir una buena función de evaluación y un buen programa de recocido. Generalmente, un enfriamiento demasiado rápido degradará la solución y un enfriamiento demasiado lento degradará el rendimiento, pero el programa suele ser un algoritmo bastante complejo, con más de un parámetro.
Otra clase de algoritmos de búsqueda directa son los diversos algoritmos evolutivos , por ejemplo los algoritmos genéticos .
Una optimización simple que es importante en los mapas reales es dividir un conjunto de etiquetas en conjuntos más pequeños que se pueden resolver de forma independiente. Dos etiquetas son rivales si pueden superponerse en una de las posibles ubicaciones. El cierre transitivo de esta relación divide el conjunto de etiquetas en conjuntos posiblemente mucho más pequeños. En mapas con etiquetas uniformes y densas, normalmente el conjunto único contendrá la mayoría de las etiquetas, y en mapas en los que el etiquetado no es uniforme puede traer grandes beneficios de rendimiento. Por ejemplo, al etiquetar un mapa del mundo, América se etiqueta independientemente de Eurasia , etc.
Si un problema de etiquetado de mapas se puede reducir a una situación en la que cada etiqueta restante tiene solo dos posiciones potenciales en las que se puede colocar, entonces se puede resolver de manera eficiente utilizando una instancia de 2-satisfacibilidad para encontrar una ubicación evitando cualquier par de ubicaciones conflictivas; varios algoritmos de ubicación de etiquetas exactos y aproximados para tipos de problemas más complejos se basan en este principio. [4]
Los algoritmos de colocación automática de etiquetas pueden utilizar cualquiera de los algoritmos para encontrar el conjunto máximo disjunto del conjunto de etiquetas potenciales. También se pueden utilizar otros algoritmos, como diversas soluciones de gráficos, programación entera , etc.
Algunas versiones del problema de colocación de etiquetas en el mapa se pueden formular como problemas de programación entera de opciones múltiples (MCIP) donde la función objetivo es minimizar la suma de penalizaciones numéricas por mover etiquetas individuales fuera de su ubicación óptima para evitar superposiciones. Las restricciones del problema son que cada etiqueta se coloque en una de un número finito de posiciones permitidas en el mapa. (O se elimine del mapa para permitir que se coloquen otras etiquetas).
Generalmente, se puede encontrar una solución cercana a la óptima para este MCIP en una cantidad práctica de tiempo de computadora utilizando la relajación lagrangiana para resolver la formulación dual del problema de optimización. [5]
La primera solución comercial al problema de las etiquetas de mapas, formulada como un problema MCIP y resuelta mediante relajación lagrangiana, fue colocar etiquetas de pozos y puntos de disparo sísmico en mapas base de la industria petrolera. [6]
Desde que se publicó esa primera solución, se han propuesto y utilizado muchos otros algoritmos de optimización matemática para resolver este MCIP para otras aplicaciones cartográficas.
