1

半径の値を入力できる関数が欲しいのですが、その関数でそのサイズの円の面積を吐き出します。キャッチは、整数ベースの座標に対してのみそうすることです。

ガウスの円の問題を調べるように他の場所で言われました。これは私が興味を持っているものとまったく同じように見えますが、その背後にある数学を本当に理解していません（私が欲しいものを計算するのに実際に正確であると仮定します）。

ちなみに、私は現在、修正された円描画アルゴリズムを使用しています。これは、実際に希望する結果を生成しますが、非常に非効率的です（アルゴリズムと、領域を取得するために使用する方法の両方）。

したがって、これに対する可能な答えは、そのようなものが存在する場合のそのような関数の実際のコードまたは擬似コード、またはガウスの円の問題の完全な説明のようなものであり、なぜそれが私が探しているものであるかどうかです。

関数が生成することを期待する結果：

Input: Output
0: 1
1: 5
2: 13
3: 29
4: 49
5: 81
6: 113
7: 149
8: 197
9: 253
4

2 に答える 2

2

私も最近この問題を解決する必要がありました。最初のアプローチはNumeronのアプローチでした。中心から外側に向かってx軸を繰り返し、右上の4分の1内のポイントを数え、4倍にします。

その後、アルゴリズムを約3.4倍改善しました。私が今していることは、その円の内側の内接正方形内にある点の数と、その正方形と円の端の間にあるもの（実際には反対の順序）を計算することです。このようにして、実際には、円のエッジ、x軸、および正方形の右エッジの間のポイントの8分の1を数えます。コードは次のとおりです。

public static int gaussCircleProblem(int radius) {
    int allPoints=0; //holds the sum of points
    double y=0; //will hold the precise y coordinate of a point on the circle edge for a given x coordinate.
    long inscribedSquare=(long) Math.sqrt(radius*radius/2); //the length of the side of an inscribed square in the upper right quarter of the circle
    int x=(int)inscribedSquare; //will hold x coordinate - starts on the edge of the inscribed square
    while(x<=radius){
        allPoints+=(long) y; //returns floor of y, which is initially 0
        x++; //because we need to start behind the inscribed square and move outwards from there
        y=Math.sqrt(radius*radius-x*x); // Pythagorean equation - returns how many points there are vertically between the X axis and the edge of the circle for given x
    }
    allPoints*=8; //because we were counting points in the right half of the upper right corner of that circle, so we had just one-eightth
    allPoints+=(4*inscribedSquare*inscribedSquare); //how many points there are in the inscribed square
    allPoints+=(4*radius+1); //the loop and the inscribed square calculations did not touch the points on the axis and in the center
    return allPoints;
}

これを説明するための写真は次のとおりです。

私のガウスの円の問題のアルゴリズムが示されています

  1. 円の右上の四分の一に内接する正方形（ピンク）の辺の長さを切り下げます。
  2. 内接正方形の後ろの次のx座標に移動し、端に到達するまでオレンジ色の点のカウントを開始します。
  3. オレンジ色のポイントに8を掛けます。これはあなたに黄色のものを与えるでしょう。
  4. ピンクの点を四角にします。これはあなたに紺色のものを与えるでしょう。次に4を掛けると、緑色のものが得られます。
  5. 軸上の点と中央の点を追加します。これにより、水色のものと赤いものが得られます。
于 2017-02-21T16:57:30.403 に答える
1

これは古い質問ですが、私は最近同じことに取り組んでいました。あなたがやろうとしているのは、あなたが言ったように、ガウスの円の問題です。これは、ここで説明されているようなものです。

私もその背後にある深刻な数学を理解するのは難しいですが、奇妙なエイリアンのシンボルを使用しない場合、多かれ少なかれそれは次のようになります。

1 + 4 * sum(i=0, r^2/4, r^2/(4*i+1) - r^2/(4*i+3))

これは少なくともJavaでは次のとおりです。

int sum = 0;
for(int i = 0; i <= (radius*radius)/4; i++)
  sum += (radius*radius)/(4*i+1) - (radius*radius)/(4*i+3);
sum = sum * 4 + 1;

なぜ、どのようにこれが機能するのかわかりません。正直に言うと、パフォーマンスがOではなくO（r ^ 2/4）であることを意味するため、1行ではなくループを使用してこれを取得する必要があります。 （1）。

数学の魔法使いはループよりもうまくいくようには見えないので、私はそれをO（r + 1）のパフォーマンスに下げることができるかどうかを確認することにしました。したがって、上記は使用せず、以下を使用してください。O（r ^ 2/4）はひどく、平方根を使用しているにもかかわらず遅くなります。

int sum = 0;
for(int x = 0; x <= radius; x++)
  sum += Math.sqrt(radius * radius - x * x);
sum = sum * 4 + 1;

このコードが行うことは、直交する線に沿って中心から端までループし、各点で線から端までの距離を垂直方向に追加することです。最後に、クォーター内のポイント数が含まれるため、結果が4倍になり、中心ポイントもあるため1が追加されます。wolframの方程式も4を掛けて1を足すので、似たようなことをしているように感じますが、IDKはなぜr^2/4をループするのですか。

正直なところ、これらは優れた解決策ではありませんが、最高の解決策のようです。これを定期的に実行する関数を呼び出している場合は、新しい半径が表示されたら、毎回完全な計算を行うのではなく、結果をルックアップテーブルに保存します。

それはあなたの質問の一部ではありませんが、誰かに関係があるかもしれないので、とにかくそれを追加します。私は個人的に、次のように定義されたセルを持つ円内のすべての点を見つけることに取り組んでいました。

(centreX - cellX)^2 + (centreY - cellY)^2 <= radius^2 + radius

余分な+半径がこれをピタゴラスの定理と正確に一致させないので、これはすべてを強打から外します。ただし、この余分なビットにより、直交するエッジに小さなにきびがないため、円はグリッド上で視覚的にはるかに魅力的に見えます。はい、私の形はまだ円ですが、半径としてrの代わりにsqrt（r ^ 2 + r）を使用していることがわかりました。これは明らかに機能しますが、方法を尋ねないでください。とにかく、それは私にとって、私のコードは少し異なり、次のように見えることを意味します：

int sum = 0;
int compactR = ((radius * radius) + radius) //Small performance boost I suppose
for(int j = 0; j <= compactR  / 4; j++)
  sum += compactR / (4 * j + 1) - compactR / (4 * j + 3);
sum = sum * 4 + 1;
于 2013-09-05T02:36:53.890 に答える