Автоматическое размещение меток , иногда называемое размещением текста или размещением имени , включает в себя компьютерные методы автоматического размещения меток на карте или схеме. Это связано с типографским дизайном таких меток .
Типичные объекты, изображенные на географической карте, — это линейные объекты (например, дороги), площадные объекты (страны, участки, леса, озера и т. д.) и точечные объекты (деревни, города и т. д.). Помимо изображения объектов карты географически точным образом, крайне важно разместить названия, которые идентифицируют эти объекты, таким образом, чтобы читатель сразу понимал, какое название описывает какой объект.
Автоматическое размещение текста является одной из самых сложных, комплексных и трудоемких задач в картографии и ГИС (географической информационной системе) . Другие виды компьютерной графики, такие как диаграммы , графики и т. д., также требуют хорошего размещения надписей, не говоря уже об инженерных чертежах и профессиональных программах, которые создают эти чертежи и диаграммы, таких как электронные таблицы (например, Microsoft Excel ) или вычислительные программы (например, Mathematica ).
Наивно размещенные метки чрезмерно перекрываются, что приводит к карте, которую трудно или даже невозможно читать. Поэтому ГИС должна допускать несколько возможных размещений каждой метки, а часто также возможность изменения размера, поворота или даже удаления (подавления) метки. Затем она выбирает набор размещений, который приводит к наименьшему перекрытию и имеет другие желаемые свойства. Для всех, кроме самых тривиальных настроек, задача является NP-трудной .
Алгоритмы на основе правил пытаются имитировать опытного человека-картографа. На протяжении столетий картографы развивали искусство картографирования и размещения меток. Например, опытный картограф повторяет названия дорог несколько раз для длинных дорог, вместо того, чтобы размещать их один раз, или в случае с городом Оушен-Сити, изображенным точкой, очень близкой к берегу, картограф размещал метку «Оушен-Сити» над землей, чтобы подчеркнуть, что это прибрежный город. [1]
Картографы работают на основе принятых соглашений и правил, таких как те, которые были перечислены швейцарским картографом Эдуардом Имхофом в 1962 году. [2] Например, Нью-Йорк, Вена, Берлин, Париж или Токио должны отображаться на картах стран, поскольку они являются высокоприоритетными метками. После их размещения картограф размещает следующий по важности класс меток, например, основные дороги, реки и другие крупные города. На каждом этапе они следят за тем, чтобы (1) текст размещался таким образом, чтобы читатель легко ассоциировал его с объектом, и (2) метка не перекрывала те, которые уже размещены на карте.
Однако если конкретную проблему размещения меток можно сформулировать как математическую задачу оптимизации, то использование математики для решения этой проблемы обычно лучше, чем использование алгоритма, основанного на правилах. [3]
Самый простой жадный алгоритм размещает последовательные метки на карте в позициях, которые приводят к минимальному перекрытию меток. Его результаты не идеальны даже для очень простых задач, но он чрезвычайно быстр.
Чуть более сложные алгоритмы полагаются на локальную оптимизацию для достижения локального оптимума функции оценки размещения — в каждой итерации размещение одной метки перемещается в другую позицию, и если это улучшает результат, перемещение сохраняется. Он работает достаточно хорошо для карт, которые не слишком плотно помечены. Чуть более сложные вариации пытаются перемещать 2 или более меток одновременно. Алгоритм завершается после достижения некоторого локального оптимума.
Простой алгоритм — имитация отжига — дает хорошие результаты с относительно хорошей производительностью. Он работает как локальная оптимизация, но может сохранить изменение, даже если это ухудшит результат. Вероятность сохранения такого изменения равна , где — изменение функции оценки, а — температура . Температура постепенно понижается в соответствии с графиком отжига . Когда температура высока, имитация отжига вносит почти случайные изменения в размещение меток, имея возможность избежать локального оптимума . Позже, когда, как можно надеяться, будет найден очень хороший локальный оптимум, он ведет себя аналогично локальной оптимизации. Основными проблемами при разработке решения имитации отжига являются выбор хорошей функции оценки и хорошего графика отжига. Обычно слишком быстрое охлаждение ухудшает решение, а слишком медленное охлаждение ухудшает производительность, но график обычно представляет собой довольно сложный алгоритм, содержащий более одного параметра.
Другой класс алгоритмов прямого поиска — это различные эволюционные алгоритмы , например генетические алгоритмы .
Одна простая оптимизация, которая важна на реальных картах, — это разделение набора меток на меньшие наборы, которые могут быть решены независимо. Две метки являются конкурентами, если они могут перекрываться в одном из возможных размещений. Транзитивное замыкание этого отношения делит набор меток на возможно гораздо меньшие наборы. На равномерно и плотно размеченных картах, как правило, один набор будет содержать большинство меток, а на картах, для которых разметка неравномерна, это может дать очень большой выигрыш в производительности. Например, при разметке карты мира Америка размечается независимо от Евразии и т. д.
Если проблему маркировки карты можно свести к ситуации, в которой каждая оставшаяся метка имеет только две потенциальные позиции, в которые ее можно поместить, то ее можно эффективно решить, используя случай 2-выполнимости , чтобы найти размещение, избегая любых конфликтующих пар размещений; на этом принципе основано несколько точных и приблизительных алгоритмов размещения меток для более сложных типов задач. [4]
Алгоритмы автоматического размещения меток могут использовать любой из алгоритмов для поиска максимального непересекающегося множества из множества потенциальных меток. Также могут использоваться другие алгоритмы, такие как различные графовые решения, целочисленное программирование и т. д.
Некоторые версии проблемы размещения меток на карте можно сформулировать как проблемы целочисленного программирования с множественным выбором (MCIP), где целевая функция заключается в минимизации суммы числовых штрафов за перемещение отдельных меток от их оптимального размещения для избежания наложений. Ограничения проблемы заключаются в том, что каждая метка должна быть размещена в одном из конечного числа разрешенных положений на карте. (Или удалена с карты, чтобы можно было разместить другие метки.)
Близкое к оптимальному решение этой MCIP обычно можно найти за разумное количество машинного времени, используя релаксацию Лагранжа для решения двойственной формулировки задачи оптимизации. [5]
Первое коммерческое решение проблемы маркировки карт, сформулированное как задача MCIP и решенное методом релаксации Лагранжа, состояло в размещении меток скважин и точек сейсмического взрыва на базовых картах нефтяной промышленности. [6]
С тех пор, как было опубликовано первое решение, было предложено и использовано множество других алгоритмов математической оптимизации для решения этой задачи MCIP для других картографических приложений.
