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

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. Compute xC和y从yC-R循环到yC+R (在数组边界进行适当的裁剪，并且在R不是整数的情况下进行适当的舍入)。
   1. 对于每个这样的y，让r=sqrt(R*R-(y-yC)*(y-yC))和x通过适当的舍入从xC-r循环到xC+r (并且再次在数组boundaries).
   2. Convert x和y处进行适当的裁剪)回到数组索引。<代码>H221<代码>G222