在地图中寻找相邻平行街道对的有效算法

Question

我正在开发一个Python程序，该程序处理Openstreetmap中的地图数据，我需要能够识别彼此靠近且平行的街道（道路）对。现在，我使用的基本算法效率很低：

1. 将所有街道（街道对象）放入一个大列表中
2. 使用嵌套的for循环查找列表中两条街道中的每一对；对于每一对，在两条街道周围绘制一个矩形，并计算每条街道的方向角。在
3. 如果矩形重叠，则重叠区域足够大，且角度相似，则认为成对的两条街道平行且彼此靠近。在

这对于小地图很有效，但是对于大地图来说，最大的问题显然是需要迭代大量的对，因为一个城市中可能有数千条街道。我希望能够在一个大的区域（如城市）上运行该程序，而不必将该区域分割成小块。在

我想的一个想法是按经纬度对街道列表进行排序，只比较列表中彼此相距50个位置内的成对街道。它可能会更有效，但看起来还是不太优雅；有更好的方法吗？在

每个街道都由节点对象组成，我可以轻松地检索节点对象和每个节点的横向/纵向位置。我还可以很容易地检索出街道的方位角。在

Answer 1

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

然后，假设您可以准确地识别角度，并且您需要一对具有相同角度的街道。（由于浮点精度和所需街道在数据中可能不完全平行，这并不是一个真实的情况，但让我们暂时忘掉这一点。）

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

这种排序可以很容易地完成，无需任何交叉点，您只需计算从原点（或任何其他固定点）到该街道线的距离，然后按此距离对街道进行排序。（如果您有一条由标准直线方程Ax+By+C=0定义的街道，那么到原点的距离是C/sqrt(A*A+B*B)。）

现在你已经有了所有需要的平行的封闭的街道，按照这种顺序彼此非常接近。如果所有的街道都是无限长的，那么这些最接近的街道总是一个接一个；如果街道长度有限，中间可能会有更多的街道，但我认为，在任何实际数据中，它们的数量都会非常少。所以你可以取一些距离差的阈值，然后检查所有在这个阈值内的线对。在

现在让我们记住，角度的定义并不精确。我可以建议以下方法。维护一个二元搜索树（如C++的^ {CD3}}），搜索关键字将是从原点到街道线的距离。沿着街道走，因为它们是按角度排列的。在树上，我们将保留所有角度相差小于某个阈值的街道。因此，在每一时刻，树上的每一条街道，它在树上的邻居将有两个角度的不同小于阈值，而距离原点的距离则小于某个阈值。因此，对于每个街道，请执行以下操作：

• 把这条街加到树上
• 对于树中的所有街道，但是它们的角度与当前街道的角度相差太大，请从树中删除这些街道
• 现在处理添加的街道：查看树中搜索关键字（与原点的距离）在所需阈值内的所有街道，然后检查这两条街道（添加的街道，另一条街道）。在

第一个点是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

你处理垃圾箱中的片段的想法不错。您确实需要考虑穿过垃圾箱边界的路段会发生什么。在

另一种方法是对所有路段进行Hough变换。每条线段所在的无限长直线对应于二维Hough空间中的一个点：直线的极角为一个轴，到直线最近点原点的距离为另一个轴。从直线上的两点到Hough点的变换是简单的代数。在

现在，您可以使用最近点对算法来检测几乎共线的路段。幸运的是，这可以在预期的时间内完成。E、 g.使用k-d树。在树中插入所有点。使用标准的k-d树算法寻找每个点的最近邻。对对距离进行排序，并将结果的前缀作为对来考虑，在两个对相距太远而无法满足“邻近且平行”的条件时停止。有O（n）这样的最近邻对。在

剩下的就是过滤掉那些几乎共线但不重叠的段对。这些线段位于同一条无限线的不同部分上或附近，但它们并不有趣。这只是一点代数。在

关于这里提到的所有算法，维基百科上有相当好的文章。如果他们不熟悉的话就去看看。在