Pythonでは、2つの円に共通するすべての整数点をどのように見つけるのでしょうか。
たとえば、中心点と半径を持つ2つの（同じサイズの）円のベン図のような交点を想像してみ(x1,y1)て(x2,y2)くださいr1=r2。(xi1,yi1)さらに、円の2つの交点がとであることがすでにわかってい(xi2,yi2)ます。
(x,y)両方の円に含まれるすべての点のリストを効率的に生成するにはどうすればよいでしょうか。つまり、交点を含むボックスを描画してそれを反復処理し、特定の点が両方の円内にあるかどうかを確認するのは簡単ですが、より良い方法はありますか？
円の位置と半径がグリッドよりも小さい粒度で変化する可能性がある場合は、とにかく多数のポイントをチェックします。
検索エリアを適切に定義することで、チェックするポイントの数を最小限に抑えることができます。幅は交点間の距離に等しく、高さはに等しい
r1 + r2 - D
D2つの中心の分離であると。この長方形は通常、X軸とY軸に位置合わせされていないことに注意してください。（これにより、2つの円が交差するかどうかのテストも行われます！）
実際には、これらのポイントの半分をチェックするだけで済みます。半径が同じである場合、それらの4分の1をチェックするだけで済みます。問題の対称性はそこであなたを助けます。
ここには 4 つのケースがあることに注意してください。
また、グラフィックス開発で使用されるさまざまなクリッピング アルゴリズムを調べることもできます。私はクリッピングアルゴリズムを使用して、あなたがここで求めているのと同様の問題をたくさん解決しました。
あなたはほとんどそこにいます。ボックス内のポイントを反復することはかなり良いはずですが、2 番目の座標について制限間で直接反復する場合は、より良い結果が得られます。
最初に x 軸に沿って反復し、次に y 軸について、境界ボックスの座標間で反復する代わりに、各円が x 線と交差する場所を特定するとします。より具体的には、交点の y 座標に関心があり、それらの間を反復します。 （丸めに注意）
これを行うと、サークルの内側にいることが既にわかっているため、チェックを完全にスキップできます。ポイントが多い場合は、多くのチェックをスキップすると、パフォーマンスが向上する可能性があります。
追加の改善として、x 軸または y 軸を選択して、交点の計算に必要な回数を最小限に抑えることができます。
では、両方の円の内側にある格子点を見つけたいですか?
ボックスを描画し、ボックス内のすべてのポイントを反復処理するというあなたが提案した方法は、私にとって最も簡単なようです。ボックス内のポイントの数が交点のポイントの数と同等である限り、おそらく効率的です。
また、可能な限り効率的でなくても、それが本当のボトルネックであると確信できる十分な理由が得られるまでは、最適化を試みるべきではありません。
「すべてのポイント」とは、「すべてのピクセル」を意味すると思います。ディスプレイが NX x NY ピクセルであるとします。2 つの配列を持つ
int x0[NY], x1[NY]; initially full of -1.
交差点は、2 つの曲線の間の菱形です。各曲線に沿って x、y 値を繰り返します。各 y 値 (つまり、曲線が y + 0.5 と交差する場所) で、x 値を配列に格納します。x0[y] が -1 の場合は x0 に格納し、そうでない場合は x1 に格納します。
また、y の最小値と最大値を追跡します。
完了したら、y 値を反復処理し、各 y で、x0 と x1 の間の x 値を反復処理しますfor (ix = x0[iy]; ix < x1[iy]; ix++)(またはその逆)。
ピクセルは、x と y が整数であるポイントではないことを理解することが重要です。むしろ、ピクセルはグリッド線の間の小さな正方形です。これにより、エッジケースの問題が発生するのを防ぐことができます。