グラフで最も近いエッジを見つけたい。次の例を検討してください。
図 1: 黄色:頂点、黒:エッジ、青:クエリ ポイント
一般情報: グラフには、約1,000 万の頂点と約1,500 万のエッジが含まれています。すべての頂点には座標があります。エッジは、隣接する 2 つの頂点によって定義されます。
最も簡単な解決策: クエリ ポイントからグラフ内の他のすべてのエッジまでの距離を単純に計算できますが、それは非常に遅くなります。
アイデアと難しさ: 私のアイデアは、空間インデックスを使用してクエリを高速化することでした。最も近い頂点を見つけるために、すでに kd-tree を実装しています。しかし、図 1 が示すように、最も近い頂点に付随するエッジは、必ずしもクエリ ポイントに最も近いとは限りません。より近いエッジ7-8ではなく、エッジ3-4を取得します。
質問: グラフで最も近いエッジを見つけるアルゴリズムはありますか?
非常に単純な解決策 (ただし、複雑さが最も低い解決策ではないかもしれません) は、バウンディング ボックスに基づいてすべてのエッジにクワッド ツリーを使用することです。次に、クエリ ポイントに最も近い一連のエッジを抽出し、それらを繰り返し処理して最も近いエッジを見つけます。
四分木によって返される抽出されたエッジのセットは、元の 1,500 万のエッジよりもはるかに小さいため、反復処理のコストが大幅に削減されます。
クワッド ツリーは、R ツリーよりも単純なデータ構造です。これはかなり一般的であり、多くの環境ですぐに利用できるはずです。たとえば、Java のJTS Topology SuiteQuadTreeには、このタスクを実行するために簡単にラップできる構造があります。
ボロノイ図を計算し、各ボロノイ セルに対してクエリを実行できます。ボロノイ図を細分化して、より良い結果を得ることができます。メートル法とボロノイ図を組み合わせることができます: http://www.cc.gatech.edu/~phlosoft/voronoi/