4

1000x1000 の領域内の 2 つの場所を決して交差しない 25 のセグメントを持つランダムなパスを生成する必要があります。これを行うのに適したアルゴリズムは何ですか?

良い結果を生成する私の最初のアイデアは、空間分割法を使用してランダムな多角形を生成し、次に片側を削除することでした。

結果は次のようになります。 出力

この方法の欠点は、始点が常に終点にかなり近いことです (最初は線で結ばれていたため)。

もう1つの欠点は、それらが多角形であるため、全体的な形状が何らかの形または歪んだ円を生成することです. らせんのように、決して生成されないパスの種類がたくさんあります。

これらのパスを生成するのに役立つアルゴリズムを知っている人はいますか?

4

2 に答える 2

2

ここにアイデアがあります（免責事項：頭のてっぺんから、テストも検証もされていません...）：

ランダムな座標を描画し、描画した順序で線を接続するように「試行」します。つまり、P1 (x1、y1)、次にP2 (x2、y2)があり、それらを接続し、次にP3 (x3、y3)を接続し、交差がない限りが作成されたら (毎回テストする必要があります)、描画と接続を続けます。最終的に、交点が生成されます - 次に、最後の点 ( Pn-1 : 新しく作成された点の前) を、交差する線を形成する 2 つの点の前の点 (これらをPi & Pi+jと呼びましょう) に接続しようとします。それは有効です (つまり、他の線と交差しません) その線を切断します ( Pi+jはPiの後に来なくなりました)、PiをPn-1に接続し、 Pi+jから再開します (点の順序でPn-1になります)。Pn-1をPiに接続することが無効な場合は、同じことを行いますが、新しく見つかった交点を使用します。

最終的に交差点を解決し、最新のポイントであるPnに接続し、通常どおり再開できます。

このアルゴリズムの明らかな欠点は、非常に危険な Big-O 時間の複雑さがあることですが、あらゆる種類のパスを生成できるはずです。

実装データ構造に関しては、双方向リンク リストが当面の候補のようです。

于 2016-04-26T20:05:53.243 に答える
1

ポイント セットを三角測量し、エッジ上を歩くことは、ポリゴン ベースのウォークが持つ「円形のような」パスの問題を回避するソリューションです。

ポイントが近すぎるランダムなポイント セットは、パスが特定のポイントで交差しているように見える可能性があるため、おそらく必要ありません。このため、ポイント セットを生成するためにポアソン ディスクサンプリング方法のようなものを使用することをお勧めします。このようなポイント セットの三角形分割により、ほぼ同じ長さのセグメント、セグメント間の角度が約 60 のランダム パスが提供されます。 ° そして明らかな交点がない。

アルゴリズム

Delaunay 三角形分割ライブラリを使用すると、アルゴリズムは次のようになります。

初期化するには、

  • ポイントセットの生成
  • 三角点セット
  • 三角形分割 ( lastVisitedVertex)からランダムな頂点を選択します。

次にループします。

  • エッジに接続されている他の頂点がまだアクセスされていない場合にのみ、最後にアクセスした頂点に接続されたランダムなエッジを選択します(このエッジは次のセグメントです)。
  • 今来たばかりの頂点を訪問済みとしてマークする
  • lastVisitedVertex= 選択したエッジの他の頂点
  • もう一度ループするか、パスの長さが目的の長さを超えた場合 (つまり > 25) は終了します。

イラスト

三角形分割されたポアソン ディスク ポイント セット上のランダム パス

[ここに画像の説明を入力

三角形分割されたランダム ポイント セット上のランダム パス ここに画像の説明を入力

コード

これは、三角測量にTinourライブラリを使用した Java の例です。三角形分割にライブラリを使用する場合、特定の頂点の接続されたエッジと、特定のエッジを構成する頂点に簡単にアクセスできるライブラリを選択することをお勧めします。

この例では、開始点として (頂点ではなく) ランダムなエッジを選びます。

ArrayList<Vertex> randomPath(List<Vertex> randomPoints, int pathLength) {

    IncrementalTin tin = new IncrementalTin(10);

    tin.add(randomPoints, null); // insert point set; points are triangulated upon insertion

    HashSet<Vertex> visitedVertices = new HashSet<>();
    ArrayList<Vertex> pathVertices = new ArrayList<>();

    IQuadEdge lastEdge = tin.getStartingEdge(); // get random edge

    int n = 0;
    while (n <= pathLength) {

        List<IQuadEdge> list = new ArrayList<>();
        lastEdge.pinwheel().forEach(list::add); // get edges connected to A; add to array
        IQuadEdge nextEdge;
        int attempts = 0;
        do {
            nextEdge = list.get(random.nextInt(list.size())); // randomly select connected edge
            if (attempts++ > list.size() * 4) {
                return pathVertices; // path ended prematurely (no possible edges to take)
            }
        } while (visitedVertices.contains(nextEdge.getB()) || nextEdge.getB() == null);

        lastEdge = nextEdge.getDual(); // A and B flip around, so A is next vertex
        pathVertices.add(lastEdge.getB()); // add the point we just came from to path
        visitedVertices.add(lastEdge.getB()); // add the point we just came from to visited vertices
        n++;
    }
    return pathVertices;
}
于 2021-02-06T14:12:32.910 に答える