地理座標ベースの大きなデータ構造ですか？

Question

私は実際に使用する言語を気にしません。

A1 023 UBL 15.245197 104.865917 
A1 024 BUTRA 15.418278 105.596083 
A1 025 PAPRA 15.766667 107.183333 
A1 026 BATEM 15.931389 107.765556 
A1 027 DAN 16.052778 108.198333 
A1 028 BUNTA 16.833334 109.395000 
A1 029 LENKO 17.416667 110.300000 
A1 030 IKELA 18.661667 112.245000 
A1 031 IDOSI 19.000000 112.500000 
A1 032 CH 22.219542 114.030056 

最初の数は空気の経路である（これらの何百もある）：私は世界中の様々な航空座標の周り84.1kエントリの大規模なデータベースを持っている

、彼らはこのようにフォーマットされています。第2の数は、航空路のシーケンスに関して座標が保持する位置である。 3番目は修正の名前、4番目と5番目は座標そのものです。

それを説明するためのより良い方法はハイウェイです。 A1が高速道路だとしましょう。 UBL、BUTRA、PAPRAなど...すべての出口です。 023、024、025はあなたがこれらの出口に出くわす命令です（私はUBLが22回の出口の後、23回目はBUTRA、24回目はPAPRA、25なので）。

しかし、これらの出口は都市ではなく新しい高速道路につながります。例えば、UBL出口が

A1 023 UBL 15.245197 104.865917 
G473 006 UBL 15.245197 104.865917 
R470 001 UBL 15.245197 104.865917 
W1 018 UBL 15.245197 104.865917 
W4 031 UBL 15.245197 104.865917 
W5 013 UBL 15.245197 104.865917 

につながる私の究極の目標は、これらの点を使用して、これらの空気経路を使用して、2の間の都市での最短距離を見つけることです。しかし、それは私の問題ではありません。私はそれを理解することができますが、私はこの物を保持するためにどの構造を使用するか分からない。データを整理するために何らかの構造が必要であることを最初に示唆したのはプログラミング教師でした。

私は思っています。最初と最後のポイントを利用できるようにしてから、リストを検索し、そのポイントにつながるすべての可能な「高速道路」をつかみ、A *いくつかの距離制限を使用してブランチの数を制限することができます。しかし、言ったように、私はどのデータ構造を使用するのか不明確なままでした。

助けてください。

Answer 1

PM1 Quadtreeのような空間データ構造を使用する必要があります。

また、PM2 QuadtreeとPM3 Quadtreeに対して評価して、制約に適しているかどうかを確認する必要があります。