9

2次元の座標系がある場合、特定の点から半径内の整数座標を持つすべての点を見つけるにはどうすればよいですか？ポイントを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よりも半径に近いポイントが追加されるかどうかは関係ありません。つまり、浮動小数点の精度は必要ありません。

4

4 に答える 4

11

最も簡単な解決策：正方形を取り、それをフィルタリングします：

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));
}
于 2013-01-11T19:42:19.530 に答える
4

1つの方法は、xの-Rから+ Rへの外側のループと、そのx値（-sqrt（r ^ 2-x ^ 2）からsqrt（r ^）での円のy値に応じたyの内側のループです。 2-x ^ 2）中心が0,0）の場合、中心がX、Yの場合-例で行ったのと同じ方法で、すべてのループ範囲にXまたはYを追加するだけです。

于 2013-01-11T19:35:02.730 に答える
2

中点円アルゴリズムに小さな変更を加えて、塗りつぶされた円を取得できます。

最初に座標を生成します。

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

これにより、サークル内にないいくつかの作業訪問ポイントが節約されますが、少し前処理が必要になります。それは確かに小さな円には役立たないでしょう、そして大きな円には、まあ、私は正直にわかりません。あなたはそれをベンチマークする必要があります。

于 2013-01-11T21:14:22.660 に答える
1

次のコードは、4分の1円に沿って境界を解析し、内部領域を決定します。外側の点や内側の点の距離を計算する必要はありません。（編集：しかし、最後に、塗りつぶされた円のすべてのポイントが追加されます）

一部のミニJavaベンチマークでは、半径が小さい（<10）場合、完全な正方形を解析する単純なアプローチと同じ速度になります。半径20〜40の場合は、約2倍速く、半径> 50の場合は約4倍のスピードアップを達成します。半径がはるかに大きい（> 200）場合は、どのアプローチでも支配的な時間が必要になるため、スピードアップは再び低下します。 10万を超えるポイントを作成および追加するために、それらがどのように決定されるかに関係なく。

// 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));
    }
}
于 2013-01-11T22:48:06.730 に答える