回路化（Metro）マップのアルゴリズム

Question

これはロングショットですが、汚い仕事を始める前に試してみるかもしれないと思いました。

定義された入力ステーション（頂点）と行（エッジ）、つまり公共交通機関の実際のマップで、特定のマップをメトロマップに模倣するアプリケーションを構築するプロジェクトがあります。私はこの問題についていくつかの研究をしましたが、これは3-SAT問題に相当するNP完全な問題です。また、そのようなマップを生成する方法についても理論的なアイデアがいくつかありますが、それらは十分に詳細ではありません。

私が探しているのは、この問題の他の既存のソリューション、ある種の擬似コード、（ほぼ）他のプログラミング言語などの実際のコードなど、アルゴリズム自体の作業に費やす必要がある時間を短縮するものです。 、その見返りに、アプリケーションの他の側面に取り組む時間が増えます。

誰かが私を助けることができるものを見たことがあるなら、私はそれをとても感謝しています。

Answer 1

「Metro Map Layoutの問題」と「Metro Map Lineの交差点」についてグーグルで検索すると、過去10年間で非常に積極的に調査されているため、多くの参照が見つかります。

問題はまったく些細なことではないようであり、「芸術的」な機能を数学的制約に翻訳することは、最も難しいタスクの1つであるように見えます。

とにかく、ここに私が（他の多くの人の中でも）、私が興味深いと感じた3つの出版物があります：

マルチ基準の最適化を使用したメトロマップレイアウト

メトロマップのライン交差最小化

メトロマップレイアウトの問題

hth！

Answer 2

あなたのトピックに似た研究： http://graphics.stanford.edu/papers/routemaps/

Answer 3

これは、手節約に関するいくつかの提案です - ピンチの塩を飲みなさい。

「Metro」マップの私の概念は、8つの基本的な方向とステーションの1つにラインが定期的に間隔を空けている傾向があるものです。

実際の座標のセットを「メトロ」座標に変換しようとしていると思います。

私はあなたのメインルート（たとえば、都市ループ）から始めて、重要な順に他のルートを徐々に追加します。

各ルートについて、8つの基本方向を移動する直線の最も少ない数を使用する最も近い近似を見つけたいと思う。これは、実際の座標の境界ボックスから始めて、それをグリッドに分割し、グリッドスクエアからグリッドスクエアへの「メトロ」ルートを見つけてから、そのルートを連続的に改良して、マップを歪めずに曲がり数を減らすために連続して改良します。可能であれば、他のルートとの交差点を導入することなく多すぎます。

それを行ったので、各ラインを拡張して、連続したステーションが「メトロ」ビューで同じ距離になるようにします。

私の推測では、結果の手動の調整をサポートしたいと思います。

幸運を！

Answer 4

計画の問題のように感じます。あなたの難しい制約は次のとおりです。

• すべてのステーションはポイントにある必要があります。ポイントは、ポイント間にxの距離があるグリッド上にあります（2cmでこの静的になります）

• 同じ場所に2つのステーションがあるべきではありません

• ステーションラベルを描くのに十分なスペースがあるはずです。ラベルには、ステーションが割り当てられるポイントから異なる方向を割り当てることができることに注意してください。

• 地下鉄の線を描くのに十分なスペースがあるはずです。

あなたのソフト制約は次のように見えます：

• 各ステーションについて、ステーションに割り当てられたポイントまでの実際の地理的位置距離を最小限に抑えます。

その後、Drools Plannerのようなものを投げて、 これが看護師の名簿のためのハードでソフトな制約の例です.