1
$\begingroup$

Given a 2d array of pixel values, is it possible to iterate over just the pixels in a circle in a way that is less costly than simply iterating over a square and checking if a value is within the circle?

I need to get the values of pixels within a circle given center coordinates and the radius. Ideally I would ONLY iterate over the pixels in the circle as the leave number of iterations possible is the least costly for time.

The only solution I have found so far is to iterate over a square(shown in green below) and for each pixel, check if its inside the circle using pythagoras before performing the logic I wish to do.

Is there a way to only iterate over the solid circle of pixels alone?

(Int the image below, the desired pixels are highlighted in RED and the containing square is in GREEN)

thank you in advance for any help and resources offered

Example of what im after.

$\endgroup$
  • $\begingroup$ Well, at the very least, you could calculate the first and last pixel on each row and iterate between them. Symmetry about the two co-ordinate axes should also help: if the centre is at $(a,b)$ and you know that $(a-x,b-y)$ is in the circle, you know that $(a+x,b-y)$, $(a-x,b+y)$ and $(a+x,b+y)$ are all in it, too. $\endgroup$ – David Richerby Feb 8 '18 at 18:24
  • $\begingroup$ Have you tried to simply calculate starting point of the row, mirroring it to find end (also the lower half of the circle)? You have center, radius and y, solve for x? Or simply check Bresenham Circle algorithm, filling (reading) inside row by row (scanline). $\endgroup$ – Evil Feb 8 '18 at 18:24
  • 1
    $\begingroup$ @Evil Haha! I beat you by six seconds, even though my comment is twice as verbose as yours! ;-) $\endgroup$ – David Richerby Feb 8 '18 at 18:27
  • 1
    $\begingroup$ @DavidRicherby that was true, now it is only 3/2 times more verbose ;) I was looking for link with a picture of octant symmetry Bresenham style and midpoint standard. $\endgroup$ – Evil Feb 8 '18 at 18:29
  • $\begingroup$ Thanks @DavidRicherby and @Evil! In case you're interested, I have implemented both my original Pythagoras on a square method, and Bresenham's Algorithm in JavaScript. I have found the Pythagoras method to be 2.8x faster for my use case :D $\endgroup$ – drm18272 Feb 10 '18 at 20:42
1
$\begingroup$

The most important optimization is to save resources, not only avoid traversing the full square. For this reason the best option is to calculate the upper quarter of circle (hull) and then use scanlines - traverse row for fixed number of steps. Exploiting symmetry by calculating octant algorithm may not be the best option due to random access in the array and subtraction used (it should make no difference, but it happens). This is know as the midpoint circle algorithm.

Standard way is to calculate 1/8 of the circle, reflect it and use the hull, dividing circle into rows. The naive algorithm to calculate starting points uses round operation, which is time consuming (but still worth something due to actual avoiding square traversal). More optimized version is due to Bresenham circle which avoids rounding operation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.