14

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

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

4

7 回答 7

16

它会达到我的目的吗？

对于您的 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 测试此处提供的解决方案。Symmetry 在我的电脑上是最快的。Niet the Dark Absol 提出的三角函数非常聪明，但它涉及昂贵的数学函数，例如sin和acos，这会对性能产生负面影响。

于 2013-04-06T22:02:00.070 回答
6

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

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

于 2013-04-06T22:00:16.163 回答
2

您可以通过尽可能多地在循环之外进行计算来提高速度。也没有必要做毕达哥拉斯定理平方根......只要保持一切平方。最终的加速可以通过只对圆的四分之一进行数学计算来实现（因为它是对称的）......当找到匹配时，您只需将其复制到其他四分之三。

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);
        }
    }
}
于 2013-04-06T22:27:11.943 回答
1

要获取一个圆圈内所有点的列表，您应该使用：

var radius = 100, r2 = radius * radius;
var circle = [];
for (var dx = -radius; dx <= radius; dx++) {
  var h = Math.sqrt(r2 - dx * dx) | 0;
  for (var dy = -h; dy <= h; dy++) {
    circle.push([dx, dy])
  }
}

请参阅http://jsperf.com/circles/2了解此处针对其他解决方案的分析。

于 2014-11-07T13:16:57.487 回答
0

如果以下情况属实：

( ( xPos - centreX)^2 + (yPos - centreY)^2 ) <= radius^2

wherexPos和yPos是您要检查的点的坐标，则该点在您的圆内。

于 2013-04-06T21:58:51.090 回答
0

似乎是正确的。您可以通过找到 minY 然后对当前 X 执行从 -rangeY 到 +rangeY 的 DoSomething 来稍微加快速度。

for(dx=0;dx<rad; dx++)
{
  rangeY = 0;
  while (!inside(x, rangeY)) //inside == check if x*x + y*y <r*r
    rangeY++;

  for(y=center-rangeY;y<center+rangeY;y++) 
  {
    DoSomething(centerX - dx, y);
    DoSomething(centerX + dx, y);      }
}
于 2013-04-06T22:07:49.457 回答
-2

我知道这个问题有一个公认的答案，但我有一个更简单的解决方案。其他答案让我感到困惑，因为我不知道center, xcenter,ycenter是什么，并且函数背后的数学无法解释，我跋涉寻找自己的数学解决方案。

我的方程式很简单：

cx是圆心的 x 点

cy是圆心的 y 点

rad是圆的半径

我的方程/函数所做的是通过计算给定半径的每个可能点来计算点，并添加和减去 和 的偏移cx量cy。

//Creates an array filled with numbers
function range(begin, end) {
    for (var i = begin, arr = []; i < end; i++) {
      arr.push(i);
    }

    return arr;
}

function calculateAllPointsInCircle(cx, cy, rad) {

   var rang = range(-rad, rad + 1);
   var px = [];
   var py = [];
   var xy = [];

   for (var i = 0; i < rang.length; i++) {
     var x = cx + rang[i];
     px.push(x);

     for (var l - rang.length - 1; l > 0; l--) {
        var y = cy + rang[l];
        if (!py.indexOf(y)===-1) { py.push(y); }

        xy.push(x+','+y);
     }
   }

   return {
     x: x,
     y: y,
     xy: xy
   }
}

性能远高于其他答案： http: //jsperf.com/point-in-circle/4 您可以用数学检查我的方程式，使用将验证给定点是否在圆圈内的方程式x*x + y*y <= r*r或x^2 + y^2 <= r^2

编辑 - 超压缩 ES6 版本： 

function range(begin, end) {
  for (let i = begin; i < end; ++i) {
    yield i;
  }
}

function calculateAllPointsInCircle(cx, cy, rad) {
    return {
        x: [cx + i for (i of range(-rad, rad + 1))],
        y: [cy + i for (i of range(-rad, rad + 1))]
    };
}
于 2014-05-29T21:11:43.607 回答