1人月のルートを検索

かつて、このプロジェクトでは、ルートをレイアウトする機能が必要でした。 多くのプログラマーはいませんが、その反対です。既成のソリューションを探していましたが、検索して良いものは見つかりませんでした。

道路グラフのデータはありましたが、ライブラリやミドルウェアに提出するのはそれほど簡単ではありませんでした。 率直に言って、ミドルウェアナビゲーションも見つかりませんでした。そのため、単にシステムに統合されました（誰か、どこを見ればいいか教えてくれてありがとう）。 そのため、既存のライブラリを最大限に使用して、すべて自分で行うことにしました。



サービスの開発プロセスについて説明します。

グラフについて。

データに関するいくつかの言葉。 サードパーティのプロバイダーからデータを受け取ります;データの形式と構成に影響を与えることはできません。 道路データは、ArcView（Shapefile）形式のファイルの形式です。 すべての道路は交差点から交差点までのセグメントに分割され、属性は各セグメントに関連付けられます。
-一意のセグメント識別子
-道路の一部を描いた幾何学的な破線
-交通ルールの許容最大速度に関するデータ
-セグメントの最初と最後の反転の可能性に関するデータ
-セグメント上の一方通行の標識
-Zは、セグメントの開始と終了のレベルです（たとえば、陸橋への入り口は、開始レベル0と終了レベル1にあります）

さらに、ロジックやトラフィックルールによって移動制限が課された別のファイルがあります。 各制限は、順次移動が禁止されている（最初のファイルからの）道路セグメントを参照する識別子のベクトルです。

それがすべてどのように見えるかの例は、投稿のタイトルにぶら下がっています（赤-禁止、残念なことに、この場合のソフトウェアでは、方向を指定して禁止を描画することはできません）。

アルゴリズムがグラフで機能するには、グラフが一般に受け入れられている形式、たとえば、接続された頂点のリストや接続性のマトリックスの形式で表示されることが必要です。 つまり、頂点のデータとそれらの間の関係が実際に必要です。 データ内の頂点に関する情報は非常に不完全であるため、それらの幾何学的位置に関するデータのみがあり、すべての頂点が一意の識別子を取得するように処理する必要がありました。

頂点の幾何学的位置を基準として取りましたが、1つの状況がありました：セグメントの終了頂点の座標は、たとえば交差点で常に100％一致するわけではありません（GISシステムオペレーターの作業に欠陥があるかもしれませんが、確かではありません）。 したがって、グラフの1つの頂点として、同じZレベルを持ち、1メートル以上離れていないセグメントのすべての端点を考慮することにしました。

データには約140,000の道路道路ネットワークのセグメントがあり、これは約280,000のエンドポイントを意味します。したがって、各ポイントから最大1メートルの距離にあるすべての近隣を見つけるには、何らかの非正面アルゴリズムが必要です。 すべてのペアの正面疲労は2次の複雑さを持ち、過度に長く動作します。 プログラムが元のデータ表現、つまりシェイプファイル（理由：更新が簡単で、メンテナンス、ドキュメント化、独自のストレージ形式のバージョン化）で直接動作することを決定したため、効率的な頂点識別アルゴリズムが必要でした。

これを思いつきました（以下、C ++コード）：
1.グラフの端のコンテナを作成しました。

typedef size_t EdgeID; typedef size_t VertexID; struct EdgeDesc { VertexID vtxSrc, vtxDest; EdgeInfo info; }; typedef std::unordered_multimap<EdgeID, EdgeDesc> EdgeMap; 

マルチマップ。これは、グラフのセグメント/エッジに新しい識別子を導入せず、同じ識別子で前方および後方のエッジに関する情報をそれぞれ保存することを決定したためです。 私の意見ではいくつかの手順の論理を複雑にしていたので、これはおそらく正しい決定ではなかったが、最初はこれが正常であると思われた。


図1

2.座標平面は、1メートルあたりの平方メートルに分割されました（図1）。
各頂点はキーに関連付けられています：

 static_assert(sizeof(size_t) >= 8, "size_t type should be 64 bit or larger"); auto keyPartX = [this](double x) { return (size_t)(x - bound_.first.x) + 1; }; auto keyPartY = [this](double y) { return (size_t)(y - bound_.first.y) + 1; }; auto getKey = [](size_t x, size_t y) { return x << (sizeof(size_t) / 2 * 8) | y; }; auto getKeyXY = [&keyPartX, &keyPartY, &getKey](double x, double y) { return getKey(keyPartX(x), keyPartY(y)); }; 

3.ハッシュコンテナーを作成しました

 typedef size_t CellKey; typedef std::unordered_map<CellKey, std::vector<VertexID>> SPHash; 

道路ネットワークセグメントのリストを表示するとき、初期および最終頂点の識別子、エッジの識別子、および関連情報、つまり実際には隣接する頂点のリストの形式のグラフを含む要素のリストを作成します。

セクション2で計算したキーを使用して、セグメントの開始点と終了点をSPHashに追加しようとしています。 そのようなキーを持つコンテナに既にポイントがある場合、新しいポイントを追加するのではなく、既存のポイントの識別子を返します（コンテナ内の既存のポイントが追加されるポイントと同じZレベルにある場合）。
コンテナのキーに何もない場合、コンテナにポイントを入力し、追加されたポイントの識別子を返します。

真のポイント（1メートル未満の距離）は異なるキーを持つことができるため、計算されたキーだけでなく、隣接する8つのキーによってコンテナをチェックします。

 std::vector<size_t> near; size_t xPart = keyPartX(px); size_t yPart = keyPartY(py); near.clear(); merge(near, getKey(xPart, yPart)); merge(near, getKey(xPart + 1, yPart)); merge(near, getKey(xPart - 1, yPart)); merge(near, getKey(xPart, yPart + 1)); merge(near, getKey(xPart, yPart - 1)); merge(near, getKey(xPart + 1, yPart + 1)); merge(near, getKey(xPart + 1, yPart - 1)); merge(near, getKey(xPart - 1, yPart + 1)); merge(near, getKey(xPart - 1, yPart - 1)); 

merge（）は、近くのベクトル内の最も近い点の識別子をリストします。
近隣の識別子のリスト（実際には、1つの頂点にマージする候補）を受け取ったら、ポイントを比較し、それらの間の正確なユークリッド距離を計算します。 そして、指定されたものよりも小さい場合、ポイントは同じであると仮定し、1つの頂点にマージします（図では同じ色で塗りつぶされます）。getKeyキー（xPart、yPart）を使用して、セルに既にある適切な頂点の識別子を返します。
最初は、この処理には約1秒かかります。

4.その結果、特定のしきい値よりも近くにある隣接ポイントが1つの識別子を受け取ることがわかります。
これで、隣接する頂点のリストができました。 このようなリストを取得する時間の複雑さは、頂点の数に線形に依存します。これは、それぞれを正確に1回処理し、ハッシュコンテナーでの検索および挿入操作が漸近的に一定の複雑さを持つためです。

お気づきのように、ポリゴンストリートセグメントの中間頂点はグラフトポロジに影響を与えないため、中間頂点は処理しません（セグメントの中央で操作を実行することはできません。いずれにしても、これに関するデータはありません）。

ポリラインを構成するセグメントに分割し、各セグメントをエッジと見なすと、約140,000のエッジの代わりに、グラフに約600,000のエッジが既に存在することになります。パスの検索時間が大幅に増加するため、最終的にこの差を絶対値で示します。

最後の仕上げがあります。 制限、または禁止された機動。
制限により、たとえば交差点で左折するなどの操作が禁止されています。 最初は、データは順次移動が禁止されているセグメントのリストです。

例を挙げます。

図 2

赤い矢印は禁止された操作を示し、数字はセグメント識別子を示します。 実際、データでは、この禁止は{e1、e4}のように見えます。

ルートを敷設するプロセスでこの禁止の表現を使用することは非常に難しいため、禁止された操縦がグラフ内で純粋にトポロジ的に不可能であり、他のすべての許可された操縦が可能になるように、グラフをローカルに変換することにしました。

これを行うために、禁止された操作に含まれるピークを複製しました。 そして、許可された操縦を作成するような方法で、これらの複製されたピークにpeaks骨が掛けられ、禁止された操縦では、そのようなルートは単に作成できませんでした。

頂点が複製されるとき、その幾何学的位置は同じままです（図に示されている頂点v6とv5は実際には同じ場所で幾何学的であり、便宜上図の間隔が空いています）、もちろん、新しい頂点に新しい識別子が割り当てられます。

上記の禁止された左折の交差点の例で言われたことを説明します。

図3

トポロジが変更されたグラフでは、交差点で禁止されたパスに沿って左折することはできなくなりますが、許可されたすべての操作は可能です。

3つ以上のエッジからの制約は同じ原理に従って処理されますが、より多くの新しい頂点とエッジを生成します。これらの変換はグラフのサイズに影響しますが、大幅には影響しません（エッジの数が約5％増加します）。 データでは、2つのセグメントから約5000の制限があり、3つのセグメントから約400の制限があります。

以下は、3つのエッジの制約の作用下でグラフがどのように変換されるかを示しています。
それは：

図4

次のようになりました：

図5。

グラフ変換アルゴリズムの実装は、すべての作業の中で最も困難な段階になり（時間の約30％を要した）、バグが最も多かったと言わざるを得ません。 これは、あまりよく開発されていないデータストレージ構造に一部起因します。 そのため、何かが理解できないままである場合-怖くない、本当に簡単ではない、質問する、答えようとする。

ツールについて。

これで、ルートを敷設することが可能なすべての制限を考慮して、便利な形式でグラフが表示されました。 アルゴリズムとして古典的なダイクストラアルゴリズムを試すことにしました。そのアルゴリズムの実装は、boostライブラリにあります。
追加することはあまりありません。ブースト::グラフには優れたドキュメントがあり、書籍もあります。例の1つからコードを取り出し、小さな変更を加えて使用しました。

次のステップは、リクエストの処理でした。 サービスが方向を取得でき、座標で指定された開始点と終了点のみを持つことができれば便利だと判断しました。 そのため、グラフ内の開始頂点と終了頂点をすばやく見つける必要があります。これらの頂点は、対応するクエリポイントに可能な限り近い場所にあります。
そのためには、道路網上のユーザー定義のポイントに最も近い地点をすばやく見つけることが必要でした（ユーザーは、道路と道路のネットワークの外側にある地点からのルートが必要な場合があります）。

データ内の道路-道路ネットワークのセグメントは破線であるため、破線上の特定のポイントに最も近いポイントを見つける必要があります（これは、破線上にあるポイント、またはその開始または終了頂点である可能性があります）。
かなりの数の破線（140,000）ですが、すばやく調べる必要があります。 すべてのセグメントの検索が遅すぎる。 ここで、boost ::ジオメトリライブラリの新しいバージョンが助けになりました。ここでは、空間インデックス（boost ::ジオメトリ::インデックス）が、破線（ラインストリング）などのオブジェクトをサポートしてすでに登場しています。

このインデックスを使用して、最も近い候補をすばやく見つけ、その中から正確なアルゴリズムが特定のポイントに最も近いセグメントを決定します。

SHPファイルの読み取りにはGDALライブラリを使用し、地理座標系間の変換には（都市のローカルシステムで作業しますが、これは歴史的に起こりました）、proj4ライブラリを使用してユーザーがGPS（WGS84）座標を使用する方が便利です。

詳細について。

-rib骨の中央へのルート
グラフは道路網のトポロジ表現であり、ダイクストラアルゴリズムが機能するための幾何学的な詳細は重要ではないことを思い出してください。 しかし、幾何学的な側面はユーザーにとって重要です。 ダイクストラのアルゴリズムは、グラフの特定の頂点から他のすべての頂点（目的の終了頂点を含む）までの最短ルートを構築することを思い出してください。
つまり、最初の頂点を決定する必要がありますが、破線、つまり実際にはエッジ間でインデックスによる検索を実行します。 ルートのプロットに必要な（グラフ内の）頂点を理解する方法。セグメントの中間の頂点がないため、見つかったセグメントの開始頂点または終了頂点を選択する必要があることを意味します。


図6。

しかし、このような解決策は、ユーザーにとっては便利ではありません。長い高速道路で、曲がり角がありません（そして、これはよく起こります）。 ユーザーが、自分が尋ねた地点から1 km離れた地点からルートがどのように構築されたかを見るのは非常に驚くでしょう（なぜなら、最も近いセグメントには他のピークがなかったからです）。 これは悪いです。 さらに、図6（赤い破線）に示すように、セグメントの最も近い頂点を選択すると、ターゲットへのパスが長くなることがありますが、これはまったく良くありません。 そのため、グラフに頂点がより多く存在し、それらがより頻繁に配置されるという事実の外観を何らかの方法で作成する必要がありましたが、これはパス検索アルゴリズムの実行時間に影響を与えません。

利点と欠点を考慮して、いくつかのアプローチが検討されました。
1）セグメントの開始および終了の両方の頂点からの2回の検索と、セグメントの対応する終了からのユーザーのポイントからの距離に応じてより短いパスの選択。
プラス：実装が簡単
マイナス：最短パスをダブルサーチして、対応する動作時間を遅くします。

2）冗長グラフの作成：道路網のセグメントのすべての幾何学的頂点がグラフの頂点に変わります。
プラス：実装が簡単
短所：ダイクストラアルゴリズムの作業時間の大幅な増加、場合によっては問題を解決しない（長い直線道路区間）

3）要求時にグラフに一時的な頂点とエッジを追加し、ルートが見つかった後にグラフを初期状態に戻す。
プラス： 1つのルート検索で、グラフを膨らませる必要がなく、高速に動作します。
マイナス：他の方法よりも実装が難しい

3番目の方法を選択しました。 壊れたセグメント上にあるユーザーポイントに最も近い頂点と2つのエッジ（セグメントが一方向の場合、開始および終了頂点、またはそれらの1つのみに対応するセグメントの部分に対応）がグラフに一時的に追加され、これらの頂点とエッジが追加されますグラフでは、検索が実行された後、一時的な頂点とエッジがグラフから削除されます。

-ウェブ出力
実際、私たちのプログラムはネットワークではまったく機能せず、標準入力を読み取り、回答を標準出力に書き込みます。ネットワークとディスパッチのインターフェース全体は、node.js上の別個のプログラムによって作成されます。

-マルチスレッド
ここではすべてが簡単です。 プログラムは1つのスレッドで実行されます。 しかし、本当にすべてのサーバーのカーネルをロードする必要がある場合、1つのプロセスでグラフを保存するために約300 MBが必要になるため、コアごとに1つのインスタンスを実行できます（このサイズは2〜3倍削減できますが、まだこのタスクを設定していません）不要として）。 プロセスごとにリクエストを配信する方法は？ 外部ディスパッチャプログラムがあるため、リクエストの動作プロセスへの配布を処理したり、パフォーマンスなどを監視したりできます。
すべてのコアをロードするための別のオプション：C ++でのマルチスレッドプログラムの作成は、私たちにとってはより困難に思えました。 まず、C ++でネットワークコードを記述する必要があります（プロジェクトのほとんどのサーバー部分はnode.jsで記述されており、ネットワークでの作業がはるかに簡単であることがわかっていました）、または外部ディスパッチャーへのより複雑なインターフェイスを作成しますstdin / stdoutと比較して。 第二に、一時的な頂点とエッジのために読み取り専用のグラフがありません。これは、一方でパフォーマンスを犠牲にせず、他方でマルチスレッドコードの対応する問題にぶつからないように、ワークフローを非常に慎重に同期する必要があることを意味しますこの方法で（現時点で）そうする利点を見つけました。

結論として、いくつかの統計：
プログラム全体はたった1,500行であり、さらにnode.jsの数十行のディスパッチャー、1人がコーディングに従事し、約1か月かかりました+数人の同僚がアイデアとデバッグを手伝いました。 私たちには、このような最も基本的なタスクではないように思えます。

平均ルート検索時間（Core i7 3.4 Ghzで）は約60〜65ミリ秒です。 ちなみに、破損した道路セグメントの各セグメントがグラフの個別のエッジに変わるグラフ上の動作時間は約250ミリ秒であり、顕著な差があることに同意すると言います。

最後まで読んでくれた人たちに注目してくれてありがとう。