Generate coordinates in grid that lie within a circle
<p>I've found <a href="https://stackoverflow.com/a/12364749/3928184">this answer</a>, which seems to be somewhat related to this question, but I'm wondering if it's possible to generate the coordinates one by one without the additional ~22% (1 - pi / 4) loss of comparing each point to the radius of the circle (by computing the distance between the circle's center and that point).</p>

<p>So far I have the following function in Python. I know by <a href="http://mathworld.wolfram.com/GausssCircleProblem.html" rel="nofollow noreferrer">Gauss' circle problem</a> the <em>number</em> of coordinates I will end up with, but I'd like to generate those points one by one as well.</p>

<pre><code>from typing import Iterable
from math import sqrt, floor

def circCoord(sigma: float =1.0, centroid: tuple =(0, 0)) -&gt; Iterable[tuple]:
    r""" Generate all coords within $3\vec{\sigma}$ of the centroid """

    # The number of least iterations is given by Gauss' circle problem:
    # http://mathworld.wolfram.com/GausssCircleProblem.html

    maxiterations = 1 + 4 * floor(3 * sigma) + 4 * sum(\
      floor(sqrt(9 * sigma**2 - i**2)) for i in range(1, floor(3 * sigma) + 1)
    )

    for it in range(maxiterations):
       # `yield` points in image about `centroid` over which we loop
</code></pre>

<p>What I'm trying to do is iterate over only those pixels lying within 3 * sigma of a pixel (at <code>centroid</code> in the above function).</p>

<hr>

<p>I've since written the following example script that demonstrates that the solution below is accurate.</p>

<pre><code>#! /usr/bin/env python3
# -*- coding: utf-8 -*-


import matplotlib.pyplot as plt
from matplotlib.patches import Ellipse
import numpy as np
import argparse
from typing import List, Tuple
from math import sqrt


def collect(x: int, y: int, sigma: float =3.0) -&gt; List[Tuple[int, int]]:
    """ create a small collection of points in a neighborhood of some point 
    """
    neighborhood = []

    X = int(sigma)
    for i in range(-X, X + 1):
        Y = int(pow(sigma * sigma - i * i, 1/2))
        for j in range(-Y, Y + 1):
            neighborhood.append((x + i, y + j))

    return neighborhood


def plotter(sigma: float =3.0) -&gt; None:
    """ Plot a binary image """    
    arr = np.zeros([sigma * 2 + 1] * 2)

    points = collect(int(sigma), int(sigma), sigma)

    # flip pixel value if it lies inside (or on) the circle
    for p in points:
        arr[p] = 1

    # plot ellipse on top of boxes to show their centroids lie inside
    circ = Ellipse(\
        xy=(int(sigma), int(sigma)), 
        width=2 * sigma,
        height=2 * sigma,
        angle=0.0
    )

    fig = plt.figure(0)
    ax  = fig.add_subplot(111, aspect='equal')
    ax.add_artist(circ)
    circ.set_clip_box(ax.bbox)
    circ.set_alpha(0.2)
    circ.set_facecolor((1, 1, 1))
    ax.set_xlim(-0.5, 2 * sigma + 0.5)
    ax.set_ylim(-0.5, 2 * sigma + 0.5)

    plt.scatter(*zip(*points), marker='.', color='white')

    # now plot the array that's been created
    plt.imshow(-arr, interpolation='none', cmap='gray')
    #plt.colorbar()

    plt.show()


if __name__ == '__main__':
    parser = argparse.ArgumentParser()

    parser.add_argument('-s', '--sigma', type=int, \
      help='Circle about which to collect points'
    )

    args = parser.parse_args()

    plotter(args.sigma)
</code></pre>

<p>And the output for</p>

<pre><code>./circleCheck.py -s 4
</code></pre>

<p>is:</p>

<p><a href="https://i.stack.imgur.com/dXomh.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/dXomh.png" alt="enter image description here"></a></p>