私はラインのセットを持っています。1 つの線は 2 つの点で定義されます。Point には (x,y) 座標があります。一部の線は、他の線と 1 つのポイントでのみ接続されています。線のセットがマップを定義します。下の画像で例を確認できます。ここで、(線の端点だけでなく) 任意の線セグメント上のあるポイントから別の線上の別のポイントに移動したいとします。
背景: あるポイントから別のポイントに移動しながら、途中で線を描画したいので、最終的に移動したパスのみが描画されます。パスのヒートマップと考えてください。どのアルゴリズムを使用しますか? 使用できるライブラリはありますか?
グラフを xy 座標を持つ線のセットとして表すことは、パス検索アルゴリズムには適していないため、線分のセットから適切なグラフを作成する必要があります。次の式を使用できると思います: http://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line http://en.wikipedia.org/wiki/Line-line_intersection 各線分について、隣接する線分を判断するため。2 本の線の各交点は、4 本または 3 本の線に変換して、終点のみで接続されるようにする必要があります。各ノードが線を表し、各エッジが線間の接続を表すグラフを作成した後、ノード (線) の任意のペア間の最短経路を見つけるためにダイクストラ アルゴリズムを使用できます: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
2 点間には複数のパスが存在する可能性があるため、この問題は決定できません。
2 点間の最短経路が必要な場合は、4 方向の計算を行う必要があります。点 A が線分 a1-a2 上にあり、点 B が線分 b1-b2 上にあると仮定します。ダイストラのアルゴリズムを使用して、次の 4 つのパスと距離を計算します。
a1 から b1
a1 から b2
a2 から b1
a2 から b2
ここで、距離 A/B を適切に加算または減算します。たとえば、パスが次のような場合:
A -> a1 -> b2 -> B
この場合、このパスの実際の距離の合計は (A から a1 まで) + (a1 から b2 まで) + (b2 から B まで) です。上記の 4 つの可能性すべてについて、この実際の距離を計算する必要があります。最小の値が最短経路です。その後、色を付けることができます。
この計算を行う公開ライブラリはありません。一度手書きで書かなければなりませんでした。