等時線をおおよその面積に変換して、ある機能の範囲を表示できるアルゴリズムが記述されているかどうか疑問に思います (私の問題では、この機能は道路網です)。
例。下の画像のようなものがあります：
Xこれは単純なネットワークです (出発点から数分またはY数キロメートルで到着できます)。すべてのノードとリンクの情報があります。次に、到達できるおおよその範囲を示す等時線マップを作成する必要があります。
問題:
Convex hull- あまりにも一般的な近似のために吸う、私が取得する必要があるのは、次のようなものです。
HEREで役立つ可能性がある情報をいくつか見つけましたが、それを行う方法についてはいくつかのアイデアしかありません。誰かにコンセプトがある場合は、私の問題を解決するのを手伝ってください。
興味深い問題です。より良い答えを得るには、範囲 (等時線マップ) を示すこの領域を何に使用するかを正確に定義する必要があります。たとえば、それは説明的ですか？必要な近似の種類を定義すると、問題の解決に役立ちます。
ここにいくつかのアイデアがあります。
1)グラフ内のすべてのサイクルを検索し(リンクを参照)、2 つのサイクル間で共有されるエッジを削除します。最後に、残りのサイクルの凸包をすべての道路と合わせて取得し、サイクルを形成しない外れ値が含まれるようにすると、等色マップの適切な近似が得られます。
2) より簡単な解決策は、すべての道路の各ポイントの周りに厚さを定義することです。この厚さは、開始点からそのポイントに到達するまでにかかる時間に反比例する必要があります。つまり、ポイントに到達するのに時間がかかるほど、厚さが薄くなります。次に、すべての全体が塗りつぶされるまですべてのポイントの厚さをスケーリングすると、おおよその等色マップが得られます。これを実装する方法の 1 つは、開始点から可能なすべてのルートを同時に取り、新しい交差点ごとに分岐するアルゴリズムを実行し、各点に到着するまでにかかった時間を追跡することです。その実行中、すべての時点で、以前に発見されたすべてのルートが太くなるはずです。最後に、すべての全体を埋めるようにこの厚さをスケーリングできます。
うまくいけば、これはいくつかの助けになるでしょう。幸運を。
私は問題を解決しました (それほど高速ではなく、堅牢ではありませんが、今のところは十分です)。
A* (A-Star) algorithmました。後で、2 種類のジオメトリを生成することにしました (1 番目 - 画像のように、2 番目 - シンプルなバッファ):
1 つ目:
3. 次に、残りの不要なポイントを を使用して削除しましたDouglas-Peucker algorithm(非常に高速です!)。
4. 最後に、私はConcave Hull algorithm(akaAlpha-ShapesまたはNon-Convex Hull) を使用しました。
2 つ目:
3. 既存のジオメトリにバッファを適用し、外部リングを取得します (JTSライブラリにより、これは非常に簡単になりました:))。