我有一组多段线（编号为100/1000，每条多段线有大约200-300个顶点）。这些表示地图上的路线（如果有帮助的话，所有这些都来自google maps api）。顶点是经纬度坐标。
现在我给出了一个查询折线，并且我必须找到查询折线与任何现有折线的“重叠”。因此，其结果将是折线，按最大到最小重叠的顺序排序。我只需要前100个结果。另一个问题是，重叠不一定是精确的，但可以是近似的（即，被认为重叠的线段的部分不必位于另一部分上，而是只需要彼此靠近）。
要给出具体的表示，在下面图像的左侧，蓝色多段线（多段线A）是数据库中的多段线，红色多段线（多段线B）是查询多段线。算法应该确定右图中用粗黑色标记的多段线。
我目前倾向于使用空间数据库（正在考虑的选项是postgresql+postgis），但我不确定延迟是否可以接受-查询需要几乎立即返回结果。我的计算几何FU当然是弱的，但我想知道：有任何现有的算法或方法，可能证明是有用的解决这个特定的问题？
多谢提前！
最佳答案
快速近似查询，你不需要找到所有匹配的气味，比如“AA>”，我怀疑你会得到一些点击量。不久前，我对http://en.wikipedia.org/wiki/Locality-sensitive_hashing很感兴趣-我不知道它是否在实践中起作用，但在重新找到报纸的同一次搜索中，我在http://www.cs.ubc.ca/~lowe/papers/09muja.pdf找到了一个图书馆。直lsh上的wikipedia页面在底部也有指向至少一个实现的指针。lsh的优点是可以灵活地将关系数据库或dbm文件转换为数据库查找。