googlemapのようなアプリケーションのデータ構造ですか？

Question

私は地図を描くアプリケーションをやっています。何人かの人が私に地図を分割したデータ構造を教えてくれたことを私は示唆しています。理論的には本当にいいと思うが、実装したときのパフォーマンスが悪いため、私は確信していない。

最悪の場合、すべての道路を描画する必要があります。マップをグリッドで分割すると、グリッド内のすべてのセルの道路の合計は、リストにすべての道路を配置する場合よりもはるかに大きくなります（各セルには、道路が通過する場合に実際よりも多くの道路が必要ですそれ）。

ズームインする必要がある場合は、グリッドを使用することでスマートさが見えますが、リストに保持すると、ズームする度に道路の数を減らすことができます。 今のようにリスト）それは本当に高速ではないので、私はそれをより速くするためのすべてです。しかし、実際にはグリッドで分割すると、私にとっては遅くなります。

私はどのデータ構造を使用すべきか、そして/あるいは何が間違っているのかについての示唆はありますか？

Answer 1

としてそのように完全ではありません：生活のためにこの種のソフトウェアを書き込み

What algorithms compute directions from point A to point B on a map?

誰かがそれに答えました。

も参照のレンダリングのために：

What is the best way to read, represent and render map data?

を、私はあなたが速いか、レンダリングを行うルーティングしようとしている場合、非常にわかりません！

Answer 2

あなたがすばやく移動したい場合は、主要道路とマイナー道路に道路を整理することをお勧めします。

マイナーロードのリストを使用して、最も近いメジャーロードへのルートを検索します。 主要道路を使用して目的地に近づけます。 その後、小道に戻り、ルートを完成させます。

このような分割がなければ、検索する道路がたくさんあります。そのほとんどはかなり遅いルートです。

Answer 3

Googleでは、画面を更新するたびに道路を描画しません。彼らは地図の予め描画されたタイルを使用しました。彼らは必要に応じてそれらを再描画することができます。例えば地図更新があるとき。彼らはさらに透明なオーバーレイ、タイルのスタックを使用して、詳細のレイヤーを追加したり削除したりします。

非常に巧妙ですが、非常に簡単です。

openlayers javascript libraryをご覧ください。無料で、あなたがマップで行う必要があるものだけを行うことができます。

Maptraction JSも利用可能である - の関連情報については、この質問を参照してくださいOpenLayersを

Answer 4

グリッドを空間データ構造として使用すると、マップが対数的に分解されるため、四分木になる可能性があります。そして、ソースを勉強することから、私の推測は、Googleが（それとも）類似のデータ構造を使用するということです。

方向を取得する場合は、最初に方向を近似してプロセスをスピードアップするために階層的な経路探索を調べることをお勧めします。一般的な経路探索アルゴリズムは、その複雑さのレベルではかなり遅くなる傾向があります。