在地图中寻找附近且平行的街道对的高效算法

Question

在地图中寻找附近且平行的街道对的高效算法

4

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

1. 将所有街道（Street对象）放入一个大列表中。 2. 使用嵌套的for循环找到列表中的每一对可能的两个街道；对于每一对，绘制一个围绕两条街道的矩形，并计算每条街道定位的角度。 3. 如果矩形重叠，重叠区域足够大，并且角度相似，则认为该对街道是平行且相互靠近的。

这对于小地图来说效果很好，但是对于大地图来说最大的问题显然是因为城市中可能有数千条街道，所以会有大量的街道对需要迭代。我希望能够在不必将区域分成较小的块的情况下，在大范围（如城市）运行程序。

我考虑的一个想法是按纬度或经度对街道列表进行排序，并仅比较列表中彼此间距离在50个位置以内的街道对。这可能更有效，但仍然不太优雅；是否有更好的方法？

每个街道都由节点对象组成，我可以轻松地检索到每个节点对象和每个节点的纬度/经度位置。我也可以轻松地检索到街道定位的角度。

- tlng05

你想做什么？在起点和终点节点方面平行的街道只有平均角度相同，但很可能不是平行的。你是在寻找平行的街道段吗？或者是共享节点并朝着同一个方向行驶的街道？你的问题描述得很清楚，但似乎不是你想要解决的实际问题？ - H W

2个回答

3

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

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

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

这种排序可以很容易地完成，无需任何交集，您只需要计算每条街道从原点（或任何其他固定点）到该街道线的距离，并按此距离对街道进行排序。（如果您有一条由标准直线方程定义的街道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)的时间复杂度内完成。

这并不会“循环”数组，也就是不考虑排序数组中一个位于末尾，另一个位于开头的街道对，但这很容易解决。

- Petr

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Gene · Accepted Answer

你的将路段处理成 bin 的想法不错。但是，你需要仔细考虑穿越 bin 边界的路段会发生什么。

另一个想法是对所有路段进行 Hough 变换。每个路段所在的无限直线对应于 2D Hough 空间中的一个点：直线的极角是一个轴，距离直线最近点到原点的距离是另一个轴。从一条直线上的两个点到 Hough 点的变换只需要简单的代数运算。

现在，可以使用最近点对算法检测几乎共线的道路段。幸运的是，这可以在 O(n log n) 的预期时间内完成。例如，可以使用 k-d 树。将所有点插入树中，使用标准的 k-d 树算法查找每个点的最近邻居。对一对点的距离进行排序，并将结果的前缀作为要考虑的对，停止在距离太远以至于不符合“附近和平行”的标准时。这样的最近邻点对有 O(n) 个。

现在只需要过滤掉 - 尽管几乎共线 - 但不重叠的路段对。这些路段位于或靠近同一条无限直线的不同部分，但它们并不是感兴趣的。这只需要一点点更多的代数运算。

关于这里提到的所有算法，都有相当不错的维基百科文章。如果不熟悉，请查找相关内容。