c++ - 有效地查找位于圆内的数组的索引

Question

我会提前告诉你我开始学习编程了。

问题如下:

我有一个长度为 N 的数组，我想找到位于以一个索引为中心的半径 R 的圆内的所有索引，比如第 j 个。

我有一个想法，但它可能效率很低。

我会使用以下方法将 [0,N-1] 中的第 k 个索引转换为笛卡尔坐标:

        int x = k / side;               

        int y= k % side;

其中side为sqrt(N)，检验是否满足圆的方程:

         (x_xC)*(x-xC)+ (y_yC)*(y-yC)<=R*R

其中 (xC, yC) 是第 j 个元素的坐标。如果是，我将存储与 (x, y) 关联的索引，或者对下一个元素再次执行此操作，直到我覆盖整个数组。

这是个好主意还是对于非常大的数组来说效率太低了？

Answer 1

有一种方法不是遍历整个数组，而是只遍历圆圈中的元素:

1. 计算xC 和yC。

2. 让 y 从 yC-R 循环到 yC+R(在数组边界处适当裁剪，并适当如果 R 不是整数，则四舍五入)。

3. 对于每个这样的 y，让 r=sqrt(R*R-(y-yC)*(y-yC)) 并让 x 从 xC-r 循环到 xC+r 并进行适当的舍入(并且再次在数组边界处进行适当的裁剪)。

4. 将 x 和 y 转换回数组索引。