26

グリッド上の各スポットが x 個のオブジェクト (x >=0) を持つ 2D グリッドがあるとします。ユーザーが座標を指定すると、アルゴリズムがオブジェクトを含む最も近い座標 (指定されたものを含む) を見つけるように、きれいなアルゴリズムを考えるのに苦労しています。

簡単にするために、2 つの座標が同じ距離にある場合、最初の座標が返されると仮定します (または、アルゴリズムがこのように機能しない場合は、最後の座標は問題ではありません)。

編集: 1 離れた座標は、1 上、下、左、右のいずれかでなければなりません。斜めに離れた座標は2です。

余談ですが、アルゴリズムに関する優れた無料のオンライン リファレンスは何ですか?

4

5 に答える 5

18

アップデート

新しい情報:

対角線上の座標が2つ離れていると仮定すると

このアルゴリズムは機能します。アルゴリズムは、内側から開始された各「リング」の各ポイントをテストする、らせん状の方法で外側に検索します。

範囲外の状況は処理されないことに注意してください。したがって、ニーズに合わせてこれを変更する必要があります。

int xs, ys; // Start coordinates

// Check point (xs, ys)

for (int d = 1; d<maxDistance; d++)
{
    for (int i = 0; i < d + 1; i++)
    {
        int x1 = xs - d + i;
        int y1 = ys - i;

        // Check point (x1, y1)

        int x2 = xs + d - i;
        int y2 = ys + i;

        // Check point (x2, y2)
    }


    for (int i = 1; i < d; i++)
    {
        int x1 = xs - i;
        int y1 = ys + d - i;

        // Check point (x1, y1)

        int x2 = xs + i;
        int y2 = ys - d + i;

        // Check point (x2, y2)
    }
}

古いバージョン

2D グリッドで (0, 0) と (1, 0) の間の距離が (0, 0) と (1, 1) と同じであると仮定します。このアルゴリズムは機能します。アルゴリズムは、内側から開始された各「リング」の各ポイントをテストする、らせん状の方法で外側に検索します。

範囲外の状況は処理されないことに注意してください。したがって、ニーズに合わせてこれを変更する必要があります。

int xs, ys; // Start coordinates

if (CheckPoint(xs, ys) == true)
{
    return (xs, ys);
}

for (int d = 0; d<maxDistance; d++)
{
    for (int x = xs-d; x < xs+d+1; x++)
    {
        // Point to check: (x, ys - d) and (x, ys + d) 
        if (CheckPoint(x, ys - d) == true)
        {
            return (x, ys - d);
        }

        if (CheckPoint(x, ys + d) == true)
        {
            return (x, ys - d);
        }
    }

    for (int y = ys-d+1; y < ys+d; y++)
    {
        // Point to check = (xs - d, y) and (xs + d, y) 
        if (CheckPoint(x, ys - d) == true)
        {
            return (xs - d, y);
        }

        if (CheckPoint(x, ys + d) == true)
        {
            return (xs - d, y);
        }
    }
}
于 2010-07-25T17:36:14.500 に答える
13

オブジェクトのリストがある場合

リスト内のすべてのオブジェクトのすべての位置がある場合、すべての空の正方形を検索する必要がなく、2D距離計算を実行して最も近い正方形を決定できるため、これははるかに簡単です。オブジェクトのリストをループして、次のように距離を計算します。

Define your two points. Point 1 at (x1, y1) and Point 2 at (x2, y2).

    xd = x2-x1
    yd = y2-y1
    Distance = SquareRoot(xd*xd + yd*yd)

次に、距離が最も短いものを選択します。

2Dアレイしかない場合

ただし、説明した問題が、最初にすべてのオブジェクトを検索しないとオブジェクトの場所を一覧表示できない2D配列を想定している場合は、スパイラルループを実行する必要があります。

「スパイラル検索方法」を検索すると、いくつかの興味深いリンクが表示されます。 配列の周りでスパイラルループを実行するコードを次に示します。ただし、これは任意のポイントからは機能せず、外側に向かってスパイラルしますが、目的を達成するための優れたアイデアが得られるはずです。

これは、2D配列でスパイラル順序で値を入力することについての同様の質問です。

とにかく、これが私が問題に取り組む方法です：

与えられた点Pで、の周りの領域を指定するベクトルペアを作成しますP。

したがって、もしP = 4,4 あなたのベクトルペアは3,3|5,5

それらの境界で各値をループします。

for x = 3 to 5
    for y = 3 to 5
        check(x,y)
    next
next

値が見つかった場合は、終了します。そうでない場合は、境界をもう一度1つ増やします。したがって、この場合、2,2|6,6に移動します

ループして値をチェックするときは、負のインデックスが作成されていないことを確認し、配列のサイズを超えていないことも確認してください。

また、境界をn回拡張する場合は、外側の境界値をループするだけでよく、内側の値を再チェックする必要はありません。

どちらの方法が速いですか？

それはすべて以下に依存します：

  • アレイの密度
  • 配布手法
  • オブジェクトの数

アレイの密度

2つのオブジェクトを含む500x500の配列がある場合、リストをループすると、スパイラルを実行するよりも常にパフォーマンスが向上します。

配布手法

分散のパターンがある場合（つまり、オブジェクトが互いにクラスター化する傾向がある場合）、スパイラルのパフォーマンスが向上する可能性があります。

オブジェクトの数

リスト手法ではすべての距離をチェックして計算する必要があるため、100万個のオブジェクトがある場合、スパイラルのパフォーマンスはおそらく速くなります。

リストソリューションは毎回すべてのオブジェクトをチェックする必要があるという事実と比較して、スペースが埋められる確率を計算することにより、最速のソリューションを計算できるはずです。

ただし、リスト手法を使用すると、パフォーマンスを向上させるためにスマートな並べ替えを実行できる場合があります。おそらく調べる価値があります。

于 2010-07-25T17:21:56.197 に答える
5

オブジェクトが密集している場合は、近くのポイントを検索するだけで、中心かららせん状に広がる最も近いオブジェクトを見つけることができます。オブジェクトがまばらな場合は、クアッドツリーまたは関連するデータ構造（Rツリーなど）の方がおそらく優れています。これが例のある記事です。

優れたオンラインアルゴリズムリファレンスはわかりませんが、たまに1行以上のコードを作成する場合は、ペニーを節約してCLRSを購入する価値があります。この本に基づいて、Peteris Kruminsによって入念に注釈が付けられた講義がオンラインにありますが、それらは本の一部しかカバーしていません。これはあなたが所有する必要がある数少ない本の1つです。

于 2010-07-25T17:27:38.153 に答える
3

次の簡単な解決策は、グリッドセルごとに追加情報を格納する余裕があり、グリッドに新しいオブジェクトを追加するための時間コストが比較的高くなることが許容されることを前提としています。

アイデアは、すべてのセルが最も近い占有セルへの参照を保持しているため、O（1）クエリ時間を許可するというものです。オブジェクトが位置（i、j）に追加されるたびに、サイズが大きくなるリングをカバーして、周囲のセルのスキャンを実行します。スキャンされるセルごとに、現在最も近い占有セル参照を評価し、必要に応じて交換します。スキャンされている最後のリングがまったく変更されていない場合、プロセスは終了します。最悪の場合、プロセスはすべてのグリッドセルをスキャンしますが、グリッドが十分に密になると、最終的にはより良くなります。

このソリューションは実装が簡単で、（グリッドがメモリ内でどのように編成されているかによって）かなりのスペースオーバーヘッドが発生する可能性がありますが、最適なクエリ時間を提供します。

于 2010-07-25T17:54:34.367 に答える