如何維護城市道路數據？ （數據結構，我應該使用什麼）

Question

（對不起我的英文不好，但我會盡量句話很清楚）

例如，我有道路數據的形式是這樣的：

  Latitude  Longitude 
RoadA(consists of 2 dots) 
      31.263319  121.5555711 
      31.2619722 121.5564754 
RoadB(consists of 3 dots) 
      31.2619722 121.5564754 
      31.2611567 121.557023 
      31.2610903 121.557088 

正如你所看到的，每條道路由幾個（2〜x）點組成。道路可能是一條曲線，需要許多點來描述它。在兩點之間，它們通過直線相連。

一旦我讀完所有的道路數據，我會讀一組點，我的任務是，一旦給出了一個新的點，我需要找出它是否在任何道路上。如果不是，我需要向最近的道路繪製垂直線，並找出踏板腳的座標（道路上最近的點）。

查詢量很大，所以我需要速度儘可能快。我應該使用哪種數據結構？

Answer 1

遊戲開發和理論中存在一些空間劃分方法。 也許你應該使用其中之一。 link

你應該在Binary，Quad，Oct，...樹中劃分你的位置。 我認爲最好的方法，就是使用對的地圖。