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

我代表我的二维空间（考虑一个窗口），其中每个像素都显示为二维数组中的单元格。 即100×100窗口由相同尺寸的阵列表示。

现在在窗口中给出一个点，如果我绘制一个半径为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，是的。

我能加快速度吗？

是。 例如，您可以：

由于对称性，只检查一个象限并得到其他点。

计算距离时跳过平方根。

码：

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提出的三角法黑暗Absol非常聪明，但它涉及昂贵的数学函数，如sin和acos ，这对性能有负面影响。

---

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

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) 。

---

您可以通过尽可能多地计算循环来获得加速。 也不需要做毕达哥拉斯定理的平方根...只是保持一切平方。 最后一次加速可以通过仅对圆的四分之一进行数学计算（因为它是对称的）......当发现匹配时，您只需为其他三个季度复制它。

radiusSquared = radius*radius;
rightEdge = centerX+radius;
bottomEdge = centerY+radius;
for(x = centerX; x <= rightEdge; x++){
    xSquared = x*x;
    for(y = centerY; y <= bottomEdge; y++){
        ySquared = y*y;
        distSquared = xSquared+ySquared;
        if(distSquared <= radiusSquared){
            // Get positions for the other quadrants.
            otherX = centerX-(x-centerX);
            otherY = centerY-(y-centerY);
            // Do something for all four quadrants.
            doSomething(x, y);
            doSomething(x, otherY);
            doSomething(otherX, y);
            doSomething(otherX, otherY);
        }
    }
}

链接地址: http://www.djcxy.com/p/84937.html

上一篇: Finding all the points within a circle in 2D space

下一篇: Uniform sampling of 2D path draped on a set of 3D data points