细分匹配算法

#1 楼

可以使用Hausdorff距离：根据该距离，匹配段可以是“接近”段。在段上计算非常简单。

JTS中提供了免费的Java实现-请参见JTS Distance Package。您还可以查看JCS Conflation Suite（现已废弃的源副本，例如https://github.com/oschrenk/jcs）。

#2 楼

我不知道什么是“最佳”，因为这取决于细分的具体情况。

一种通常很好的方法是将细分散列为关键的几何信息。至少包括中心的位置（x，y），方向（0到180度）和长度。在应用了适当的权重和方向的精细化处理（因为180“环绕”回到0）之后，您几乎可以将所有统计聚类算法应用于所有分段的集合。 （K均值将是一个不错的选择，但是大多数分层方法都应该工作良好。此类聚类分析倾向于快速且易于应用。）理想情况下，分段将成对出现（或对于不匹配的分段为单例），其余部分成对出现。很容易。

处理方向问题的一种方法是复制标记的片段。如果第一份副本的方向小于90度，则将其增加180度，否则将其减去180度。 （显然）这会扩大数据集，但不会以任何方式更改算法。

之所以需要权重，是因为坐标，长度和方向的差异可能意味着与它们相应段的相似性完全不同的事物。在许多应用中，段之间的差异是由其端点位置的差异引起的。作为粗略的近似，我们可以预期段长度的典型变化与其端点之间的典型变化大致相同。因此，与x，y和长度关联的权重应大致相同。棘手的部分是权重方向，因为方向不能等同于距离，更糟糕的是，短片段比长片段更容易错位。考虑一种反复试验的方法，该方法将一些方向错误的现象等同于段之间的典型间隙的大小，然后对其进行调整，直到该过程似乎运行良好为止。作为指导，令L为典型的段长度。以较小的角度t度改变方向将扫出大约L / 2 * t / 60的距离（60近似于一个弧度的度数），即L / 120乘以t。这建议从x，y和长度的单位权重以及方向的权重L / 120开始。

总而言之，此建议是：


复制带标签的片段的副本（如关于对齐方向的段落中所述）。
将每个片段转换为四倍（x，y，长度，L / 120 *方向），其中L是典型的片段长度。
对四元组进行聚类分析。使用良好的统计数据包（R是免费的）。
使用聚类分析输出作为查找表，将带标签的细分与附近的无标签细分相关联。

#3 楼

大约5年前，我从事了一个具有类似要求的项目。它涉及将来自街道中心线的坐标（坐标精度相对较高）与高速公路性能监控系统（HPMS）交通网络链接相结合。

当时，联邦公路管理局没有提供任何工具来进行此类操作事情。情况可能已经改变，您可能要检查一下。即使您不使用高速公路数据，这些工具也可能仍然有用。

我是用ArcGIS编写的，但是该算法应该在开源中工作，只要它提供类似于ISegmentGraph的跟踪功能：

// features is a collection of features with higher geometry
// Links are a collection features with attributes but low res geometry
For each Link in lowResFeatureclass
    point startPoint = SnapToClosestPoint(Link.StartPoint, hiResfeatures);
    if(startPoint == null)
       continue;
    point endPoint = SnapToClosest(Link.EndPoint, hiResfeatures);
    if(endPoint == null)
       continue;
    polyline trace = Trace(hiResfeatures,startPoint,endPoint);
    if(polyline != null)
    {
        // write out a link with high precision polyline
        Write(Link,polyline);
    }
Next Link

#4 楼

这是一个想法

如果您将其中一个线串拆开以进行比较并测试顶点是否与另一个线串相距一定距离以进行比较，则可以通过多种方式控制测试。

这些示例在PostGIS中工作（可能会猜到:-)）

首先，如果我们说如果table_1的线串中的所有顶点都为0.5米（地图单位），则存在匹配项）或更接近table_2中的线串：

SELECT a.id, b.id FROM
(SELECT ST_NPoints(the_geom) as num_of_points,
(ST_Dumppoints(the_geom)).geom as p, id FROM table_1) a 
INNER JOIN 
table_2 b 
ON ST_DWithin(a.p, b.the_geom, 0.5) GROUP BY a.id, b.id
HAVING COUNT(*)=num_of_points;

然后我们可以说，如果table_1的线串中的vertex_points的60％以上在表_2中线串的距离

SELECT a.id, b.id FROM
(SELECT ST_NPoints(the_geom) as num_of_points, 
(ST_Dumppoints(the_geom)).geom as p, id FROM table_1) a 
INNER JOIN 
table_2 b 
ON ST_DWithin(a.p, b.the_geom, 0.5) GROUP BY a.id, b.id
HAVING COUNT(b.id)/num_of_points::float > 0.6

或者我们可以接受一个点不在范围内：

SELECT a.id, b.id FROM
(SELECT ST_NPoints(the_geom) as num_of_points, 
(ST_Dumppoints(the_geom)).geom as p, id FROM table_1) a 
INNER JOIN 
table_2 b 
ON ST_DWithin(a.p, b.the_geom, 0.5) GROUP BY a.id, b.id
HAVING COUNT(b.id)-num_of_points <= 1;

您还必须以相反的角色使用table_1和table_2运行查询。

我不知道它的运行速度如何。 ST_Dumppoints当前是PostGIS中的sql函数，而不是C函数，这使其慢于应有的速度。但我认为无论如何都会很快。

空间索引将有助于ST_Dwithin发挥作用。

HTH
尼克拉斯

#5 楼

我已经编写了代码来处理边界生成器中的草率线段匹配（并使它们重叠）。我在这里写下了它的（相当基本的）数学公式：http://blog.shoutis.org/2008/10/inside-boundary-generator-computational.html。该代码是开源的，并且可以从该博客文章中链接。

该代码遵循一种非常简单的方法：


段分段测试，它将告诉您是否两个线段在给定的角度和距离公差以及重叠量内重叠。
快速的“肮脏”空间索引消除了针对数据集中的所有其他线段测试数据集中的每个线段的需要。

这种方法的主要优点是您可以得到精确的旋钮，以获取有效的角度，距离和重叠长度。不利的一面是，它不是一种通常测量两个线段相似度的方法，因此难度更大。进行统计聚类以确定可能的匹配-您被精确的旋钮卡住了。

注意：我猜测如果有足够的SQL印章，您可以将段-段测试填充到WHERE子句中。 .. :)

干杯！

#6 楼

我在这里为地图匹配实现了一个粗糙的原型，相对易于使用。它基于开源路由引擎并用Java编写。此处描述了所使用的算法。