在2D空间中查找圆内的所有点

Question

我代表我的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
        }
    }
}

它会满足我的目的吗？我可以加快速度吗？

Answer 1

它会满足我的目的吗？

对于你的100x100,是的.

我可以加快速度吗？

是.例如,您可以:

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

码:

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测试此处提供的解决方案.对称性是我电脑上最快的.Niet the Dark Absol提出的三角函数非常聪明,但它涉及昂贵的数学函数,如sin和acos,它对性能有负面影响.

Answer 2

您可以绕过条件检查的需要:

for(x=center-radius; x<center+radius; x++) {
    yspan = radius*sin(acos((center-x)/radius));
    for(y=center-yspan; y<center+yspan; y++) {
        // (x,y) is inside the circle
    }
}

如果需要,你可以round(yspan).