サンガブリエル山脈の到達困難地点

ディマ・コーガン タグアーカイブ RSS Github ホーム / Notes /2015 /05 /サンガブリエル山脈の到達困難地点 更新情報 最も遠い地点を訪れ、登録簿を設置しました: https://eispiraten.com/viewtopic.php?t=7040。ぜひ訪れて署名してください！また、米国本土全体についても同様の分析を行いました。 友人とハイキングに出かけた際、サンガブリエル山脈で最も到達困難な地点はどこか、という疑問が持ち上がりました。「到達困難」とは、近くに道路やトレイルがあることと定義しました。この疑問に答えることにしました。結果のコードは新しいリポジトリにあります: https://github.com/dkogan/inaccessibility。これは「到達困難地点」（Pole of Inaccessibility）と呼ばれます。これは、特定のオブジェクトのセットから最も遠い地点のことです。このような地点は、地球上で最も陸地に囲まれた場所や、陸地から最も遠い場所として知られています。ここではサンガブリエル山脈に限定し、道路やトレイルから離れるように努めます。 アプローチ 入力データ処理 OpenStreetMapは私が使用できるオープンデータを提供しています。これが入力データセットです。2次元ジオメトリの場合、到達困難地点を計算する最良のアプローチは、回避したいジオメトリのボロノイ図を構築し、最も遠い地点に対応するボロノイ頂点を見つけることのようです。私たちの世界は2次元ではありません。むしろ、楕円体の上に様々な標高があります。ここでの大きな目的は、健脚な人々が訪れることができる場所を計算し、それを皆に伝えることなので、極端な精度は必要ありません。したがって、世界は局所的に平坦であると仮定し、ボロノイ図ベースの方法を使用すれば十分であると主張します。そこで、クエリ領域を最もよく表す平面を構築し、すべての入力点をこの平面に投影します。クエリ領域の中心で地球の表面に接する平面を使用します。これは、例えば海のような大きなものの到達困難地点を見つけようとする場合には機能しませんが、ここでは機能します。接平面を計算するために、地球は球形であると仮定します。接点から接平面に沿って離れるにつれて、標高誤差が増加します: E = sqrt(Rearth^2 + d^2) - Rearth サンガブリエル山脈は約80kmの広がりがあり、接平面はその中央にあるため、最悪の場合 d = 40km で誤差は約125mです。これは十分すぎるほど良いです。 プロット（出典）: 地球の楕円体形状は完全に無視します。地形も無視します。なぜなら、距離測定に地形を含めると、ボロノイ図を作成するよりも高度なアルゴリズムが必要になり、「到達困難性」の概念が曖昧になるからです。 到達困難地点の計算 最も基本的なボロノイアルゴリズムを使用したいので、入力を点のみのセットとして表します。合理的な精度を得るために、各道路を100mごとにサンプリングします。これで2次元の十分密な点のセットが得られたので、ボロノイ図を構築します。制約がない場合、最も遠い点は片側に無限に遠くなるため、一般的に解を点の凸包内に制約します。これは、到達困難地点がボロノイ頂点上にあるか、ボロノイ辺と点の凸包の交点にあることを意味します。私の場合は、一般的にクエリ領域の端の内側よりも道路が多い（平地よりも山の中に物が少ない）ため、到達困難地点が凸包上にない単純に仮定します。これにより、クエリ領域外にあるすべてのボロノイ頂点を単純に無視するため、実装が簡素化されます。したがって、すべてのボロノイ頂点を調べる必要があり、各頂点と隣接する入力点との距離をチェックし、最も大きい距離を持つ頂点を返します。 実装 プロセスの各ステップは独自のプログラムにあります。これにより、実装が簡素化され、各部分を個別に作業することが容易になります。 データインポート まずOSMをクエリします。これはquery.shスクリプトで行われます。クエリ領域の角を取り、クエリを構築し、サーバーに送信し、結果を保存します。query.shは4つの引数（lat0、lon0、lat1、lon1）を取り、その出力をquery_$lat0_$lon0_$lat1_$lon1.jsonというファイルに保存します。クエリはOSM Overpassクエリ言語を使用します。デフォルトでは、すべての道路、トレイル（highwayタグが付いたすべて）を単純に調べます: [out:json]; way [