ドライバーにとって、なじみのない道路の問題はナビゲーターによって長い間解決されてきました。 しかし、運転手でさえ歩く。 店が道路の向かいにある場合は、立ち上がって行きます。 なじみのない通りを500メートル歩いて、2、3回曲がらなければならない場合に困難が生じます。
私たちに知られているどのサービスも、経路や歩道のない地点Aから地点Bへのルートを構築していませんが、フェンスや奇妙な輪郭の家でいっぱいです。
2GISはこの問題を解決しました。 ラスタライズされたエリアの地図上に歩行者用のルートを作成する方法を学びました。 マップは、歩行者が物理的に配置できる場所の規則的なグリッド上の頂点を持つグラフによって正式に表されます。
ルートを構築するこのような方法は、多くのリソースを消費するため、一般に受け入れられません。 カットの下-どのように対処したか。
アルゴリズム
歩行ルートを構築するアルゴリズムを示します。
- 2×2メートルの解像度で領域をラスタライズします。 ラスタライズには、家、道路、フェンス、貯水池、通路、渓谷が含まれます...最も単純なケースでは、各ピクセルが値を取得します-通過することは可能または不可能です。 しかし、十字架の卒業を妨げるものは何もありません：
- 速く行くことができます
- 合格できる
- 一生懸命
- 乗り越えないで
- 領域のマップは、隣接するセル間の関係が暗黙的に示されているグラフの記述と見なされます。 私たちが行ったことがない、まずまずに移行します。
- グラフを使用します。 ポイントからポイントへのパッセージを探している場合、 アルゴリズムA *のバリアントを使用します。
最も近い道路を探して、最も近い登録済みオブジェクトへの通過を決定する場合、正直なダイクストラアルゴリズムで検索波を開始します 。
このパターンで怖いのは、記憶と記憶の2つです。 操作上およびディスク上。 それとそれの両方があまりにも速く費やされます。 問題を解決してみましょう。
RAMのために戦う
各ポイントには、前方と後方の8ペアのエッジのポテンシャルがあります。 平方キロメートルの場合、500×500×8 = 2 000 000です。「額」で行動する場合、それぞれを処理して保存する必要があります...
RAMを節約するために、カードを256×256セルまたは512×512メートルのタイルに分割します。 タイルの境界に沿って通過する波の周囲のみを保存します。 境界を保存するために、共通の「 ヒープ 」を作成します 。
タイルは原子的に処理されます。 タイルを注ぐときは、ローカルの「ヒープ」を使用します。 アルゴリズムは次のとおりです。
- 開始点が位置するタイルを見つけ、このタイルのローカル「ヒープ」にポイントを挿入します。
- タイルでウェーブを開始します。 塗りつぶし時にフィニッシュラインに達した場合は、手順7に進みます。そうでない場合、波がタイル全体を塗りつぶすと、境界で開始点から長さを取得します。
- このタイルの周囲を共通の「パイル」に入れます。 タイル自体は不要になり、解放できます。
- 一般的な「ヒープ」から最小要素を取得し、この要素がどのタイルとどの側に見えるかを調べます。
- このタイルのこちら側からすべてのポイントを共通の「ヒープ」から削除し、それらを覚えています。
- 新しいタイルをダウンロードします。 右側からの彼のローカルヒープに、見つかったポイントを入力します。 再びポイント2に戻ります。
- パスが見つかったら（これは実際にはタイル間グリッド上のポイントのリストです）、タイル内の実際のパスも復元します。 これは、メモリを節約するためにタイルを長時間アンロードしたためです。 これを行うには、タイルを順番に読み込んでルートを再構築しますが、今回はタイル内のポイントからポイントへと進みます。
- 見つかったパスをまっすぐにして、特徴的な「のこぎり」を取り除きます。 この手法は、すべてのアーティファクトを除去するわけではありませんが、最も明白なアーティファクトを迅速に除去します。
このために、tile内でBresenhamアルゴリズムを使用します。 パスの断片をまっすぐにするために、断片の間に線を引き、障害物のマスクを使用してこの線が通過可能かどうかを確認します。
タイル間で、パスをまっすぐにします。 これを行うには、前のタイルの最後から2番目のポイントと現在のタイルの2番目のポイントを取得します。 格子上で、それらと交差する線がスイープする点を見つけます。 両方のタイルで、ブレゼンハムはこの境界点に直接移動しようとします。 成功したら-出来上がり！ -直接接続します。
タイル内の値の分布を見てみましょう。
色-青からオレンジまで-長さを示します
走行距離。 右上隅を離れました。
したがって、私たちは波の境界を保存するための最小限のメモリに自分自身を制限することができます。 タイルをキャッシュすることも必要ありません。 このオプションは許容できると考えており、RAMを節約するという目標は達成されています。
ディスクメモリの獲得
1つのタイルを256×256ポイントで1ポイントあたり1ビットの解像度で保存するには、8キロバイトが必要です。 それから1平方キロメートルは32キロバイトで、周囲の典型的な都市-100×100 kmはすでに320 MBの重さです。
多すぎる。 ただし、0と1の比率には大きな歪みがあるため、この種の情報は適切に圧縮する必要があります。さらに、長い単調なシーケンスがあります。
最初に、これを考慮して、適応算術エンコーダーを使用しました。 ノボシビルスクのラスタライズには約4分かかりました。 4946の空でないタイルが判明しました。これには約10 MBかかりました。 同時に、gif内の同じデータは6 MBしか占有しません（これは屈辱的です:-)。 次のようになります。
写真形式のいくつかのカスタムタイル
Novosibirskの場合、10または6 MBでも、ルーティングインデックスに必要な量を超えています。
さらに、ポイントからポイントではなく道路まで歩く場合、別のラスタが必要です-歩行者が到達できる道路があります。 これはすでに多すぎます。 別の解決策が見つかりました-「オンザフライ」でのラスタライズ。
オンザフライのラスタライズ
一見、このアプローチは追加情報を必要としません。 実際、私たちはすでに情報を持っています：家、フェンス、道路-ほんの数十層です。
ただし、各タイルをラスタライズするには、空間インデックスに対して10個の空間クエリを作成し、対応する空間レイヤーから減算する必要があります。
利用可能なメモリ上の携帯電話の制限により、データウェアハウスにはほとんどキャッシュがありません。 また、サブシステムは「エイリアン」です。これとは信頼関係がないため、CRTを介してメモリが割り当てられますが、断片化の観点からはあまり良くありません。
簡単に言えば、このオプションは高すぎます。 そこで、ラスタライズ用のデータウェアハウスを作成しました。
ジオメトリを格納するために、3つの要素（または必要に応じて2 +値）のキーを持つBツリーが使用されます。
- TileID-タイル識別子。 マップの範囲はタイルに分割され、番号付けは下から上へ左から右へ行ごとに行われます。
- Attrはオブジェクトの属性です。 最下位1ビットのみを使用します。 0-オブジェクトを1、0-でラスタライズします。
ツリーをトラバースすると、ゼロが前進し、最初にすべてのブロッキングオブジェクト（家、フェンス）を描画し、次に解決オブジェクト（ウィケット、転送）を上に適用します。 - Shp-ジオメトリ、すべてのタイプのジオメトリがまとめられています。
このような組織は、1回の検索と1回のトラバースでこのタイルのデータを見つけます。 この場合、主にスタックオブジェクトが使用されます。 追加のメモリがプールから取得されますが、これはCRTに比べて明らかに人道的です。
エクスポート段階のジオメトリは、タイルの境界に沿ってクリップされます。 ツリーを書き込むとき、データは圧縮されます。 その結果、ベクトル情報の保存は、適応算術エンコーダーと比較すると、ラスタライズの3倍、そしてgifの2倍の経済的です。
ルートの例
私たちはポイントからポイントへ行き、駅を通過します 再配置。
再びポイントからポイントへ。 都会のジャングルの歩行者道は複雑になる場合があります。
最寄りの道路に行きます。
再び最も近いrib骨に。
結果は何ですか
ノボシビルスクの追加データの量は約3 Mbです。 広大な祖国の首都は8Mbです。 デスクトップで1.5 kmを検索するには、ウォームアップせずに90ミリ秒かかります。 これらは約20個の開梱および処理されたタイルです。 通常、追加のRAMは1メガバイト未満で済みます。
しかし、このアプローチには欠点があります。 ジオメトリが「まっすぐ」になっているにもかかわらず、結果がかなり奇妙な場合があります。 たとえば、ラスター化の離散性により、建物は時々「くっついて」います。
このアルゴリズムは距離に対して2次関数であり、何も実行できません。 幸いなことに、それが問題になるとき、そのような距離で構築することは非常にまれです。 実際、徒歩距離は2キロメートルに制限されています。
それでも、これは障害物にかかわらず、最も近い道路に直接引き付けられ、都市や町を歩き回るよりも優れています。 ハイキングルートは、iOSおよびWindows Phoneのモバイルアプリケーションで、 2gis.ruの公共交通機関でルートを検索するときにすでに機能しています。