我正在开发一个Python程序,用于处理Openstreetmap中的地图数据,并需要能够识别彼此靠近且平行的街道(路段)对。目前,我使用的基本算法非常低效:
1. 将所有街道(Street对象)放入一个大列表中。 2. 使用嵌套的for循环找到列表中的每一对可能的两个街道;对于每一对,绘制一个围绕两条街道的矩形,并计算每条街道定位的角度。 3. 如果矩形重叠,重叠区域足够大,并且角度相似,则认为该对街道是平行且相互靠近的。
这对于小地图来说效果很好,但是对于大地图来说最大的问题显然是因为城市中可能有数千条街道,所以会有大量的街道对需要迭代。我希望能够在不必将区域分成较小的块的情况下,在大范围(如城市)运行程序。
我考虑的一个想法是按纬度或经度对街道列表进行排序,并仅比较列表中彼此间距离在50个位置以内的街道对。这可能更有效,但仍然不太优雅;是否有更好的方法?
每个街道都由节点对象组成,我可以轻松地检索到每个节点对象和每个节点的纬度/经度位置。我也可以轻松地检索到街道定位的角度。
1. 将所有街道(Street对象)放入一个大列表中。 2. 使用嵌套的for循环找到列表中的每一对可能的两个街道;对于每一对,绘制一个围绕两条街道的矩形,并计算每条街道定位的角度。 3. 如果矩形重叠,重叠区域足够大,并且角度相似,则认为该对街道是平行且相互靠近的。
这对于小地图来说效果很好,但是对于大地图来说最大的问题显然是因为城市中可能有数千条街道,所以会有大量的街道对需要迭代。我希望能够在不必将区域分成较小的块的情况下,在大范围(如城市)运行程序。
我考虑的一个想法是按纬度或经度对街道列表进行排序,并仅比较列表中彼此间距离在50个位置以内的街道对。这可能更有效,但仍然不太优雅;是否有更好的方法?
每个街道都由节点对象组成,我可以轻松地检索到每个节点对象和每个节点的纬度/经度位置。我也可以轻松地检索到街道定位的角度。