GPS寻找邻近道路

Question

所以我正在构建一个GPS应用程序。我有一组道路对象，每个道路对象都包含一个起点和终点（加上道路弯曲的其他中点）。我已经实现了用于查找最短路径（其中道路是图中的节点）的dijkstra算法，但是在我运行它之前，我需要确定哪些路相邻（连接）彼此以创建边。

轻松（？）的方式是迭代每条道路并在嵌套循环中查看是否有其他道路也在同一点开始/结束。但是这似乎是O（N^2）的低效率。其中一个想法是将道路预先分成区域（即在英国有NW，NE，E，SE，SW等），然后只在相同区域寻找邻居，以减少搜索空间。

寻找更多经验程序员的建议，你会如何解决这个问题？

这不是一个家庭作业，刚刚毕业时，我正在将此作为一个宠物项目，以获得一些实践经验并填写简历。

编辑：我应该先添加道路永远只在起点/终点连接

Answer 1

你可以整理所有的（X，Y）点，你有，用x由y。对于n个点，如果使用基数排序，这应该是O（nlogn），或者甚至是线性的。那么你只需要通过列表;每当两个相邻的条目相等时，它们相应的道路相交。