查找給出一個二維座標系我怎麼能找到的所有點整數在半徑從給定的點的座標給定半徑

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