GPS尋找鄰近道路

Question

所以我正在構建一個GPS應用程序。我有一組道路對象，每個道路對象都包含一個起點和終點（加上道路彎曲的其他中點）。我已經實現了用於查找最短路徑（其中道路是圖中的節點）的dijkstra算法，但是在我運行它之前，我需要確定哪些路相鄰（連接）彼此以創建邊。

輕鬆（？）的方式是迭代每條道路並在嵌套循環中查看是否有其他道路也在同一點開始/結束。但是這似乎是O（N^2）的低效率。其中一個想法是將道路預先分成區域（即在英國有NW，NE，E，SE，SW等），然後只在相同區域尋找鄰居，以減少搜索空間。

尋找更多經驗程序員的建議，你會如何解決這個問題？

這不是一個家庭作業，剛剛畢業時，我正在將此作爲一個寵物項目，以獲得一些實踐經驗並填寫簡歷。

編輯：我應該先添加道路永遠只在起點/終點連接

Answer 1

你可以整理所有的（X，Y）點，你有，用x由y。對於n個點，如果使用基數排序，這應該是O（nlogn），或者甚至是線性的。那麼你只需要通過列表;每當兩個相鄰的條目相等時，它們相應的道路相交。