LINE Corporation 於2023年10月1日成爲 LY Corporation。LY Corporation 的新部落格在這裏。LY Corporation Tech Blog

Blog


在 「LINE 熱點」服務上如何處理地理性資訊 ( Serving Location-based data)

寫在前面

大家好,我是 LINE Taiwan DevRel 團隊的 Evan Lin。很開心在這裡跟各位分享本年度的第三場開發者小聚中,由 LINE SPOT Team – Julian Shen 帶來分享他在處理地理資料 (location-based data) 時候所遇到的一些問題與經驗分享。關於LINE SPOT 可以參考 Julian 在 TECHPULSE 2019 的會場有介紹過關於 LINE SPOT 服務介紹。更多的 LINE SPOT 服務介紹與 LINE SPOT 架構介紹可以參考這篇文章 「LINE TAIWAN TECHPULSE 2019 科技盛會精彩回顧」

KKTIX 活動網頁: 活動網址

其他相關文章:

投影片

演講影片

https://www.youtube.com/embed/Dir0iUpAjH4

地理資訊服務 Location-Based Services

這次主要介紹 LBS: Location-Based Serivice 的內容,關於 LBS 相關的遊戲或是服務我們經常可以看到,舉凡打卡,地圖,導航都會用到。那麼要尋找兩個點之間距離上,可以使用的技術也相當的多。

找出距離幾公里的景點

處理上面經常是拿到 GPS 座標,或是直接拿到地址。 地址是可以方便人類來閱讀的,但是真正要電腦能夠處理的就是經緯度的座標位置。 如果要對某一個座標找尋出距離三公里距離的所有座標,那是不是需要把資料庫裡面的地點全部拿來計算呢? 這裡介紹了一種方式叫做 K-D Tree 。

K-D Tree 的方法就是將地圖平面透過二分法的方式來切割,將每兩個點找出距離後作為一個區塊。透過這樣的方式可以很快速地找出兩個最相近的距離點。

如何將搜尋結果作 Caching

如果有一群人同時開 LINE SPOT 需要尋找三公里內所有座標,那麼有方式可以快速的暫存起來資料,並且快速的回覆使用者的需求嗎? 這時候可以考量使用 Geo Hash 的方式來將經緯度數值直接轉換成一串文字,透過這個方式可以快速找到上一次搜尋的結果。如果沒有搜尋過才去跑 K-D Tree 的搜尋,這樣一來就可以在不經過複雜的運算就可以快速的回覆使用者。http://speakerdeck.com/player/cbb774e9c4494d28953fb6f11c8cd36b?slide=22

這個方式雖然可以快速地知道有沒有搜尋過,但是有一些問題如下:

  • 由於採取 zig zag travesal 的方式來 hashing ,可能不同的經緯到有相當相似的結果。
  • 可能相當的接近,由於在邊界上可能造成 geo hashing 結果不同。

其他的方式

Google 也有提出 S2 Cell ID 的方式來區分地理資訊。而 Uber 也有提出 H3 的方式,透過六角形的方塊來切分整個地理資訊。也因為使用六角形,才能更精確地將地球球形的地理狀況表現出來。

「LINE 熱點」美食推薦

別再說新竹市美食沙漠, LINE 熱點也是有精選「十家新竹在地美食店家」。

活動小結

希望同學們了解地理資訊的處理經驗分享後。也都可以來 LINE 熱點來分享你的新竹美食地圖。

立即加入「LINE開發者官方社群」官方帳號,就能收到第一手Meetup活動,或與開發者計畫有關的最新消息的推播通知。▼

「LINE開發者官方社群」官方帳號ID:@line_tw_dev

關於「LINE開發社群計畫」

LINE今年年初在台灣啟動「LINE開發社群計畫」,將長期投入人力與資源在台灣舉辦對內對外、線上線下的開發者社群聚會、徵才日、開發者大會等,已經舉辦30場以上的活動。歡迎讀者們能夠持續回來察看最新的狀況。詳情請看: