在2D空间中查找圆内的所有点 [英] Finding all the points within a circle in 2D space

问题描述

我代表我的2D空间(考虑一个窗口)，其中每个像素都显示为2D阵列中的一个单元.即100x100的窗口由尺寸相同的数组表示.

I am representing my 2D space (consider a window), where each pixel is shown as a cell in a 2D array. i.e. a 100x100 window is represented by the array of same dimensions.

现在在窗口中给定一个点，如果我绘制一个半径为r的圆，我想找到该圆中的所有点.

Now given a point in the window, if I draw a circle of radius r, I want to find all the points lying in that circle.

我当时想用side = 2*r检查半径周围的正方形区域中的每个点是否在圆上.我会使用正常的距离公式吗?

I was thinking I'd check for the each point in the square region around the radius, with side = 2*r, if it lies in the circle or not. I'll use the normal distance formula maybe?

因此，可能是以下情况:

Hence, maybe the following:

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

这会达到我的目的吗?我可以加快速度吗?

Will it serve my purpose? Can I make it faster?

推荐答案

它会达到我的目的吗?

Will it serve my purpose?

对于您的100x100，是的.

For your 100x100, yes.

我可以加快速度吗?

Can I make it faster?

是的.例如，您可以:

• 由于对称性，仅检查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倍.

That's about 4x speed up.

JS测试，此处提供了解决方案.对称性是我计算机上最快的.三角学由尼古拉·尼·黑索尔(Niet the Dark Absol)呈现非常聪明，但是它涉及到昂贵的数学函数，例如sin和acos，这会对性能产生负面影响.

JS tests for solutions presented here. Symmetry is the fastest on my computer. Trigonometry presented by Niet the Dark Absol is very clever, but it involves expensive mathematical functions like sin and acos, which have a negative impact on performance.

这篇关于在2D空间中查找圆内的所有点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！