Colocación automática de etiquetas

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 diagramas , 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 diagramas, 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 que es 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 .

Algoritmos basados ​​en reglas

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]

Algoritmos de optimización local

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. exp ⁡ − Δ mi yo {\displaystyle \exp {\frac {-\Delta E}{T}}} Δ mi {\displaystyle \Delta E} yo {\estilo de visualización T}

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 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.

Algoritmos de 2-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 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]

Otros algoritmos

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.

Programación entera

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.

Notas

  1. ^ Slocum, Terry (2010). Cartografía temática y geovisualización . Upper Saddle River, NJ: Pearson. pág. 576. ISBN 978-0-13-801006-5.
  2. ^ 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: "Posicionamiento de nombres en mapas", The American Cartographer , V. 2 # 2 (1975), págs.128-144
  3. ^ Zoraster, Steven, "Sistemas expertos y el problema de la ubicación de las etiquetas en los mapas", Cartographia, https://utpjournals.press/doi/10.3138/P75V-T152-7U53-4170
  4. ^ Doddi, Srinivas; Marathe, Madhav V.; Mirzaian, Andy; Moret, Bernard ME; Zhu, Binhai (1997), "Etiquetado de mapas y sus generalizaciones", Proc. 8.º Simposio ACM-SIAM sobre algoritmos discretos (SODA), págs. 148-157, ISBN 9780898713909; Formann, M.; Wagner, F. (1991), "Un problema de empaquetamiento con aplicaciones a la rotulación de mapas", Proc. 7th ACM Symp. Computational Geometry , 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.
  5. ^ James Bean, "Un algoritmo lagrangiano para programación de enteros de opción múltiple", https://www.jstor.org/stable/170661
  6. ^ Zoraster, Steven; Bayer, Stephen. "Experiencia práctica con un programa de colocación de etiquetas en mapas" (PDF) . CaGIS . Cartografía y Sociedad de Información Geográfica .

Referencias

  • Freeman, H., Procesamiento de datos de mapas y el problema de la anotación, Proc. 3.ª Conferencia 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., “Colocación de nombres de computadora”, cap. 29, en Sistemas de información geográfica, 1, DJ Maguire, MF Goodchild y DW Rhind, John Wiley, Nueva York, 1991, 449–460.
  • Podolskaya NN Algoritmos automáticos de eliminación de conflictos de etiquetas para aplicaciones gráficas interactivas. Tecnologías de la información (ISSN 1684-6400), 9, 2007, págs. 45-50. En ruso: Подольская Н.Н. Algoritmos automáticos con muchas fórmulas para la interacción con gráficos gráficos. Информационные технологии, 9, 2007, с. 45–50.
  • Kameda, T. y K. Imai. 2003. Ubicación de etiquetas de mapas para puntos y curvas. IEICE Transactions of Fundamentals of Electronics Communications and Computer Sciences. E86A(4):835–840.
  • Ribeiro Glaydston y Luiz Lorena. 2006. Heurística para problemas de colocación de etiquetas cartográficas. Computers & Geosciences. 32:739–748.
  • Wagner, F., A. Wolff, V. Kapoor y T. Strijk. 2001. Tres reglas son suficientes para una buena colocación de etiquetas. Algorithmica. 30:334–349.
  • Sitio de etiquetado de mapas de Alexander Wolff Archivado el 30 de enero de 2017 en Wayback Machine
  • La bibliografía sobre etiquetado de mapas Archivado el 24 de abril de 2017 en Wayback Machine
  • Colocación de etiquetas
  • Un estudio empírico de algoritmos para la colocación de etiquetas de características puntuales
Obtenido de "https://es.wikipedia.org/w/index.php?title=Colocación_automática_de_etiquetas&oldid=1192827844"