Хочу представить вашему вниманию одну любопытную задачу и несколько способов ее решения. Изначально задача появилась на stackoverflow, но перед тем как перейти к сути хочу подчеркнуть отсутствие какого бы то ни было желания навязать свою точку зрения.
Итак, задача: есть серия изображений и набор пояснительных меток к каждому изображению, необходимо оптимальным образом расставить метки, избежав пересечения связывающих линий и сохранив общую читабельность.
Очевидно, задача не является тривиальной. Более того, я бы сказал любое прямое решение не сможет гарантировать оптимальность результата. Другими словами, человек (для которого, собственно, мы и стараемся) обязательно заметит некоторые странности размещения поясняющих меток. В некоторых, особо сложных случаях, результат может показаться даже отвратительным.
Постараюсь коротко сформулировать важные, на мой взгляд, критерии:
- общая чистота и читабельность
- отсутствие «увода внимания», поскольку приоритетным является основное изображение, а не метки, которые играют важную, но, тем не менее, второстепенную роль
- легкость размещения пояснений
- стабильное качество результата
Итак, на данном этапе можно выбирать из следующего:
- попытаться найти подходящий алгоритм
- изменить стиль, решая задачу на другом уровне
Первый способ: найдем подходящий алгоритм
Вариантов, на самом деле, вполне достаточно: итеративные методы, нечто похожее на разводку печатных плат, генетический алгоритм и т.д. Касательно разводки печатных плат интерес вызывает следующий документ: Algorithmic studies on PCB routing by Tan Yan
Думаю, у каждого будет своя оценка надежности одного из указанных подходов, ресурсоемкости реализации, тестирования и внесения необходимых изменений для корректной отработки возможных граничных ситуаций.
Второй способ: постараемся поработать со стилем
Другими словами, перейдем на мета-уровень, что может позволить существенно улучшить результат, одновременно упрощая и реализацию. Идеальный вариант — метки и пояснения остаются доступными, но не воспринимаются как основная составляющая иллюстрации, сохраняя максимум информации, предоставляемой основным изображением.
Напрашивается решение, которое позволит обеспечить наименьшую длину сносок и их однообразность. Таким образом, человек, умеющий различать и отфильтровывать нежелательные шаблоны, быстро научится не замечать второстепенные детали. Кроме того, вполне логично выглядит переход от наклонных линий к горизонтальным (помним об антиалиасинге и дополнительной потере деталей). Одно из возможных решений выглядит следующим образом:
В этом случае алгоритм размещения меток становится существенно проще, а результат предсказуемее. Как вы можете заметить, стиль размещения пояснений будет подобен даже для очень разных изображений, что, смею предположить, положительно скажется на впечатлении от просмотра многих десятков «аннотированных» иллюстраций.
Надеюсь, данный материал был инетересен. Сформулирую заключительный вопрос следующим образом:
Стоит ли программисту всегда оставаться программистом?
Каждый решает для себя. Интересные и полезные мысли, как обычно, приветствуются в комментариях.
Изначальный вопрос на stackoverflow
Автор: aarner
