高效的算法在地图

Question

我在从OpenStreetMap的处理地图数据的Python程序工作发现对附近的，平行的街道，我需要能够识别的街道（路）对那些彼此靠近和平行。现在，我使用的基本算法是相当低效：

1. 把所有的街道（街道对象）进入大名单
2. 使用嵌套循环for查找列表中的每一个可能对两条街道;对于每一对，在两条街道周围绘制一个矩形，并计算每条街道所朝向的角度。
3. 如果该矩形重叠时，重叠区域是足够大的，并且角是相似的，在对中的两个街道被认为是平行且相互靠近。

这对于小地图很好，但对于大地图，最大的问题显然是会有大量的对要迭代，因为可能会有成千上万的城市街道。我希望能够在大面积（如城市）上运行该程序，而不必将区域分割成更小的部分。

一个想法，我想的是通过经纬度排序街道的名单，而只有比较对街道是内说，50个位置远离彼此的名单。它可能会更有效率，但它看起来还不够优雅;有没有更好的办法？

每个街道由Node对象的，我可以很容易地检索两个节点对象和每个节点的纬度/经度位置。我还可以轻松地检索街道所朝向的角度。

Answer 1

我认为首先要做的是按角度对所有街道进行排序，从而使所有平行的街道彼此靠近。

然后，假设一开始，你可以识别的角度正是和你需要对具有完全相同相同的角度街道。 （由于浮点精度以及由于所需街道在数据中可能不完全平行的事实，这并非真实情况，但我们暂时忘了这一点。）

然后所有排序的街道都可以被分成相同方向的组。在每个这样的组中，存在如下定义的自然顺序。考虑另一条垂直于所有街道的方向相同的线。对于任何这样的街道，考虑与该垂直线的交叉点，并通过该交叉点对所有这些街道进行分类（我假设所有街道都是无限长的）。

此排序可以在没有任何交集很容易做到，你只需要通过这个距离计算各街道从产地（或任何其他固定点）到街道线的距离和排序街道。 （如果你有一条由标准直线方程Ax+By+C=0定义的街道，那么这个距离原点的距离是C/sqrt(A*A+B*B)。）

现在你已经拥有了所有需要的平行靠得很近的街道，这个排序顺序非常接近。如果所有的街道都是无限长的，那么最接近的两条街道总是会一个接一个。有限长度的街道之间可能会有额外的街道，但我认为在任何实际的数据中都会有很少的街道。所以，你可以采取一些距离差异的门槛，并检查其中的所有对。

现在让我们记住角度没有精确定义。我可以建议那么下面的方法。为街道维护一个二叉搜索树（类似于C++的std::map），搜索键将是从原点到街道的距离。按顺序沿街道排列，因为它们按角度排序。在树中，我们将保持角度相差小于某个阈值的所有街道。因此，在树中的每条街道的每一次，其树中的邻居将具有不同于小于阈值的两个角度，并且与起点的距离相差小于某个阈值。因此，对于每个街道，做到以下几点：

• 这条街上添加到树
• 对于这一切都在树上，而是有自己的角度，从当前街道的角度也不同街道，清除这些从树上的街道
• 现在处理添加的街道：查看树中具有所需阈值内的搜索关键字（距离原点的距离）中的所有街道，并检查一对（增加的街道，另一条街道）。

第一点是O(log N)，第二个是O(log N)每删除街头，如果你只是一味另一个指针指向一起到街上排序的角度阵列要删除运行，第三个是O(log N)％的人认为邻居街道。

一个非常粗糙的伪代码：

sort lines by angle 
r = 0 // the street to be deleted from the tree 
for l=0..n-1 
    tree.add(street[l]) 
    while street[r].angle<streel[l].angle-angle_threshold 
     tree.remove(street[r]) 
    other_street=tree.prev(street[l]) 
    while other_street.dist>street[l].dist-dist_threshold 
     process(street[l], other_street) 
     other_street = tree.prev(other_street) 
    other_street=tree.next(street[l]) 
    while other_street.dist<street[l].dist+dist_threshold 
     process(street[l], other_street) 
     other_street = tree.next(other_street) 

这里tree.prev找到以前的街道树，即具有最大距离的街道是小于给定街的距离，tree.next同样发现了另一条街上。这两项操作都可以在O(log N)中完成。

这不会“循环”数组，即不会考虑一对位于排序数组非常末端而另一个位于最开始处的街道对，但这很容易解决。

Answer 2

你的处理垃圾箱中段的想法并不差。您确实需要考虑通过箱体边界的路段会发生什么情况。

另一个想法是霍夫变换所有的路段。每个段所在的无限长线对应于2d Hough空间中的一个点：该线的极角是一个轴，并且该线的最近点的原点的距离是另一个轴的距离。从一条线上的两点到霍夫点的转换是简单的代数。

现在，您可以使用最近点对算法来检测几乎共线的路段。令人高兴的是，这可以在O（n log n）预期的时间内完成。例如。使用k-d树。将所有点插入树中。使用标准k-d树算法来查找每个点的最近邻居。排序对距离并以结果的前缀作为成对的考虑对象，停止对的距离太远而不符合“附近和平行”的标准。这些最近邻居对有O（n）个。

剩下的就是过滤出线段对 - 虽然几乎是线性的 - 不会重叠。这些部分位于同一无限线的不同部分或其附近，但它们并不感兴趣。这只是一个更多的代数。

这里提到的所有算法都有相当不错的维基百科文章。如果他们不熟悉，请查看他们。