从道路网络中提取拓扑(.NET)

Question

我们有多个来自多个来源的高质量道路网络(Open Street Map,TomTom ......).这些来源包含的信息比我们需要的更多,有效地阻止了我们的计算.过滤二级公路很容易.我们的主要问题是高速公路(两条相反方向的道路)的代表,复杂的公路交叉口(各种出口道路,交叉点不是点).就我们的目的而言,更具"拓扑"风格的道路网络将是理想的.

高度详细的数据来源:

理想的简化网络:

是否有任何算法可以帮助我们提取简化的道路网络？如果.NET中有可用的实现,那将是一个真正的赢家.

更新:

原始数据表示为折线,附加了一些有限的元数据.元数据告知道路的标识(名称或编号),道路的"等级"(高速公路,主要,次要等),以及一些更多细节,如速度限制,线路部分是桥梁还是隧道.数据的质量非常好,我们可以轻松地将折线段组合在一起,根据道路标识一起形成道路.同样,忽略二级公路也很容易.高速公路出口处的加速/减速车道也在其等级中明显标出,因此它们也易于过滤.

我们看到两个主要问题:

1)高速公路:用一条道路替换两条(或多条)单向道路

2)高速公路交叉口:确定交叉点的中心点,并确保我们的简化高速公路与之相连.

更新2: 数据存储在EZRI Shape文件中.使用SharpMap库,它们相对容易解析或进行地理空间搜索.源数据按国家/地区分段,一个国家/地区是一个形状文件(如果国家/地区太大,如美国,德国),则进一步划分为较小的区域.是的,这种划分带来了另一个问题.如何确保法国和德国边境的简化高速公路相遇？

Thanx为关注

Answer 1

这只是解决方案的草图，但是：

• 定义曲线对之间的距离度量。第一个想到的是两条曲线围成的面积除以它们的长度。您可以使用元数据来增强这一点。目标是设计一种度量，为您认为相似的道路对提供较小的距离，为您认为不相似的道路提供较大的距离。

• 现在选择一个聚类算法，并要求它根据您刚刚定义的距离对道路进行聚类。对你让它使用的集群数量要非常慷慨。当它返回时，寻找“直径”非常小的簇，这意味着簇中的每个点都非常相似。“完全连锁聚类”可能是开始您的研究的好地方，因为它恰好导致了这种聚类。

• 然后，您可以取每个集群中的平均值，将非常相似的道路集合转变为一条道路，从而解决您的问题 (1)（希望也能解决 (2)）。

完成后，下一个任务是区分“重要”道路和“不重要”道路。这里最好的方法是坐下来建立一个由数百条随机道路组成的训练集，手动标记它们是否重要。然后采用某种分类器并在手动标记的集合上训练它们。然后要求它预测哪些其他道路是重要的。

我不能说哪个分类器最好使用，但如果您能抽出时间构建大型训练集并研究文献，“神经网络”可以给出一些令人印象深刻的结果。如果您想要更简单的东西，请查看“随机森林”或（甚至更简单）“逻辑回归”。