高速整数座標円内/円に沿って半径rの元を中心に

Question

半径rで0,0の中心を持つ円があるとします。

このサークルの内側にあるすべての整数点を取得したいと思います。この問題は簡単に解決できます。

x = -r to +rとy =-r to +rからif x * x + y * y <= r * rを参照してください。もしそうなら、結果にポイントを追加してください。

ただし、これを行う最も簡単な方法は何ですか？ (2r)^2から4/3 r^2

より具体的には、私は刻まれた四角形の長さを計算し、残りの残りのコンポーネントを追加できるという気持ちがあります。私はこれをどうやって行うのか分からない。数学は少し緻密です。私は一般的なアルゴリズムの応答をしたいのでコードを投稿するのを控えていますが、もし好みがあれば、これはJVM言語を使うべきであるという最終的なベンチマークを述べるかもしれません。

助けが必要ですか？

注：これはガウスサークルの問題と似ていますが、ポイントの数をカウントする代わりに、ポイントが何であるかを知りたいと思います。

for x in [-floor(r), floor(r)] 
    y_max = floor(sqrt(r^2 - x^2)) # Pythagora's theorem 
    for y in [-y_max, y_max] 
     # (x, y) is good ! 

：

Answer 1

あなたは最大yを計算することによって値を直接得ることができ、そのようなxの値ごとに（第2の（X、0）の垂直に円上の点の座標）とにかくあなたが結果にこれらの点を持っているので、あなたはずっと良くできているとは思わない（多分y_maxを速く計算することはできますが、それは大きな勝利にはなりません）。

EDIT：

これは、ポイントの数なので、あなたが行うことができます少なくともある、*パイのR^2時間です。 あなたは四分円だけを行い、他のものを対称で取得することで、いくつかの計算を保存することができますが、それがより高速であるかどうかもわかりません。