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

Question

我有一组折线(数字为100,每条折线有大约200-300个顶点).这些代表地图上的路线(如果有帮助,则全部来自Google Maps API).顶点是纬度/经度坐标.

我现在得到一个查询折线,我必须找到查询折线与任何现有折线的"重叠".因此,结果本身将是折线,按最大到最小重叠的顺序排序.我只需要前100个结果左右.另一个问题是重叠不一定是精确的,但可以是近似的(即,被认为是重叠的线段的部分不需要位于另一个上,而是仅需要彼此"接近").

为了给出具体的表示,在下图的左侧部分,蓝色折线(折线A)是数据库中的折线,红色折线(折线B)是查询折线.该算法应确定以粗黑标记的折线,如右图所示.

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

提前谢谢了!

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