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

Question

我代表我的二维空间（考虑一个窗口），其中每个像素都显示为二维数组中的单元格。也就是说，一个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
        }
    }
}

它能满足我的需求吗？我能让它跑得更快吗？

- Kraken

---

为了模拟圆周率，我们生成符合 xx+yy<=rr 约束条件的均匀分布随机值。我认为将随机值放入并搜索邻居，就像爬山算法一样，可能是一个非常好的想法。 - Arnaldo Ignacio Gaspar Véjar

使用勾股定理来确定当前“单元格”的距离是否在圆内。 - intrepidis

Answer 1

它能满足我的需求吗？

对于你的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 the Dark Absol所提出的三角函数非常聪明，但它涉及到像sin和acos这样昂贵的数学函数，这会对性能产生负面影响。

- Adam Stelmaszczyk

---

你说对于100X100它可以工作。那么对于其他尺寸它就不能工作吗？ - Kraken

它总是有效的。问题是，速度有多快。在维度d = 2中，它是O（r ^ 2），其中r是半径。在d = 3中，它是O（r ^ 3），我们正在寻找球体中的点。通常是O（r ^ d）。你的问题是“它是否能满足我的目的”，我理解为“它是否运行得如此之快，以至于我感觉不到它”。我说是的，因为对于r = 100和d = 2，在现代计算机上，即使在JS中，时间也不会引起注意。但是，对于更大的r或d，时间将会引起注意。 - Adam Stelmaszczyk

哦，抱歉，我的意思是如果尺寸100X100是其他的尺寸，比如500X300或者其他什么的。 - Kraken

这对我没有用，而且性能变差了。 - Sairam

JS测试链接返回500。 - Qumber

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

- Niet the Dark Absol

---

我假设，如果您有x中心和y中心的不同坐标，则会更改为第一个for循环：center = xcenter，yspan：center = xcenter，第二个for循环center = ycenter？ - aze45sq6d

没错，你甚至可以在 for 和 sin 中使用不同的 radius 来得到一个椭圆。 - Niet the Dark Absol

@ChandrapalSinghJhala 请看一下我刚才在你上面的评论。 - Niet the Dark Absol

Answer 3

为了提高速度，您可以尽可能在循环外计算。此外，没有必要进行勾股定理平方根运算...只需将所有内容都平方即可。还有一个最终的加速方法是仅对圆的四分之一进行数学计算（因为具有对称性）...当找到匹配项时，只需复制其余三个四分之一的结果。

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);
        }
    }
}

- intrepidis

Answer 4

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

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以对比其他解决方案的性能。

- David Fooks

Answer 5

如果以下条件为真：

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

其中xPos和yPos是您正在检查的点的坐标，那么该点位于您的圆内。

- BlackBox

---

我的解决方案比顺序多个数量级快 ;) - Niet the Dark Absol

我的代码一直以为他必须用最少的字符来完成任务 咳咳 :D - BlackBox

Answer 6

看起来没问题。你可以通过找到 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);      }
}

- OSH

Answer 7

我知道这个问题有一个被接受的答案，但我有一个更简单的解决方案。其他答案让我感到困惑，因为我不知道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))]
    };
}

- user1076821

---

浪费了我的时间去检查它的速度，但是它并没有工作。 - Jacek Pietal