查找给出一个二维坐标系我怎么能找到的所有点整数在半径从给定的点的坐标给定半径

Question

所有整数坐标？我想要的点为x坐标和y坐标值。

找点周围的给定点方是容易的，可以这样做：

for(int x = -radius + point.x; x < radius + point.x; ++x) 
for(int y = -radius + point.y; y < radius + point.y; ++y) 
{ 
    points.insert(point(x, y)); 
} 

但我怎么能找到在围绕给定的点了一圈点？该算法与性能相关，但与精度无关。所以，如果一个点接近半径，加1或不加1并不重要。换句话说，我不需要浮点精度。

Answer 1

最简单的解决办法：拿一个正方形并将其过滤：

Point point(100, 100); 
for(int x = -radius; x <= radius; ++x) 
for(int y = -radius; y <= radius; ++y) 
if(x*x + y*y <= radius* radius) { 
    points.insert(Point(x + point.x, y + point.y)); 
} 

Answer 2

的一种方式是x上的外环从-R到+ R，并根据在该x值（圆的y值从-sqrt（R^2 Y上内环 - X^2）至开方（R^2 - X^2）如果中心是在0,0），如果该中心在X，Y - 只需添加X或Y的所有环路范围内以同样的方式，你在你的例子一样

Answer 3

你可以做一个小的修改到中点画圆算法得到一个实心圆。

首先生成坐标：

data = new int[radius]; 
int f = 1 - radius, ddF_x = 1; 
int ddF_y = -2 * radius; 
int x = 0, y = radius; 
while (x < y) 
{ 
    if (f >= 0) 
    { 
     y--; 
     ddF_y += 2; f += ddF_y; 
    } 
    x++; 
    ddF_x += 2; f += ddF_x; 
    data[radius - y] = x; data[radius - x] = y; 
} 

然后访问所有的内部点：

int x0 = center.X; 
int y0 = center.Y - Radius; 
int y1 = center.Y + Radius - 1; 

for (int y = 0; y < data.Length; y++) 
{ 
    for (int x = -data[y]; x < data[y]; x++) 
    { 
     doSomething(x + x0, y + y0); 
     doSomething(x + x0, y1 - y); 
    } 
} 

这可以节省一些工作访问，将不会在圈内点，但其代价一点预处理。这绝对不会对小圈子有所帮助，对于更大的圈子来说，我真的不知道。你必须对它进行基准测试。

Answer 4

下面的代码只是解析沿着四分之一圆的边界，以确定内部区域。它不需要计算外点的距离，也不需要计算内点的距离。 （编辑：但最后，添加了实心圆的所有点）

在一些小型的Java基准测试，对于小半径（< 10），它是相同的速度与解析的简单方法全方。对于半径20-40，它快了大约2倍，并且对于半径> 50，它实现了大约4倍的加速。对于一些更大的半径（> 200），加速再次减小，因为对于任何方法，需要占优势时间用于创建和添加> 100k点 - 无论他们如何确定。

// add the full length vertical center line once 
for (int y = -radius + point.y; y <= radius + point.y; ++y) 
    points.insert(Point(point.x, y)); 

int sqRadius = radius * radius; 

// add the shorter vertical lines to the left and to the right 
int h = radius; 
for (int dx = 1; dx <= radius; ++dx) { 
    // decrease h 
    while (dx*dx + h*h > sqRadius && h > 0) 
     h--; 

    for (int y = -h + point.y; y <= h + point.y; ++y) { 
     points.insert(Point(point.x + dx, y)); 
     points.insert(Point(point.x - dx, y)); 
    } 
}