半徑搜索中的地理障礙物

Question

我在這裏是新來的，點差，所以我只能提供50點賞金。

假設我有一個應用程序搜索某個位置10英里範圍內的所有加油站。然而，這個位置的一側被山脈圍繞着，你必須開車50英里才能到達。你不想從山的另一邊返回結果。有什麼好的算法/技巧來處理這樣的問題？我知道點對點搜索，你可以使用路徑成本，但我不知道半徑搜索技術是什麼。

下面是一個例子：

紅線是從40半徑圓，-74至41的和絃，-72 LAT長（不準確只是說）在40用戶，-73進行地理半徑搜索，其中還包括康涅狄格州LI聲音的區域，這些區域不切實際。該算法應該知道存在與搜索圈完全相交的和絃而不是在該和絃的另一側上返回結果。所以只有在綠色區域的點纔會返回。

如果程序員定義了這些邊界線，這應該可以在沒有任何道路網絡分析的情況下完成。例如，在某個國家可能會有危險的區域通過，您希望該區域任何一方的人都被限制在該區域。或國際邊界等我只是問這個，因爲我很確定人們正在這樣做。

Answer 1

雖然最好的解決方案是使用ArcGIS的Network Analyst來計算沿道路網絡的距離（而不是直線距離），但一個骯髒的黑客應該是在半徑的中心和每個中心之間創建直線然後計算沿該剖面的總高程增益（一個用於自動完成此操作的腳本將給出here）。然後，您可以設置一個閾值來拒絕總高程增量高於特定值（那些需要穿越山脈才能達到的值）的閾值。

編輯由於您似乎設置爲不使用網絡分析，爲什麼不創建一個柵格成本圖，其中的值對應於遍歷該地形的難度？這可能基於其他數據（即水體，海拔，土地覆蓋等）。然後，您可以返回成本最低的工作站或使用成本圖進行選擇屬性...

另一種選擇是創建一個多邊形矢量圖層，以顯示不可通過的區域（高山，水體等）和然後在您的位置和半徑內的所有站點之間創建一條線。使用按位置選擇您可以看到該線是否與任何不可通過的多邊形相交;如果是這樣，請取消選擇該電臺。

的仍然是網絡分析任務的最佳工具......

Answer 2

你應該改變你的指標，什麼是「近」則指。在你的例子中，10英里附近的meams直線10英里。但是，您可能更想查詢任何加油站，其中最短的街道路徑不超過10英里。

您也可以將兩種方法結合起來，首先查詢所有周圍的點，然後過濾它們，即通過計算路徑長度。

如果你更深入的算法，我建議你看看用於導航助理的尋路算法。

Answer 3

解決方案，可能更接近你問什麼是採取區域內所有加油站的位置，圈子和你的禁區邊界線之間添加交叉點，然後在2得到的節點的集執行拓撲排序維空間。在特定區域內查找加油站將如同返回一組落在給定範圍內的值一樣簡單。

請參閱在史蒂芬Skienn'a「算法設計手冊」章節5.10.1和15.2的更多細節。 Boost圖庫提供了拓撲排序算法的實現。

我仍然認爲這是嚴格意義上的圖形的問題，所以「10英里的半徑」是不是你的算法將用它來尋找匹配的東西，而是沿道路距離。良好的解決方案還應包括諸如道路限速，單向街道等因素，並允許用戶在成本功能中包含最佳匹配。