-1

我有一个数学难题/问题

在 3 x 3 网格的情况下,如果我们连接两个相邻单元格内的两个随机点,我如何确定哪些线将与中心单元格相交。邻居由 (grid_size - 1) / 2 = 1 定义,其中网格大小为 3 或 sqrt(单元格数)。例如,单元格 1 和 3 是相邻单元格,这条线将与中心单元格相交。单元格 0 和 8 不是因为距离 2 个单元格。

因此,在 3 x 3 的情况下,以下单元格的点之间绘制的线将与中心单元格相交:1-3、1-5、7-3、7-5

3 x 3 网格

现在有了 5x5 网格,事情变得更加复杂。由于 (grid_size - 1) / 2 = 2 其中网格大小为 5 或 sqrt(单元格数),邻居被认为距离中心单元格 2 步。以下单元格的线将与中心单元格相交:

2-11, 2-13, 7-10, 7-11, 7-13, 7-14, 17-10, 17-11, 17-13, 17-14, 22,11, 22-13, 6- 13、6-17、6-18、7-16、7-17、7-18、8-11、8-16、8-17、11-13、11-18、16-13、1-13、 3-11、5-17、7-15、7-19、9-17、11-23、13-21

5 x 5 网格

编辑澄清:

在一个单元格中时,我正在从当前单元格中的一个点到周围 5 x 5 网格(粉红色)的相邻单元格中的点绘制线条。在单元格中,我还需要考虑在相邻单元格(绿色)之间绘制的任何相交线。

在此处输入图像描述

我可以在一个单元格(灰色)中迭代所有单元格和行,但这将是低效的。

在此处输入图像描述

理想情况下,我只会绘制/计算可能与单元格相交的线。

片段着色器的一部分:

#define C 25 // cells in 5x5 grid
#define T 2  // shift size sqrt(C)-1
#define X 12 // center cell (C-1)/2
#define NP (2,11, 2,13, 7,10, 7,11, 7,13, 7,14, 17,10, 17,11, 17,13, 17,14, 22,11, 22,13, 6,13, 6,17, 6,18, 7,16, 7,17, 7,18, 8,11, 8,16, 8,17, 11,13, 11,18, 16,13, 1,13, 3,11, 5,17, 7,15, 7,19,  9,17, 11,23, 13,21)

// Cells
vec2 id = floor(st)+n;
st = fract(st)-.5;
vec2 p[C];
int i=0;
for(float y=-T; y<=T; y++) {
    for(float x=-T; x<=T; x++) {
        p[i++] = GetPos(id, vec2(x,y));
    }
}

// Lines
const int[] np = int[]NP;
for(int i=0; i<(C+np.length()); i++) {
    // draw grid center to neigboring cells
    if( i < C){
        m += line(p[X], p[i], st);
    // intersecting lines
    }else{
        int e = (i - C) * 2;
        m += line(p[np[e]], p[np[e+1]], st);
    }

}
4

1 回答 1

1

只是一个快速的想法:如果你的两个点的 x 坐标都位于中心正方形的左侧,那么这条线不会与它相交。如果两个 x 坐标都位于右侧,它们也不在右侧,如果两个 y 坐标都位于顶部上方或底部下方,它们也不位于右侧。在所有其他情况下,它们相交 (?)。

于 2019-06-21T14:16:26.950 回答