HN 日本語サマリー

← 一覧へ戻る
科学・技術

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

Poles of Inaccessibility in the San Gabriel Mountains (notes.secretsauce.net)

25 pointsby dima5520 コメント

要約

この記事は、サンガブリエル山脈における「到達困難地点」(Pole of Inaccessibility)を計算する技術的なプロセスについて解説しています。これは、道路やトレイルから最も遠い地点を特定する問題であり、OpenStreetMapのデータとボロノイ図を用いて、平面近似された地球上で計算されています。計算結果として、いくつかの異なる定義(道路、トレイル、舗装道路のみを考慮)に基づいた到達困難地点の座標と、それらが最も近い道路/トレイルからの距離が示されています。

全文翻訳

サン・ガブリエル山脈における到達困難点の極

友人とハイキングに出かけた際、サン・ガブリエル山脈で最もアクセスしにくい地点はどこか、という疑問が持ち上がりました。「アクセスしやすい」とは、近くに道路やトレイルがあることと定義しました。この疑問に答えることにしました。結果として得られたコードは、新しいリポジトリにあります: https://github.com/dkogan/inaccessibility

これは到達困難点の極と呼ばれるもので、与えられたオブジェクトの集合から最も遠い地点です。このような極の場所は、地球上で最も内陸の地点や、陸地から最も遠い場所として知られています。ここでは、サン・ガブリエル山脈に限定し、道路やトレイルから離れるように努めます。

アプローチ

入力データ処理

OpenStreetMapには、道路やトレイルをマッピングするために使用できるオープンデータがあります。これが入力データセットです。

2次元幾何学において、到達困難点の極を計算するための最良のアプローチは、回避したい幾何学のボロノイ図を構築し、最も遠い点に対応するボロノイ頂点を見つけることのようです。

私たちの世界は2次元ではありません。むしろ、楕円体の上に様々な標高が存在します。ここでの大目的は、頑健な人々が訪れることができる場所を計算し、それを皆に伝えることなので、極端な精度は必要ありません。したがって、世界は局所的に平坦であると仮定し、ボロノイ図ベースの方法を使用することが十分であると主張します。そこで、クエリ領域の中心に接する平面を構築し、すべての入力点をこの平面に投影します。これは、例えば海の到達困難点の極を見つけようとする場合には機能しませんが、ここでは機能します。

接平面を計算するために、地球は球形であると仮定します。接点から接平面に沿って移動すると、標高誤差が増加します:

E = sqrt(Rearth^2 + d^2) - Rearth

サン・ガブリエル山脈は約80kmの広がりがあり、接平面はその中央に位置するため、最悪の場合 d = 40km で誤差は約125mです。これは十分に良い精度です。プロット (ソース):

[画像: plot_flat_earth_error.svg]

地球の楕円体形状は完全に無視します。地形も無視します。なぜなら、距離測定に地形を含めると、ボロノイ図を作成するよりも高度なアルゴリズムが必要になり、「到達困難性」の概念がより曖昧になるからです。

到達困難点の極の計算

最も基本的なボロノイアルゴリズムを使用したいので、入力を点のみの集合として表現します。線分は使用しません。合理的な精度を得るために、各道路を100mごとにサンプリングするようにします。

これで2次元の十分な密度の点の集合が得られたので、ボロノイ図を構築します。制約がない場合、最も遠い点は片側に無限に遠く離れてしまいます。そのため、一般的には解が入力点の凸包内に収まるように制約を設けます。これは、到達困難点の極がボロノイ頂点にあるか、またはボロノイ辺と入力点の凸包の交点にあることを意味します。私の場合は、クエリ領域の端には内部よりも多くの道路があることが多いため(平地よりも山の中の方が少ない)、到達困難点の極が凸包上にないことを単純に仮定します。これにより、クエリ領域外にあるすべてのボロノイ頂点を単純に無視することで、実装が簡素化されます。

したがって、すべてのボロノイ頂点を調べ、それと隣接する入力点との距離を確認し、最も大きい距離を持つ頂点を返します。

実装

プロセス内の各ステップは、独自のプログラムとして存在します。これにより、実装が簡素化され、各部分を個別に作業しやすくなります。

データインポート

まずOSMからクエリします。これはquery.shスクリプトで行われます。クエリ領域の角を取り込み、クエリを構築し、サーバーに送信して結果を保存します。query.shは4つの引数(lat0, lon0, lat1, lon1)を取り、出力をquery_$lat0_$lon0_$lat1_$lon1.jsonというファイルに保存します。クエリはOSM Overpassクエリ言語を使用します。デフォルトでは、すべての道路、トレイル(highwayタグを持つすべて)を調べます:

[out:json];

way ["highway"] ($lat0,$lon0,$lat1,$lon1);

(._;>;);

out;

計算で道路のみを考慮したい場合(トレイルは許可しない)は、クエリからトレイルを除外できます:

[out:json];

way ["highway"] ["highway" != "footway" ] ["highway" != "path" ] ($lat0,$lon0,$lat1,$lon1);

(._;>;);

out;

実行例:

$ ./query.sh 34.1390884 -118.4944153 34.5020298 -117.5852966

  % Total    % Received % Xferd  Average Speed   Time    Time     Time  Current
                                 Dload  Upload   Total   Spent    Left  Speed
100 28.3M    0 28.3M    0   138  72803      0 --:--:--  0:06:48 --:--:--  138k


$ ls -lh query*

-rw-r--r-- 1 dkogan dkogan 29M May  6 04:12 query_34.1390884_-118.4944153_34.5020298_-117.5852966.json
データ整形

次に、緯度/経度ペアを取得し、接平面にマッピングして、データが十分に密であることを確認します。これはmassage_input.plスクリプトで行われます。これは、先ほど取得したquery_....jsonファイルを入力として受け取り、points_$lat0_$lon0_$lat1_$lon1.datというファイル(私の平面上の(x,y)タプルのリスト)を生成します。前述のように外れ値の頂点を拒否できるように、データの境界を表す4つの値を持つ小さなヘッダーがあります。

実行例:

$ ./massage_input.pl query_34.1390884_-118.4944153_34.5020298_-117.5852966.json


$ ls -lh points*

-rw-r--r-- 1 dkogan dkogan 4.3M May  6 04:20 points_34.1390884_-118.4944153_34.5020298_-117.5852966.dat
到達困難点の極の計算

これでボロノイ図を計算できます。boost::polygonを使用します。このステップが非常に遅くなるのではないかと懸念していましたが、アルゴリズムとこの実装は十分に高速で、「問題なく動作」します。

points_....datファイルは標準入力からの入力です。これは、コマンドラインでファイルを読む他のツールとは異なる点に注意してください。

各ボロノイ頂点について、任意の隣接エッジと任意の隣接セルを取得します。定義により、頂点とセル中心との距離は、任意のそのようなエッジに対して同じです。最も大きい距離を持つセルを追跡し、最も大きい距離を持つ頂点を到達困難点の極として報告します。

実行例:

$ ./voronoi < points_34.1390884_-118.4944153_34.5020298_-117.5852966.dat

furthest point center, surrounding points:
25541 -78
25308 4259
21223 -543
26931 -4192
distance: 4342.873206

これで完了です!到達困難点の極は、最寄りのトレイル/道路から約4.3kmの地点にあります。ここの座標は私の2次元接平面上のもので、あまり役に立ちません。これを緯度/経度に変換すれば完了です。

平面座標の逆変換

これを、以前と同様にマッサージスクリプトを使用して、コマンドラインで座標を渡すことによって行います:

$ ./massage_input.pl query_34.1390884_-118.4944153_34.5020298_-117.5852966.json 25541 -78 25308 4259 21223 -543 26931 -4192

34.3206972918426,-117.761740671673
34.3597096140465,-117.764149633831
34.3165155855012,-117.808770212857
34.2837076589351,-117.746734473897

OK。完了です。

結果

これを3回実行しました。

  • すべての道路、トレイルを回避
  • すべての道路を回避
  • すべての舗装された、走行可能な道路を回避

すべての到達困難点の極は、サン・ガブリエル川の東支流、ロス・マウンテンとアイアン・マウンテンの近くにあります:

polelat,londistance to nearest (m)
roads,trails34.3204, -117.76174343
roads only34.3108, -117.74745677
paved roads34.2992, -117.71678157

これは地図上で綺麗に示されています:

http://caltopo.com/m/4N7A

[画像: poles.png]

道路とトレイルの地点の境界となっているのは、サウス・マウント・ホーキンスへの道、マウント・バデン=パウエルの頂上にあるPCT(パシフィック・クレスト・トレイル)、そしてブリッジ・トゥ・ノーウェアのトレイルのようです。

道路のみの地点の境界となっているのは、サウス・マウント・ホーキンスへの道、キャビン・フラット・キャンプグラウンド、そしてシューメーカー・キャニオン・ロードです。