Алгоритм схематизации карт (метро)

Question

Это маловероятно, но я подумал, что стоит попробовать, прежде чем начинать грязную работу.

У меня есть проект по созданию приложения, которое будет для определенных входных станций (вершин) и линий (ребер), то есть реальной карты некоторого общественного транспорта, схематизировать данную карту в карту метро.Я провел некоторое исследование этой проблемы, и это NP-полная проблема, эквивалентная задаче 3-SAT.У меня также есть некоторые теоретические идеи о том, как создать такую ​​карту, но они недостаточно подробны.

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

Если кто-нибудь когда-нибудь видел что-нибудь, что может мне помочь, я был бы очень признателен.

Answer 1

Если вы погуглите «проблема с компоновкой карты метро» и «пересечение линий карты метро», вы найдете много ссылок, поскольку в последние 10 лет эта проблема очень активно исследовалась.

Проблема кажется совсем не тривиальной, и перевод «художественных» особенностей в математические ограничения, по-видимому, является одной из самых сложных задач.

В любом случае, вот три публикации, которые мне показались интересными для начала (среди многих, многих других):

Компоновка карты метро с использованием многокритериальной оптимизации

Минимизация пересечения линий на картах метрополитена

Проблема с компоновкой карты метро

ХТХ!

Answer 2

Исследования, аналогичные вашей теме: http://graphics.stanford.edu/papers/routemaps/

Answer 3

Это всего лишь какое-то предложение, махающее рукой – отнеситесь к этому с недоверием.

Мое представление о карте «метро» — это карта, на которой линии направлены к одному из восьми основных направлений, а станции расположены через равные интервалы.

Я предполагаю, что вы пытаетесь преобразовать набор реальных координат в координаты «метро».

Я бы начал с основного маршрута (например, городской петли), а затем постепенно добавлял другие маршруты в порядке важности.

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

Сделав это, масштабируйте каждую линию так, чтобы последовательные станции находились на одинаковом расстоянии друг от друга в представлении «метро».

Я предполагаю, что вы все равно захотите поддерживать ручную настройку результата.

Удачи!

Answer 4

Похоже на проблему с планированием.Похоже, ваши жесткие ограничения:

• Каждая станция должна быть на точке.Точки расположены на сетке с расстоянием X между точками (я бы сделал это статическим на расстоянии 2 см).

• На одном месте не должно быть 2 станций.

• Должно быть достаточно места для нанесения обозначения станции.Обратите внимание, что метке могут быть присвоены разные направления от точки, которой присвоена станция.

• Должно быть достаточно места для рисования линий метро.

Похоже, ваши мягкие ограничения:

• Для каждой станции минимизируйте фактическое географическое расстояние до точки, назначенной станции.

Затем добавьте туда что-нибудь вроде Drools Planner, вот пример жестких и мягких ограничений для набора медсестер.