确定给定折线与一组现有折线的近似重叠。

Question

我有一组折线（数量在数十万条左右，每条折线大约有200-300个顶点）。它们代表地图上的路径（如果有帮助，这些折线均来自Google Maps API），其中顶点是纬度/经度坐标。

现在我有一个查询折线，并且我必须找到查询折线与任何现有折线的“重叠部分”。结果本身将是折线，按最大到最小重叠排序。我只需要前100个结果左右。另一个问题是重叠不需要是精确的，但可以是近似的（即被视为重叠的线段部分不需要相互覆盖，只需要“接近”彼此）。

为了具体表示，在下面的图像左侧，蓝色折线（折线A）是数据库中的折线，红色折线（折线B）是查询折线。算法应确定如右侧所示的用粗黑线标记的折线。

我目前倾向于使用空间数据库（正在考虑的选项是PostgreSQL + PostGIS），但我不确定延迟是否可接受 - 查询需要立即返回结果。我的计算几何功力令人遗憾，但我想知道：是否有任何现有的算法或方法可以解决这个特定的问题？

提前致谢！

- ARV

---

相关链接：http://gis.stackexchange.com/q/59729/16594 - Jakub Kania

Answer 1

快速近似查询，您不需要找到所有匹配项，类似于局部敏感哈希http://en.wikipedia.org/wiki/Locality-sensitive_hashing - 我怀疑您会得到很多点击量。一段时间以前，我被http://www.cs.ubc.ca/~lowe/papers/09muja.pdf所吸引 - 我不知道它在实践中是否有效，但是重新发现论文的相同搜索在http://www.cs.ubc.ca/research/flann/找到了一个库。直接LSH的维基百科页面底部有至少一个实现指针。 LSH的优点是可以与关系数据库或dbm文件轻松转换为数据库查找。

- mcdowella

Answer 2

鉴于问题规模较大，我建议您采用分网格方法。我的意思是在地图上覆盖一个正方形网格，并为每个瓦片（我们称之为像素）保留跨越它的折线列表。从某种程度上讲，这相当于使用Bresenham算法或其变体对地图执行光栅扫描转换。

同样，您可以绘制查询折线并收集与前者共享一个或多个像素的所有折线。您可以计算共同像素的数量以获得重叠长度的第一个估计值。为了吸收离散化带来的不准确性，绘制“粗”线可能是明智的选择。

在这个第一次筛选通过后，需要考虑的折线数量将大大减少，因此可以使用任何暴力方法进行重叠评估。

一个关键问题是网格分辨率。过于粗糙将导致候选拒绝效率低下。太细将以无法接受的方式增加预处理时间/空间。

假设网格大小为W x H像素，则需要W x H个链表指针加上N x L个指针（对于平均长度为L像素的N条折线，而不是顶点数）。第一项随分辨率的平方增长，而第二项仅线性增长。预处理时间与此数据结构的大小成正比（W x H用于初始化列表，N x L用于Bresenham线绘制）。

查询大约需要L' x K的时间，其中L'是查询折线的长度，K是找到的重叠折线数（如果K >> 1，则使用高效的字典结构来记录K个候选人）。这与分辨率成比例。

附注：如果所选分辨率使您可以假设每个像素最多只有一条折线（这是一个近似值），则算法简化为：在不同颜色中绘制整个地图中的每条折线；然后绘制查询折线并记录您穿过的颜色。这正是您所描绘的！

- user1196549

Answer 3

首先只考虑线的边界框 - 因此从(x1,y1)->(x2,y2)到线变成一个矩形(x1,y1,x2,y2)。使用二维区间树或线段树可以在O(log n)时间内查找一个边界框与其他边界框之间的重叠。然后，您可以迭代这些潜在匹配项以检查线是否真正相交。对于具有少量重叠边界框的数据集，总时间复杂度大约为O(n log n)。

有一个stackoverflow帖子描述了如何测试两条线是否相交。

- Isaac Turner