半径の地理的な障害物検索

Question

私はここに新しいとポイントが悪いので、私は50ポイントの賞金を提供することができます。

特定の場所の半径10マイル以内にあるすべてのガソリンスタンドを検索するアプリケーションがあるとします。しかし、この場所の片側は、周りを回るために50マイル走行する必要のある山脈に囲まれています。あなたは山の向こう側から結果を返すことを望んでいません。このような問題に対処するための良いアルゴリズム/テクニックは何ですか？ポイントツーポイント検索ではパスコストを使用することができますが、半径検索でどのような手法が使用されているのかわかりません。ここ

例である：

赤線は、41から40、-74から半径円上の和音である-72緯度長い（正確ではないだけ言う）40でユーザ、-73はコネチカット州のLIサウンドの領域を網羅しているものの地理的半径の検索を実行しますが、これは実現不可能です。アルゴリズムは、探索円と完全に交差するコードが存在し、そのコードの反対側にある結果を戻さないことを知るべきである。緑色の部分の点だけが返されます。

これは、プログラマーがこれらの境界線を定義している場合、道路ネットワーク解析なしで実行できるはずです。例えば、通過するのが危険な地域があるかもしれませんし、そのエリアの両側の人がその側に制限されることを望むでしょう。国際的な国境など。人々がこれをやっていると確信しているので、私はこれを求めているだけです。

Answer 1

たとえば、ArcGISのNetwork Analystなどを使用して、道路ネットワークに沿った距離を計算するのが最適な解決策ですが、汚れたハックは、半径の中心と各点の間に直線を作成することですその後、そのプロファイルに沿った全高度ゲインを計算します（これを行うスクリプトは自動的にhereとなります）。あなたは、一定の値よりも高い隆起の高さを持つ人を拒否するための閾値を設定することができます（到達するために山を渡る必要があるもの）。

編集ネットワーク解析を使用しないように設定されているように見えるので、その地形を通過するのが難しいラスタコストマップを作成してみませんか？それは他のデータ（水域、標高、土地被覆など）に基づいている可能性があります。次に、最もコストの低いステーションを返すか、コストマップを使用して属性を選択します。

もう1つの選択肢は、通過可能なゾーン（山、水域など）を示すポリゴンベクトルレイヤを作成することです。あなたの場所と半径内のすべての駅との間に線を作成します。場所による選択を使用すると、その線が通過できないポリゴンと交差するかどうかを見ることができます。そうであれば、ステーションの選択を解除します。

タスクに最適なツールが分析し、ネットワークはまだです...

Answer 2

それから手段をごメトリック、どのような「近く」に変更する必要があります。あなたの例では、10マイルの近くの牧場は10マイルのビーラインです。ただし、最短の道路が10マイル以上離れていないガソリンスタンドを検索したい場合もあります。

両方のアプローチを組み合わせて、最初に周囲のすべてのポイントを照会し、それらをフィルタリングすること、つまりルートの長さを計算することもできます。

アルゴリズムにもっと興味があるなら、ナビゲーションアシスタントに使用される経路探索アルゴリズムを調べることをお勧めします。

Answer 3

あなたが求めるものに近いかもしれない解決策は、エリア内のすべてのガソリンスタンドの場所を取得し、円とあなたの排他ゾーンの境界線の交差点を追加してから、結果セットのノード次元空間。特定の地域内のガソリンスタンドを見つけることは、セット内のエントリーがソートされていることを考えると、与えられた範囲内にある値のセットを返すだけで簡単です。

詳細については、Steven Skienn'a "Algorithm Design Manual"の章5.10.1と15.2を参照してください。 Boostグラフライブラリは、トポロジカルソートアルゴリズムの実装を提供します。

これは厳密にグラフの問題だと私は思っています。「10マイル半径」はアルゴリズムがマッチを見つけるのに使うのではなくむしろ道路距離です。良いソリューションには、道路、片道などの速度制限などの要因も含まれていなければならず、ユーザーは最高のマッチングのためにインコスト機能を組み込むことができます。