地鐵族

 找回密碼
 注冊地鐵族
搜索

社區廣播臺

查看: 5521|回復: 47
打印 上一主題 下一主題

[其他] 如何科學的讓計算機自動繪制一份地鐵線路圖 [復制鏈接]

Rank: 4

UID
197150
帖子
535
精華
0
積分
696
威望
19
人氣
80
注冊時間
2011-9-18
跳轉到指定樓層
樓主
發表于 2020-2-26 14:03:11 |只看該作者 |倒序瀏覽
本帖最后由 yinluke 于 2020-2-29 13:07 編輯

如何科學的讓計算機自動繪制一份地鐵線路圖?
其實仔細想一下,如果僅僅只是知道每條線路各個站點的信息,那么就可以繪制一份忽略地理信息的路線圖,比如知道線路一的站點為【A、B、C】,線路二為【D、B、E】。那么這兩條線組成的系統必然是一個十字型的的結構,這其實就是計算機科學中的圖論(Graph)。
所以在研究圖論之余,樓主想試試用一些常用的作“圖”軟件來讓計算機自動繪制路線圖吧(此“作圖”之“圖”為圖論之“圖”,而非一般圖像)

數據準備

為了讓計算機可以看懂線路和站名之間的關系,我們要把數據做成計算機可以理解的格式。

首先,每個圖都有兩個基本部分構成,節點(Node)和邊(Edge),如果用剛才的例子:節點即為{A, B, C, D, E},可理解為所有車站的列表;邊為{AB, BC, DB, BE},是車站之間的連接關系,是線路的列表,或者說是“區間”的列表。為了適應地鐵的情況,我們為每條邊都加入一項額外信息:線路,這樣好后期圖色方便:{AB1, BC1, DB2, BE2},這里我們用數字1,2來區分兩條不同的線路。

車站列表的信息可以在任意百科輕松取得,稍微用一點點編程即可獲得一份簡單的數據列表(想親自動手詳見附件code.py,如有亂碼請使用python3,并確保所有文本使用UTF-8編碼

而且湊巧的是,因為換乘站的站名會出現在多條線路中,所以他們也自動地被連接在一起了。

那么輸出為特定格式,一份計算機能看懂的線路列表就完成了!

Pyplot

首先嘗試的是python的pyplot,一個簡單的python使用的畫圖模塊。因為畢竟不是很偏技術向的帖子,這里不過多描述細節。
以下是結果:



因為只是把所有的節點隨機排布,然后把相關的連起來,所以這種算法得到的結果不盡人意。處理比較簡單圖還算可以,但是想地鐵圖這種復雜的圖,基本跟一團亂麻沒什么區別。而且這種算法也沒有辦法區分不同的線路。

Cytoscape
https://cytoscape.org/

可見作圖的難點在于每個節點的位置。雖然計算機可以把拓撲結構弄的一清二楚,但他完全不知道每個節點應該放在什么位置才能讓整張圖看起來規整、直觀。所以布局(Layout)(或者叫節點的排布)就顯得十分重要。

Cytoscape是一款專門作“圖”的軟件,它可以把“節點”和“邊”的數據畫成非常直觀又美觀的圖,最重要的是他提供了大量的節點算法。

其中圓形(circle)算法是一種大家很愛用的算法:



不過用在地鐵上似乎有些不合適。他雖然把所有的站點整齊地排在一個圓里面,但對于人類來說基本上就沒有可讀性。

層級(Hierarchic)算法可以發掘數據中的層級關系,作出類似流程圖的效果,實際結果像這樣:



這種排布稍微比剛才的例子稍微好了一些,如果結構再簡單一些,似乎頗適合作為狹長空間的路線圖使用。如果去掉6號線和10號線,減掉一些復雜性,可用性顯著增強:



還有一種緊致(Compound)算法,可以讓線路盡可能減少重疊的情況下壓縮空間,這樣可以在較小的空間放入大量的線路:



不過這種算法太過強調緊致而犧牲了簡潔性,這也是一種看著比較亂的算法。

最復雜的一種算法,也是效果最好的,就是仿生(Organic)算法。可以理解成他把每個節點當成一個小小的有機體,自發地(去中心化地)尋找臨近的節點:



這也就誕生了最接近真實路線圖的一種算法,別忘了這是由計算機僅憑站名就能自動生成的圖像。

Gephi
https://gephi.org/

想象一下把一團毛線放在水中,讓他自己伸展成最自然的形態。


(視頻文件見附件)

Gephi不僅能繪制靜態的圖,還可以繪制動態的,或者說是可以展示出排布的過程,他里面有一種力學(Force Atlas)算法,可以模擬每個節點、每條邊之間的力學關系:斥力、吸引力,就像把線團放入水中,使其自由伸展。

另附一張年底的標準版線路圖以做對比:


*所有資源(軟件、算法)來自網絡,僅提供各種算法之效果預覽。所有圖像均有計算機自動生成,未做修改。有些算法的隨機性導致需要生成多次圖像并從中選取效果最好的一張。源代碼不保留權限。轉載請標明出處。


附件: 你需要登錄才可以下載或查看附件。沒有帳號?注冊地鐵族
已有 9 人評分威望 金錢 人氣 收起 理由
吾知點 + 1 + 8 + 1 地鐵族有你更精彩:)
danielkwong + 1
rainy11 + 1 厲害
iCros + 1 精品文章
jerry207 + 1 精品文章

總評分: 威望 + 2  金錢 + 8  人氣 + 9   查看全部評分

Rank: 5Rank: 5

UID
246042
帖子
2186
精華
0
積分
1416
威望
18
人氣
16
注冊時間
2012-5-5

論壇長老勛章

沙發
發表于 2020-2-26 14:04:53 |只看該作者
看到標題,以為是回形針

Rank: 4

UID
197150
帖子
535
精華
0
積分
696
威望
19
人氣
80
注冊時間
2011-9-18
藤椅
發表于 2020-2-26 14:06:35 |只看該作者
CFSO6198 發表于 2020-2-26 14:04
看到標題,以為是回形針

哈哈哈哈,確實是借鑒了他們的風格

Rank: 5Rank: 5

UID
246042
帖子
2186
精華
0
積分
1416
威望
18
人氣
16
注冊時間
2012-5-5

論壇長老勛章

板凳
發表于 2020-2-26 14:14:50 |只看該作者
yinluke 發表于 2020-2-26 14:06
哈哈哈哈,確實是借鑒了他們的風格

那就轉發抽送一列地鐵列車吧

Rank: 1

UID
415860
帖子
23
精華
0
積分
16
威望
0
人氣
0
注冊時間
2014-3-26
報紙
發表于 2020-2-26 14:18:01 |只看該作者

Rank: 4

UID
197150
帖子
535
精華
0
積分
696
威望
19
人氣
80
注冊時間
2011-9-18
地板
發表于 2020-2-26 14:22:08 |只看該作者
CFSO6198 發表于 2020-2-26 14:14
那就轉發抽送一列地鐵列車吧

那個男孩子不想擁有一列地鐵列車呢

Rank: 4

UID
267317
帖子
1435
精華
1
積分
869
威望
9
人氣
11
注冊時間
2012-8-31
7
發表于 2020-2-26 14:26:27 |只看該作者
從水平那張圖開始,就和實際左右對稱了

Rank: 4

UID
197150
帖子
535
精華
0
積分
696
威望
19
人氣
80
注冊時間
2011-9-18
8
發表于 2020-2-26 14:27:48 |只看該作者
八一館站 發表于 2020-2-26 14:26
從水平那張圖開始,就和實際左右對稱了

其實結果是隨機的,我挑了一些方位角度比較符合真實情況的

Rank: 5Rank: 5

UID
515348
帖子
2775
精華
2
積分
1794
威望
21
人氣
128
注冊時間
2016-3-16
9
發表于 2020-2-26 14:33:07 |只看該作者
雖然圖很亂 但是巨tm有意思,好評

Rank: 5Rank: 5

UID
622075
帖子
2970
精華
0
積分
1557
威望
23
人氣
120
注冊時間
2018-3-4
10
發表于 2020-2-26 14:34:11 |只看該作者
哪個男孩不想擁有一款地鐵制圖工具呢?

Rank: 4

UID
197150
帖子
535
精華
0
積分
696
威望
19
人氣
80
注冊時間
2011-9-18
11
發表于 2020-2-26 14:36:19 來自手機 |只看該作者
無盡星空 發表于 2020-2-26 14:33
雖然圖很亂 但是巨tm有意思,好評

我覺得動態那個還挺亮的

Rank: 3Rank: 3

UID
359356
帖子
525
精華
0
積分
472
威望
5
人氣
2
注冊時間
2013-8-12
12
發表于 2020-2-26 16:16:18 |只看該作者
有點意思

Rank: 3Rank: 3

UID
435924
帖子
278
精華
0
積分
272
威望
1
人氣
6
注冊時間
2014-7-2
13
發表于 2020-2-26 16:42:53 |只看該作者
dalaodalao🧍♂

Rank: 5Rank: 5

UID
637660
帖子
3277
精華
0
積分
1710
威望
0
人氣
-4
注冊時間
2018-6-22
14
發表于 2020-2-26 17:13:04 |只看該作者
拓撲結構 杠杠滴

Rank: 5Rank: 5

UID
5643
帖子
2216
精華
4
積分
2224
威望
93
人氣
4
注冊時間
2007-3-24
15
發表于 2020-2-26 17:14:24 |只看該作者
最復雜的一種算法,也是效果最好的,就是仿生(Organic)算法。可以理解成他把每個節點當成一個小小的有機體,自發地(去中心化地)尋找臨近的節點:


只要鏡像一下,這個已經很接近了。

發表回復

您需要登錄后才可以回帖 登錄 | 注冊地鐵族

回頂部 赫塔菲vs巴塞罗那17