生成位于圆内的网格坐标

Question

我找到了这个答案, 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).

到目前为止，我在 Python 中有以下函数。我知道通过高斯圆问题我最终会得到坐标的数量，但我也想一一生成这些点。

from typing import Iterable
from math import sqrt, floor

def circCoord(sigma: float =1.0, centroid: tuple =(0, 0)) -> 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

我想做的是仅迭代位于像素 3 * sigma 范围内的像素（在centroid上述函数中）。

---

此后，我编写了以下示例脚本，证明下面的解决方案是准确的。

#! /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) -> 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) -> 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)

输出为

./circleCheck.py -s 4

是：

Answer 1

像这样的简单的东西（对于原点的圆）怎么样？

X = int(R) # R is the radius
for x in range(-X,X+1):
    Y = int((R*R-x*x)**0.5) # bound for y given x
    for y in range(-Y,Y+1):
        yield (x,y)

当圆的中心不在原点时，这可以很容易地适应一般情况。