我有一组多段线(数以千计，每条多段线有大约 200-300 个顶点)。这些代表 map 上的路线(如果有帮助，全部取自 Google Maps API)。顶点是纬度/经度坐标。
我现在得到一条查询折线，我必须找到查询折线与任何现有折线的“重叠”。因此，结果本身将是多段线，按最大重叠到最小重叠的顺序排序。我只需要前 100 个左右的结果。另一个问题是重叠不需要精确，但可以是近似的(即，被视为重叠的线段部分不需要彼此重叠，而只需要彼此“接近”即可)。
具体表示，下图左侧部分，蓝色折线(折线A)为数据库中的折线，红色折线(折线B)为查询折线。该算法应确定如右图所示的粗黑色标记的折线。
我目前倾向于使用空间数据库(正在考虑的选项是 PostgreSQL + PostGIS)，但我不确定延迟是否可以接受 - 查询需要近乎即时地返回结果。我的 computational-geometry-fu 固然很薄弱，但我想知道:是否有任何现有算法或方法可能被证明对解决这个特定问题有用？
非常感谢!
最佳答案
快速近似查询，您不需要找到所有匹配项，就像 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 文件巧妙地转换为数据库查找。
关于algorithm - 确定给定折线与一组现有折线的近似重叠，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21801366/