2

私はC++のRobertSedwickAlgorithmsの本を読んでいます。以下は、複合データ構造に関する本に記載されている例です。

問題の説明：「d」が与えられた場合、単位正方形内のN点のセットから、「d」より短い長さの直線で接続できるペアの数を知りたいと思います。

ロジックを使用する次のプログラムは、ユニットの正方形をグリッドに分割し、リンクされたリストの2次元配列を維持し、1つのリストが各グリッドの正方形に対応します。グリッドは、距離「d」内のすべてのポイントが同じグリッドの正方形または隣接する正方形のいずれかにあるように十分に細かく選択されます。

私の質問は

  1. なぜ作者はmalloc2d（G + 2、G + 2）にG + 2を割り当てているのですか？
  2. gridinsert関数で、作成者が次のステートメントを実行している理由int X = x * G + 1; int Y = y * G + 1; ？
  3. forループでは、なぜiをX-1に初期化し、jをY-1に初期化するのですか？
  4. コードのどこで、同じグリッドの正方形または隣接するグリッドの正方形の距離d内のポイントを維持していますか？

次のプログラムを理解するための簡単な例で助けを求めてください。

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
using namespace std;


float randFloat() {
    return 1.0*rand()/RAND_MAX;
}


struct myPoint {
    float x;
    float y;
};

float myDistance(myPoint a, myPoint b) {
    float dx = a.x - b.x, dy = a.y - b.y;
    return sqrt(dx*dx + dy*dy);
}

struct node {
    myPoint p; node *next; 
    node(myPoint pt, node* t) {
        p = pt; next = t;
    }
};

typedef node *link;
static link **grid = NULL; 

link **malloc2d(int r, int c) {
    link **t = new link*[r];
    for (int i = 0; i < r; i++) {
      t[i] = new link[c];
    }
    return t;
 }

static int G, cnt = 0; 
static float d;

void gridinsert(float x, float y) {
    int X = x*G+1;
    int Y = y*G+1;
    myPoint p;
    p.x = x; p.y = y;
    link s, t = new node(p, grid[X][Y]);
    for (int i = X-1; i <= X+1; i++)
      for (int j = Y-1; j <= Y+1; j++)
        for (s = grid[i][j]; s != 0; s = s->next)
           if (myDistance(s->p, t->p) < d) cnt++; 

    grid[X][Y] = t;
 }

int main(int argc, char *argv[]) { 

    int i; 
    int N = 10;
    d = 0.25;
    G = 1/d;

    grid = malloc2d(G+2, G+2);
    for (i = 0; i < G+2; i++)
        for (int j = 0; j < G+2; j++)
            grid[i][j] = 0;

    for (i = 0; i < N; i++)
        gridinsert(randFloat(), randFloat());

    cout << cnt << " pairs within " << d << endl;

   return 0;
 }
4

1 に答える 1

5

  1. アイデアは、グリッドの隣接するすべてのセルをチェックすることです。ただし、境界セルには隣接セルがありません。したがって、トリッキーな境界チェックを回避するために、グリッドを2つの余分なセル（最初のセルの前と最後のセルの後）だけ拡張します。これらのセルは「ダミー」であり、ポイントが含まれることはありません。アルゴリズムを単純化し、境界セルに隣接するセルを提供するためだけに必要です。

  2. （X、Y）-このポイントを含むグリッド内のセルの座標（インデックス）。p.1によると、（0,0）ではなくセル（1,1）からポイントを配置し始める必要があります。（0,0）およびその他の境界点はダミーです。

  3. グリッドの隣接するすべてのセルをチェックするためです。（X、Y）の隣接セルは、（X-1、Y-1）、（X、Y-1）、（X + 1、Y-1）などから（X + 1、Y + 1）です。そのため、X-1からX + 1、Y-1からY+1のループがあります。

  4. cntそれらを維持するのではなく、距離に一致するたびに入力ポイントと既存のセットおよびインクリメントカウンターをチェックするだけです。このようなペアのリストを保持することは、問題のある状況では必要ありません。ポイントのリストを保持する必要がある場合は、増分の代わりに、ループ内のコンテナを変更gridinsert()して配置する必要があります。(s->p, t->p)cnt++

于 2012-08-17T10:59:17.020 に答える