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

Question

我有一组多段线(以上千为单位进行编号，每条多段线大约有200-300个顶点)。它们表示地图上的路由(如果有帮助，都取自Google Maps API )。顶点是纬度/经度坐标。

现在我得到了一个查询折线，我必须找到查询折线与任何现有折线的“重叠”。因此，结果本身将是折线，按从最大到最小重叠的顺序排序。我只需要前100个结果。另一个问题是重叠不需要精确，但可以是近似的(即，被认为重叠的线段的一部分不需要相互重叠，而只需要彼此“接近”)。

具体来说，在下图的左侧，蓝色多段线(多段线A)是数据库中的多段线，红色多段线(多段线B)是查询多段线。算法应确定以粗黑色标记的多段线，如右图所示。

​

​

我目前倾向于使用空间数据库(正在考虑的选项是PostgreSQL + PostGIS)，但我不确定延迟是否可以接受-查询需要几乎即时地返回结果。无可否认，我的计算几何学很弱，但我想知道:是否有任何现有的算法或方法可以证明对解决这个特定问题有用？

首先要感谢大家！

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文件的数据库查找。

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个候选)。这与分辨率成正比。

PS:如果选择的分辨率是这样的，您可以假设每个像素不超过一条折线(这是一个近似值)，那么该算法将简化为:绘制整个地图，每条折线使用不同的颜色；然后绘制查询折线，并记下您交叉的颜色。这就是你所描绘的！

Answer 3

首先，只考虑线条的边界框--因此来自(x1,y1)->(x2,y2)的线条就变成了一个矩形(x1,y1,x2,y2)。使用二维interval tree或segment tree可以在O(log )时间内查找一个边界框与其他边界框之间的重叠。然后，您可以遍历这些潜在的匹配项，以检查这些线是否真的相交。对于几乎没有重叠边界框的所有给定数据集，总体时间复杂度大约为O(n log n)。

有一个stackoverflow帖子，很好地描述了如何test if two lines intersect