Автоматическое размещение меток - Automatic label placement

Автоматическое размещение метокиногда называют размещение текста или же размещение имени, включает компьютерные методы автоматического размещения надписей на карте или диаграмме. Это связано с типографский дизайн таких этикеток.

Типичные черты, изображенные на географическом карта - это линейные объекты (например, дороги), пространственные объекты (страны, участки, леса, озера и т. д.) и точечные объекты (деревни, города и т. д.). Помимо изображения объектов карты географически точным образом, критически важно разместить имена, идентифицирующие эти объекты, таким образом, чтобы читатель сразу знал, какое имя описывает какой объект.

Автоматическое размещение текста - одна из самых сложных и трудоемких задач при создании карт и ГИС (Географическая информационная система). Другие виды компьютерной графики, например диаграммы, графики и т. д. - также требуется хорошее размещение этикеток, не говоря уже о технических чертежах и профессиональных программах, которые создают эти чертежи и диаграммы, например электронные таблицы (например. Майкрософт Эксель ) или компьютерных программ (например, Mathematica ).

Наивно расположенные надписи чрезмерно перекрываются, в результате чего карту трудно или даже невозможно прочитать. Следовательно, ГИС должна допускать несколько возможных размещений каждой метки, а также часто возможность изменения размера, поворота или даже удаления (подавления) метки. Затем он выбирает набор мест размещения с наименьшим перекрытием и другими желательными свойствами. Для всех настроек, кроме самых тривиальных, проблема заключается в NP-жесткий.

Алгоритмы на основе правил

Алгоритмы, основанные на правилах, пытаются подражать опытному картографу-человеку. На протяжении веков картографы развили искусство создания карт и размещения этикеток. Например, опытный картограф несколько раз повторяет названия дорог для длинных дорог вместо того, чтобы указывать их один раз, или в случае Оушен-Сити, изображенного точкой, расположенной очень близко к берегу, картограф поместит метку «Оушен-Сити» над земли, чтобы подчеркнуть, что это прибрежный город.^[1]

Картографы работают на основе общепринятых конвенций и правил, таких как те, которые были изложены швейцарским картографом Эдуардом Имхофом в 1962 году.^[2] Например, Нью-Йорк, Вена, Берлин, Париж или Токио должны отображаться на картах страны, потому что они имеют высокий приоритет. После того, как они размещены, картограф размещает следующий по важности класс надписей, например, крупные дороги, реки и другие крупные города. На каждом этапе они гарантируют, что (1) текст размещен таким образом, чтобы читатель легко связал его с объектом, и (2) метка не перекрывалась с уже нанесенными на карту.

Алгоритмы локальной оптимизации

Простейший жадный алгоритм размещает последовательные надписи на карте в положениях, которые приводят к минимальному перекрытию надписей. Его результаты не идеальны даже для очень простых задач, но это очень быстро.

Чуть более сложные алгоритмы полагаются на локальную оптимизацию для достижения локального оптимума функции оценки размещения - на каждой итерации размещение одной метки перемещается в другую позицию, и если это улучшает результат, перемещение сохраняется. Он достаточно хорошо работает для карт с не слишком плотной маркировкой. Немного более сложные варианты: попробуйте переместить 2 или более меток одновременно. Алгоритм заканчивается после достижения некоторого локального оптимума.

Простой алгоритм - имитация отжига - дает хорошие результаты при относительно хорошей производительности. Он работает как локальная оптимизация, но может сохранить изменения, даже если это ухудшит результат. Шанс сохранить такое изменение составляет ${ displaystyle exp { frac {- Delta E} {T}}}$ , куда ${ displaystyle Delta E}$ - изменение функции оценки, и ${ displaystyle T}$ это температура. Температура постепенно понижается в соответствии с график отжига. При высокой температуре моделируемый отжиг вносит почти случайные изменения в размещение этикеток, позволяя избежать локальный оптимум. Позже, когда, надо надеяться, был найден очень хороший локальный оптимум, он ведет себя аналогично локальной оптимизации. Основные проблемы при разработке решения для имитации отжига - это выбор хорошей функции оценки и хорошего графика отжига. Как правило, слишком быстрое охлаждение ухудшает качество решения, а слишком медленное охлаждение ухудшает производительность, но расписание обычно представляет собой довольно сложный алгоритм с более чем одним параметром.

Другой класс алгоритмов прямого поиска - это различные эволюционные алгоритмы, например генетические алгоритмы.

Алгоритмы разделяй и властвуй

Одна простая оптимизация, которая важна для реальных карт, - это разделение набора меток на более мелкие наборы, которые можно решить независимо. Две метки соперники если они могут перекрываться в одном из возможных мест размещения. Переходный замыкание этого отношения делит набор меток на, возможно, гораздо меньшие множества. На картах с единообразной и плотной маркировкой обычно один набор будет содержать большинство надписей, а на картах, для которых маркировка неоднородна, это может дать очень большие преимущества в производительности. Например, при нанесении надписей на карту мира Америка помечен независимо от Евразия и Т. Д.

2-выполнимость алгоритмов

Если проблема маркировки карты может быть сведена к ситуации, в которой каждая оставшаяся надпись имеет только две потенциальные позиции, в которые она может быть помещена, то ее можно эффективно решить, используя экземпляр 2-выполнимость найти место размещения, избегая конфликтующих пар мест размещения; На этом принципе основано несколько алгоритмов точного и приблизительного размещения этикеток для более сложных типов задач.^[3]

Другие алгоритмы

Алгоритмы автоматического размещения этикеток могут использовать любой из алгоритмов поиска максимальное непересекающееся множество из набора потенциальных меток. Также могут использоваться другие алгоритмы, например, различные графические решения, целочисленное программирование и Т. Д.

Примечания

^ Слокум, Терри (2010). Тематическая картография и геовизуализация. Река Аппер Сэдл, Нью-Джерси: Пирсон. п. 576. ISBN 978-0-13-801006-5.
^ Имхоф, Эдуард, «Die Anordnung der Namen in der Karte», Annuaire International de Cartographie II, Orell-Füssli Verlag, Zürich, 93–129, 1962. Английский перевод: «Размещение имен на картах», Американский картограф, V.2 # 2 (1975), стр.128-144
^ Додди, Шринивас; Marathe, Madhav V .; Мирзаян, Энди; Морет, Бернард М. Э .; Чжу, Биньхай (1997), «Надпись на карте и ее обобщения», Proc. 8-й симпозиум ACM-SIAM. Дискретные алгоритмы (SODA), стр. 148–157; Formann, M .; Вагнер, Ф. (1991), "Проблема упаковки с приложениями к надписи на картах", Proc. 7-й ACM Symp. Вычислительная геометрия, стр. 281–288; Пун, Чунг Кеунг; Чжу, Биньхай; Чин, Фрэнсис (1998), «Решение с полиномиальным временем для разметки прямолинейной карты», Письма об обработке информации, 65 (4): 201–207, Дои:10.1016 / S0020-0190 (98) 00002-7; Вагнер, Франк; Вольф, Александр (1997), "Практический алгоритм разметки карт", Вычислительная геометрия: теория и приложения, 7 (5–6): 387–404, Дои:10.1016 / S0925-7721 (96) 00007-7.

внешняя ссылка

[1] Слокум, Терри (2010). Тематическая картография и геовизуализация. Река Аппер Сэдл, Нью-Джерси: Пирсон. п. 576. ISBN 978-0-13-801006-5.

[imhof-2] Имхоф, Эдуард, «Die Anordnung der Namen in der Karte», Annuaire International de Cartographie II, Orell-Füssli Verlag, Zürich, 93–129, 1962. Английский перевод: «Размещение имен на картах», Американский картограф, V.2 # 2 (1975), стр.128-144

[3] Додди, Шринивас; Marathe, Madhav V .; Мирзаян, Энди; Морет, Бернард М. Э .; Чжу, Биньхай (1997), «Надпись на карте и ее обобщения», Proc. 8-й симпозиум ACM-SIAM. Дискретные алгоритмы (SODA), стр. 148–157; Formann, M .; Вагнер, Ф. (1991), "Проблема упаковки с приложениями к надписи на картах", Proc. 7-й ACM Symp. Вычислительная геометрия, стр. 281–288; Пун, Чунг Кеунг; Чжу, Биньхай; Чин, Фрэнсис (1998), «Решение с полиномиальным временем для разметки прямолинейной карты», Письма об обработке информации, 65 (4): 201–207, Дои:10.1016 / S0020-0190 (98) 00002-7; Вагнер, Франк; Вольф, Александр (1997), "Практический алгоритм разметки карт", Вычислительная геометрия: теория и приложения, 7 (5–6): 387–404, Дои:10.1016 / S0925-7721 (96) 00007-7.

[1]

[2]

[3]