2

我正在阅读 Robert Sedwick Algorithms 的 C++ 书籍。以下是书中关于复合数据结构的示例。

问题陈述：给定“d”，我们想知道单位正方形中一组 N 个点中有多少对可以通过长度小于“d”的直线连接。

下面的程序使用逻辑将单位正方形划分为一个网格，并维护一个二维链表数组，每个网格正方形对应一个链表。选择的网格要足够精细，以使距离“d”内的所有点要么在同一个网格正方形中，要么在相邻的网格正方形中。

我的问题是

  1. 为什么作者在 malloc2d(G+2, G+2) 中分配 G+2 ？
  2. 在 gridinsert 函数中，为什么作者执行以下语句 int X = x*G+1; 整数 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) - 网格中包含该点的单元格的坐标（索引）。根据第 1 页，我们必须从单元格 (1,1) 开始放置点，而不是 (0,0)。(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)到循环内的某个容器而不是 increment cnt++。

于 2012-08-17T10:59:17.020 回答