查找二维空间中圆内的所有点

我表示我的 2D 空间（考虑一个窗口），其中每个像素显示为 2D 数组中的一个单元格。即 100x100 的窗口由相同维度的数组表示。

现在给定窗口中的一个点，如果我画一个半径的圆r，我想找到该圆圈中的所有点。

我想我应该检查半径周围方形区域中的每个点，side = 2*r，如果它位于圆圈内或不在圆圈内。也许我会使用正常距离公式？

因此，也许有以下几点：

for (x=center-radius ; x<center+radius ; x++){
    for (y=center-radius ; y<center+radius; y++) {
        if (inside) {
            // Do something
        }
    }
}

它能达到我的目的吗？我可以让它更快吗？

它能达到我的目的吗？

对于你的 100x100，是的。

我可以让它更快吗？

是的。例如，您可以：

• 由于对称性，仅检查 1 个象限并获取其他点。
• 计算距离时跳过平方根。

Code:

for (x = xCenter - radius ; x <= xCenter; x++)
{
    for (y = yCenter - radius ; y <= yCenter; y++)
    {
        // we don't have to take the square root, it's slow
        if ((x - xCenter)*(x - xCenter) + (y - yCenter)*(y - yCenter) <= r*r) 
        {
            xSym = xCenter - (x - xCenter);
            ySym = yCenter - (y - yCenter);
            // (x, y), (x, ySym), (xSym , y), (xSym, ySym) are in the circle
        }
    }
}

这大约是 4 倍的速度提升。

JS tests http://jsperf.com/point-in-circle/2了解此处介绍的解决方案。对称是我的计算机上最快的。三角学由黑暗阿卜索尔尼特呈现 https://stackoverflow.com/questions/15856411/finding-all-the-points-within-a-circle-in-2d-space#answer-15856534非常聪明，但它涉及昂贵的数学函数，例如sin and acos，这会对性能产生负面影响。