指定された半径内のすべての整数座標を見つける

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が追加されるかどうかに関係ありません。つまり、浮動小数点精度は必要ありません。

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への外側ループと、そのx値での円のy値に従ってy上の内側ループです（-sqrt（r^2 - x^2）から中心が0,0の場合はsqrt（r^2 - x^2）、中心が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)); 
    } 
}