ロングショットですが、汚い仕事を始める前にやってみようかなと思いました。
定義された入力ステーション（頂点）と線（エッジ）、つまり、いくつかの公共交通機関の実際の地図に対して、特定の地図をメトロ地図に図式化するアプリケーションを構築するプロジェクトがあります。私はこの問題についていくつかの調査を行いましたが、これは3-SAT問題と同等のNP完全問題です。そのようなマップを生成する方法についてもいくつかの理論的なアイデアがありますが、それらは十分に詳細ではありません。
私が探しているのは、この問題の他の既存の解決策、ある種の擬似コード、（ほぼ）他のプログラミング言語の実際のコードなど、アルゴリズム自体の作業に費やす時間を短縮するものです。 、その見返りに、アプリケーションの他の側面に取り組むためのより多くの時間を与えてくれます。
誰かが私を助けることができる何かを見たことがあれば、私はそれをとても感謝します。
過去 10 年間で非常に活発に研究されているため、「メトロ マップ レイアウトの問題」と「メトロ マップ ライン クロッシング」をググると、多くの参考文献が見つかります。
この問題は決して些細なことではないように思われ、「芸術的な」機能を数学的制約に変換することは、一見最も困難な作業の 1 つです。
とにかく、ここに私が最初に興味深いと思った3つの出版物があります（他の多くの出版物の中から）：
チッ！
あなたのトピックに似た研究: http://graphics.stanford.edu/papers/routemaps/
計画上の問題のように感じます。ハード制約のように見えます:
すべてのステーションはポイント上にある必要があります。ポイントは、ポイント間の距離が X のグリッド上にあります (これを 2cm で静的にします)
同じ場所に 2 つの駅があってはならない
ステーション ラベルを描画するための十分なスペースが必要です。ラベルには、ステーションが割り当てられたポイントから異なる方向を割り当てることができることに注意してください。
地下鉄の路線を引くのに十分なスペースが必要です。
ソフト制約のように見えます:
次に、Drools Planner のようなものを投げます。これは、看護師の勤務表のハード制約とソフト制約の例です。
これは手を振ることに関するいくつかの提案です - 塩のピンチで服用してください.
私の「メトロ」マップの概念は、線が 8 つの基本的な方向のいずれかに向かう傾向があり、駅が等間隔に配置されているマップです。
実際の座標のセットを「メトロ」座標に変換しようとしていると思います。
私はあなたの主要なルート (都市ループなど) から始めて、重要度の順に他のルートを段階的に追加します。
ルートごとに、基本的な 8 つの方向に移動する直線の数が最も少ない最も近い近似を見つけたいとします。これを行うには、実際の座標の境界ボックスから開始し、それをグリッドに分割してから、グリッド スクエアからグリッド スクエアへの「メトロ」ルートを見つけ、そのルートを連続的に調整して、マップを歪めずに曲がりの数を減らします。可能な限り、他のルートとの交差を導入しないでください。
それが終わったら、「地下鉄」ビューで連続する駅が同じ距離になるように各線をスケーリングします。
私の推測では、結果の手動調整を引き続きサポートしたいと思うでしょう。
幸運を！