我在读一本书由罗伯特Sedwick算法的C ++。以下是有关的例子混合数据结构在书中给出。

问题陈述：     考虑到D，我们想知道如何从单位平方一组N个点，许多对可以通过长度的直线连接不到D。

使用逻辑继程序划分单元squre成一格，并保持链表的二维阵列，其中一个列表对应于每个网格正方形。网格被选择为足够精细该内距离的所有点D要么在同一网格正方形或相邻的一个

我的问题是

     为什么笔者分配G + 2 malloc2d（G + 2，G + 2）？   在gridinsert功能，为什么笔者正在执行以下语句INT X = X * G + 1; INT Y = Y * G + 1; ？   在循环，为什么我们有我intialiazed到X-1和J初始化为Y-1？   凡在code，我们保持点在距离d在同一方格或相邻的一个？   

请求您的帮助，简单的例子理解以下编程'。

 的#include＆LT;的iostream＆GT;
＃包括＆LT; stdlib.h中＆GT;
＃包括＆LT; stdio.h中＆GT;
＃包括＆LT;文件math.h＆GT;
使用名字空间std;


浮动randFloat（）{
    返回1.0 * RAND（）/ RAND_MAX;
}


结构myPoint {
    浮动X;
    浮动Ÿ;
};

浮动myDistance（myPoint一个，myPoint B）{
    浮DX = a.x  -  b.x，DY = a.y  -  b.y;
    返回的sqrt（DX * DX + DY * DY）;
}

结构节点{
    myPoint磷;节点*下一个;
    节点（myPoint PT，节点* T）{
        P = PT;接下来= T;
    }
};

类型定义节点*链接;
静态链接**格= NULL;

链接** malloc2d（INT R，INT C）{
    链接**吨=新链接* [R]。
    的for（int i = 0; I＆LT; R;我++）{
      T [i] =新链接[C]。
    }
    返回吨;
 }

静态INT G，CNT = 0;
静浮D组;

无效gridinsert（浮X，浮动Y）{
    INT X = X * G + 1;
    INT Y = Y * G + 1;
    myPoint磷;
    p.x = X; p.y = Y;
    链接S，T =新节点（P，电网[X] [Y]）;
    的for（int i = X-1; I＆LT; = X + 1;我++）
      对于（INT J = Y-1; J＆LT; = Y + 1; J ++）
        为（S =电网[I] [J]; S = 0;！S = S-＆gt;下面）
           如果（myDistance（仲指p，叔指p）＆其中;四）的cnt ++;

    电网[X] [Y] = T;
 }

INT主（INT ARGC，字符* argv的[]）{

    INT I;
    INT N = 10;
    D = 0.25;
    G = 1次/ d;

    格= malloc2d（G + 2，G + 2）;
    对于（i = 0; I＆LT; G + 2;我++）
        对于（INT J = 0; J＆LT; G + 2; J ++）
            电网[I] [J] = 0;

    对于（I = 0; I＆所述N;我+ +）
        gridinsert（randFloat（），randFloat（））;

    COUT＆LT;＆LT; CNT＆LT;＆LT; ＆LT内双;＆LT; D＆LT;＆LT; ENDL;

   返回0;
 }
 

解决方案

的想法是要检查网格的所有相邻小区。但是边缘细胞不具有邻道。因此，为了避免棘手的边界检查，我们通过2个额外的扩展单元格 - 前第一小区和之后最后一个。这些细胞是假的，绝不包含任何点 - 他们只是需要简化算法，并提供邻道的边缘细胞

。

（x，y） - 单元的网格包含该点的坐标（索引）。根据P.1我们要开始从细胞（1,1）放置点，而不是（0,0）。 （0,0）和任何其他边界点是假的。

由于我们检查网格的所有相邻单元格。相邻小区对（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。

我们不维护他们，只是检查任何输入点VS现有的设置和增加计数器 CNT 每次的距离相匹配的时间。保持该对的列表不要求问题状况。如果你需要保持点的列表中，您应修改 gridinsert（）和EG地方（S-指p，叔指p）一些容器中的循环，而不是增量内 CNT ++

I am reading a book by Robert Sedwick Algorithms in C++. Following is example given in book regarding compound data structures.

Problem statement: Given "d", we want to know how many pairs from a set of N points in the unit square can be connected by a straight line of length less than "d".

Following program using the logic divides the unit squre into a grid, and maintains a two dimensional array of linked lists, with one list corresponding to each grid square. The grid is chosen to be sufficiently fine that all points within distance "d" are either in the same grid square or an adjacent one.

My questions are

Why author is allocating G+2 in malloc2d(G+2, G+2) ? In gridinsert function why author is performing following statement int X = x*G+1; int Y = y*G+1; ? In for loop why we are having i intialiazed to X-1 and j initialized to Y-1? Where in code we are maintaining points within distance d in same grid square or an adjacent one?

Request your help with simple example in understanding the following progam.

#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;
 }

解决方案

The idea is to check all adjacent cells of grid. But border cells don't have adjacents. So to avoid tricky bounds checking we extend grid by 2 extra cells - before first cell and after last one. These cells are "dummy" and will never contain any points - they are required just to simplify algorithm and provide adjacents for border cells.

(X,Y) - coordinates (indexes) of cell in grid containing this point. According to p.1 we have to start placing points from cell (1,1), not (0,0). (0,0) and any other border point is dummy.

Because we check all adjacent cells of grid. Adjacent cells for (X,Y) are (X-1,Y-1), (X, Y-1), (X+1, Y-1) etc to (X+1,Y+1). That's why we have loops from X-1 to X+1 and Y-1 to Y+1.

We don't maintain them, just checking any input point vs existing set and increment counter cnt each time it matches the distance. Keeping the list of such pairs is not required by problem conditions. If you need to keep the list of points, you shall modify gridinsert() and e.g. place (s->p, t->p) to some container inside the loops instead of increment cnt++.