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

Question

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

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

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

Answer 1

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

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

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

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

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

Проблема макета карты метро

НТН!

Answer 2

Исследования, похожие на вашу тему: http://graphics.stanford.edu/papers/routemaps/

Answer 3

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

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

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

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

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

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

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

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

Answer 4

Это всего лишь несколько советов о махании рукой - возьмите щепотку соли.

Мое представление о карте "метро" - это то, где линии имеют тенденцию к одному из восьми основных направлений, и станции регулярно располагаются.

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

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

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

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

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

Удачи!