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