bjd2385 bjd2385 - 2 months ago 12
Python Question

Generate coordinates in grid that lie within a circle

I've found this answer, 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).

So far I have the following function in Python. I know by Gauss' circle problem the number of coordinates I will end up with, but I'd like to generate those points one by one as well.

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


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

Answer

What about simply something like this (for a circle at origin)?

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)

This can easily be adapted to the general case when the circle is not centred at the origin.