La colocación automática de etiquetas , a veces denominada colocación de texto o colocación de nombres , comprende los métodos informáticos para colocar etiquetas automáticamente en un mapa o gráfico. Esto está relacionado con el diseño tipográfico de dichas etiquetas .
Las características típicas representadas en un mapa geográfico son características de línea (por ejemplo, carreteras), características de área (países, parcelas, bosques, lagos, etc.) y características de puntos (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 instantáneamente qué nombre describe qué característica.
La colocación automática de texto es uno de los problemas más difíciles, complejos y que requieren más tiempo en la elaboración de mapas y SIG (Sistema de Información Geográfica) . Otros tipos de gráficos generados por computadora, como cuadros , gráficos , etc., también requieren una buena colocación de etiquetas, sin mencionar los dibujos de ingeniería y los programas profesionales que producen estos dibujos y gráficos, como hojas de cálculo (por ejemplo, Microsoft Excel ) o programas de software computacional. (por ejemplo, Mathematica ).
Las etiquetas colocadas ingenuamente se superponen excesivamente, lo que da como resultado un mapa que es difícil o incluso imposible de leer. Por lo tanto, un SIG debe permitir algunas 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 da como resultado la menor superposición y tiene otras propiedades deseables. Para todas las configuraciones, excepto las más triviales, el problema es NP-hard .
Algoritmos basados en reglas
Los algoritmos basados en reglas intentan emular a un cartógrafo humano experimentado. Durante 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 carreteras largas, en lugar de colocarlas una sola vez, o en el caso de Ocean City representado por un punto muy cerca de la costa, el cartógrafo colocaría la etiqueta "Ocean City" sobre el Terreno para destacar que es un pueblo costero. [1]
Los cartógrafos trabajan según las convenciones y reglas aceptadas, como las detalladas por 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 altos. etiquetas de 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 grandes ciudades. En cada paso, se aseguran de que (1) el texto se coloque 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.
Algoritmos de optimización local
El algoritmo codicioso más simple coloca etiquetas consecutivas en el mapa en posiciones que dan como resultado 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 etiquetados con demasiada densidad. Las variaciones un poco más complejas intentan mover 2 o más etiquetas al mismo tiempo. El algoritmo finaliza después de alcanzar algún óptimo local.
Un algoritmo simple, el recocido simulado , produce buenos resultados con un rendimiento relativamente bueno. Funciona como una optimización local, pero puede mantener un cambio incluso si empeora el resultado. La posibilidad de mantener tal cambio es, dónde 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 ubicación de la etiqueta, pudiendo escapar a un óptimo local . Más tarde, cuando se espera que se haya encontrado un óptimo local muy bueno, se comportará 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. En general, 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 .
Algoritmos de divide y vencerás
Una optimización simple que es importante en 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 etiquetados de manera uniforme y densa, por lo general, el conjunto único contendrá la mayoría de las etiquetas, y en los mapas para 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.
2-algoritmos de satisfacibilidad
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 pares conflictivos. de colocaciones; Varios algoritmos de colocación de etiquetas exactos y aproximados para tipos de problemas más complejos se basan en este principio. [3]
Otros algoritmos
Los algoritmos de colocación automática de etiquetas pueden utilizar cualquiera de los algoritmos para encontrar el conjunto disjunto máximo del conjunto de etiquetas potenciales. También se pueden utilizar otros algoritmos, como varias soluciones gráficas, programación de enteros , etc.
Notas
- ^ Slocum, Terry (2010). Cartografía temática y geovisualización . Upper Saddle River, Nueva Jersey: Pearson. pag. 576. ISBN 978-0-13-801006-5.
- ^ Imhof, Eduard, "Die Anordnung der Namen in der Karte", Annuaire International de Cartographie II, Orell-Füssli Verlag, Zürich, 93-129, 1962. Traducción al inglés: "Colocación de nombres en mapas", The American Cartographer , V. 2 # 2 (1975), págs. 128-144
- ^ Doddi, Srinivas; Marathe, Madhav V .; Mirzaian, Andy; Moret, Bernard ME; Zhu, Binhai (1997), "Etiquetado de mapas y sus generalizaciones", Proc. 8vo ACM-SIAM Symp. Algoritmos discretos (SODA) , págs. 148-157; Formann, M .; Wagner, F. (1991), "Un problema de empaquetado con aplicaciones a la rotulación de mapas", Proc. Séptimo ACM Symp. Geometría computacional , págs. 281–288; Poon, Chung Keung; Zhu, Binhai; Chin, Francis (1998), "Una solución de tiempo polinomial para etiquetar un mapa rectilíneo", Information Processing Letters , 65 (4): 201-207, doi : 10.1016 / S0020-0190 (98) 00002-7; Wagner, Frank; Wolff, Alexander (1997), "Un algoritmo práctico de etiquetado de mapas", Geometría computacional: teoría y aplicaciones , 7 (5–6): 387–404, doi : 10.1016 / S0925-7721 (96) 00007-7.
Referencias
- Freeman, H., Procesamiento de datos de mapas y el problema de la anotación, Proc. 3a Conf. Escandinava sobre análisis de imágenes, Chartwell-Bratt Ltd. Copenhague, 1983.
- Ahn, J. y Freeman, H., "Un programa para la colocación automática de nombres", Proc. AUTO-CARTO 6, Ottawa, 1983. 444–455.
- Freeman, H., “Ubicación del nombre de la computadora”, cap. 29, en Geographical Information Systems, 1, DJ Maguire, MF Goodchild y DW Rhind, John Wiley, Nueva York, 1991, 449–460.
- Algoritmos automáticos de eliminación de conflictos de etiquetas de Podolskaya NN para aplicaciones de gráficos interactivos. Tecnologías de la información (ISSN 1684-6400), 9, 2007, pág. 45–50. En ruso: Подольская Н.Н. Алгоритмы автоматического отброса формуляров для интерак тивных графических приложений. Информационные технологии, 9, 2007, с. 45–50.
- Kameda, T. y K. Imai. 2003. Ubicación de etiquetas de mapa para puntos y curvas. Transacciones IEICE de Fundamentos de Comunicaciones Electrónicas y Ciencias de la Computación E86A (4): 835–840.
- Ribeiro Glaydston y Luiz Lorena. 2006. Heurística para problemas de colocación de etiquetas cartográficas. Informática y Geociencias. 32: 739–748.
- Wagner, F., A. Wolff, V. Kapoor y T. Strijk. 2001. Tres reglas son suficientes para una buena colocación de etiquetas. Algoritmica. 30: 334–349.