我有一組多段線（編號爲幾百個，每個多段線有大約200-300個頂點）。這些代表地圖上的路線（全部取自Google Maps API，如果有幫助的話）。頂點是緯度/經度座標。確定給定多段線與一組現有多段線的近似重疊
我現在給出了一個查詢折線，並且我必須找到查詢折線與任何現有折線的「重疊」。因此結果本身將是多段線，按照最大重疊次序排序。我只需要前100個結果左右。另一個問題是重疊不需要是精確的，但可以是近似的（即，被認爲重疊的線段的部分不必位於另一個上，而只需要彼此「接近」）。
爲了給出一個具體的表示，在下圖中的左邊部分，藍色折線（折線A）是數據庫中的折線，紅色折線（折線B）是查詢折線。該算法應確定如右圖所示以粗黑標記的折線。
我目前傾向於使用空間數據庫（所考慮的選擇是PostgreSQL的+ PostGIS的），但我不知道該延遲是可以接受的 - 查詢需要近瞬間返回結果。我的計算幾何體福雖然很弱，但我想知道：是否有任何現有的算法或方法可能證明對解決這個特定問題有用？
非常感謝提前！
快速近似查詢，你不需要找到所有匹配的氣味，如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文件進行整齊轉換的優點。
首先只考慮行的邊界框 - 所以從(x1,y1)->(x2,y2)開始的行變爲矩形(x1,y1,x2,y2)。使用二維interval tree或segment tree可以在O（log n）時間內查找一個邊界框與其他邊界框之間的重疊。然後你可以迭代這些潛在的匹配來檢查這些線是否真的相交。對於幾乎沒有重疊邊界框的數據集，所有行的總時間複雜度將大致爲O（n log n）。
有一個計算器用後如何test if two lines intersect
由於大尺寸的問題一個很好的說明，我建議你開始與網格化方法。我的意思是在地圖上疊加一個正方形網格，並且爲每個拼貼（讓我們稱它們爲像素）保留一個跨越它的多段線列表。在某種程度上，這相當於使用Bresenham算法或變體對地圖執行光柵掃描轉換。
同樣，您可以繪製查詢多段線並收集與前者共享一個或多個像素的所有多段線。您可以保留常用像素的數量以獲得重疊長度的第一個估計值。繪製一條「粗線」以吸收由於離散化造成的不準確性是明智的。
第一次通過篩選後，需要考慮的折線數量會大大減少，因此任何暴力方法都可用於重疊評估。
一個關鍵問題是網格分辨率。太粗會導致候選拒絕效率低下。太細將以不可接受的方式增加預處理時間/空間。假設網格大小爲W x H像素，則需要W x H鏈接列表指針加N x L個指針（對於平均長度爲L的N條多邊形，以像素爲單位 - 不在頂點數中）。第一項作爲分辨率的平方增長，而第二項僅線性增長。預處理時間與此數據結構的大小呈線性關係（W x H初始化列表，Bresenham線條圖的N x L）。
查詢的費用大概爲L'x K，其中L'是查詢折線的長度，K是找到的重疊多段線的數目（在K >> 1的情況下，使用有效的字典結構來記帳K候選人）。這與分辨率成正比。 PS：如果選擇的分辨率是每個像素不超過一條折線（這是一個近似值），那麼該算法簡化爲：繪製整個地圖，每條不同顏色的多段線;然後繪製查詢折線並記下您穿過的顏色。這正是你勾勒出來的！
相關：http://gis.stackexchange.com/q/59729/16594 –