摘要：輾轉流傳出班車手冊后發現搜索實在是太不方便了，于是有了一個主義，想做一個可以搜索房子地址，找出附近班車點類似大眾點評的定位搜索附近餐館的功能。

七月份要去某廠報道了，異地租房的時候發現想租一個有公司班車的地方，卻不知道哪里有班車。輾轉流傳出班車手冊后發現搜索實在是太不方便了，于是有了一個主義，想做一個可以搜索房子地址，找出附近班車點（類似大眾點評的定位搜索附近餐館的功能）?，F在做的差不多了，發現好像本來公司就有做這個東西。。權當學一下一些位置匹配的技術了。
最后成果是這樣子的：

大頭針是輸入的位置（福田中學），附近的藍點就是一個一個站點。由于一個站點他會在上班下班夜班不同的線路的不同站點位置，會在不同時刻到達，因此聚合為多個同一站點的數據會聚合為一個點。點擊藍色的站點就會在下面顯示出這個站點所在的所有線路。

下面將分為幾個步驟講一下具體使用了什么方法什么技術：

一開始拿到的是excel手冊，所以我們有的原始數據是長成這樣的（忽略的從excel中導出的步驟）：
["A(B門口)(07:30)→C(政府前100米天橋下)(07:45)→D(2站臺前10米)→E→F(09:12)", ...路線二, ...路線三]
然后我們需要做的事情是：

從數組里把每一條線路的站點拆分成一個個獨立的單元
這一步比較簡單，str.split("→")

每一個單元分離出站點和時間
這一步要做的就多一點點了，需要用到正則匹配，而且因為站點的名字其實是有多種的，需要考慮到多種情況。因此我的方法是：

先用/(.*)(([0-9:]*))/分離時間和站點，因為只有時間是左右括號內只包含數字和:的。

實際上站點名稱里有一些非法字符，因此還需要進行一步過濾station.replace(/([^u4e00-u9fa5()d])/g, "")

每一個站點獲取到經緯度
這個就沒啥好說的了。。調用騰訊地圖的api，不過由于調用api有每秒請求數和每日請求數的限制，用異步回調加定時器的方式模擬了休眠，然后運行腳本慢慢等結果返回就好了。

我參考的資料
簡單介紹一下geohash就是，把經緯度按照一定的規則去映射出一個hash字符串，在后續搜索的時候，只要hash字符串匹配程度足夠高就可以認為這兩個點是相近的。具體的內容可以閱讀上面的參考資料。下面給我javascript代碼的實現。

function geoHashCode (num, range) {
    range = [-range, range]
    let retCode = []
    for (let i = 1; i <= 20; i++) {
        let middle = (range[0] + range[1]) / 2
        let code = num < middle ? "0" : "1"
        if (code === "0") {
            range[1] = middle
        } else {
            range[0] = middle
        }
        retCode.push(code)
    }
    return retCode
}
function geoHash ({ lng, lat }) { // lng: 經度， lat： 緯度
    let lngCode = geoHashCode(lng, 180)
    let latCode = geoHashCode(lat, 90)

    // 偶數位放經度，奇數位放緯度，把2串編碼組合生成新串
    let code = []
    for (let i = 0; i < 40; i++) {
        if (i % 2 === 0) { // 偶數
            code[i] = lngCode[i / 2]
        } else {
            code[i] = latCode[(i - 1) / 2]
        }
    }

    const base32 = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "b", "c", "d", "e", "f", "g", "h", "j", "k", "m", "n", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"]

    let newCode = []
    const splitLen = 5
    for (let i = 0; i < 8; i++) {
        newCode.push(code.slice(i * 5, i * 5 + 5).join(""))
    }

    // base32編碼
    newCode = newCode.map(item => base32[parseInt(item, 2)]).join("")

    return newCode
}

經過上述步驟，我們可以得到什么呢？
一個很大的list，每一個單元為

{
    station:班車名字,
    location:該點的經緯度,
    name:屬于上班下班夜班中的哪一個,
    lineIndex:屬于該班車類型的拿一條線路,
    stationIndex:屬于該線路里的第幾個站點,
    time:到站時間,
    geohash:該點經緯度映射出的的geohash
}

到這一步其實已經可以做到輸入一個點，匹配出附近班車的點了，只要把輸入的點通過api查詢出經緯度，再轉化成geohash，最后遍歷這個list把匹配程度足夠高的點挑出來就可以了。
但是其實我們有5000個這樣的點，在頁面上不斷做這種遍歷匹配我覺得挺蠢的，于是我想到構建一個匹配樹。把一組hash映射成一個匹配森林，然后輸入點的geohash不斷尋找匹配節點去遍歷這個森林的時候可以完全避開不匹配的項去提高匹配效率。舉個例子就是:

我們根據左側的hashList映射出右側的匹配森林，由于geohash的精度關系是會出現多個站點的geohash是一樣的。因此我在葉子節點里用一個數組存放所有的對應站點信息。當我們要匹配"wsc2"時我們可以一直搜索到葉子節點，取出‘站點1，站點2’,但是有時候我們要搜索的geohash沒辦法匹配到葉子節點，我們就要先判斷當前精度是否足夠高，誤差會不會太大，比如我們認為匹配了三個前綴字符的時候精度就足夠高了，那么搜索"ws11"的時候由于只匹配到兩個，不應返回結果。而匹配"wsc3"的時候，可以匹配到前綴字符"wsc"，雖然沒有到葉子節點，但是我們可以認為以"wsc"為根（大概是那個意思你們應該明白）的樹的所有葉子節點都可以認為是這個geohash的附近節點，也就是返回"站點1，站點2，站點6"。至于誤差范圍可以看上面的參考文獻。

騰訊地圖或者其他地圖的開放接口

獲取輸入地址轉化為經緯度和geohash

查找樹獲取匹配的地址在list中的index

聚合相同經緯度的點為一個繪制點
將經緯度作為鍵名構建一個map

繪制，附近的點為藍色，輸入的點為大頭針，綁定附近的點的點擊事件（渲染列表，生成該點的所有線路信息）

這個小玩具就這么結束了，中間其實還有一些值得一提的地方。我也就一起記下來了，感覺還是挺有趣的，做一些好玩的東西。

必備知識點： sync/await（只是因為這么寫看起來很爽，沒有別的意思

function sleep () {
    return new Promise((resolve, reject) => {
        setTimeout(() => {
            resolve()
        }, 500)
    }) 
}
(async function () {
    let i = locationList.length // 計數器
    let newList = []
    while (i !== -1) {
        let item = locationList.pop() // 取出要查詢的點
        let location
        try {
            if (locationMap[item.station]) { // 如果這個點請求過了就直接用緩存信息
                location = locationMap[item.station]
            } else {
                location = await getXY(item.station) // 調用api獲取經緯度
                locationMap[item.tation] = location // 緩存經緯度信息
                await sleep() // 休眠
            }
            item.location = location
            item.geoHash = geoHash(location) // 獲取geohash
            newList.push(item)
        } catch (e) { // 請求失敗了，把這個點推回去重新請求
            console.log(e)
            locationList.push(item)
            i++
        }
        i--
        console.log(i)
    }
})()

其實一開始設計的時候沒有查詢地點附近的班車站點功能的。而是顯示上班線路下班線路的功能。不同線路之間的轉換用了數據劫持的方式，也就是vue實現數據綁定的Object.defineProperty，還真的挺有意思的，建議大家也可以用這個試一下。另外還有單頁應用路由里面的hashchange事件。這些都是些可以再創造的api。