Iterate over pixels along a rasterized circular arc

2
votes

I want to iterate over pixels along a rasterized circular arc, given its radius, start and end angles in radians, eg:

template<typename Functor>
void arc(float startRadians, float endRadians, int radius, Functor f);

To be used like:

arc(0.f, M_PI, 10, [](int x, int y) {
  std::cout << "got: " << x << " " << y << "\n";
});

There's a few catches:

  • pixels have integer coordinates
  • radius is also given as an integer
  • the rasterised arc is effectively every pixel in a sector between the arc of radius radius and the arc of radius radius-1

In the picture below:

  • blue pixels have been visited, red pixel is the next to be visited
  • the arc is confined by the two radial lines defined by start/end angles, and the sector between the two arcs radius, radius-1.
  • finally, if every arc with radius 0 to 100 were to be drawn, angles 0 to 2*PI, then we'd get a filled disc/circle of radius 100 and no pixel would be visited twice.

I think Bresenham's circle algorithm doesn't directly apply to this problem, because of the angle constraints and visitation order.

In stackoverflow, I believe this is the most closely related question:

Finally, OpenCV has something similar/related in spirit, but only for lines:

enter image description here

1
c++algorithmmathgeometryrasterizing
Er, no, Bresenham’s algorithm is exactly what you want... you just need to add logic to the basic algorithm that: skips the 8-quadrant optimization (draw each quadrant individually with a subfunction in the order you wish), and watches the in/out angles in the quadrants where it matters. The other option is to just use floating-point calculations directly. – Dúthomhas
Oh, so your idea is generate all the points using standard Bresenham and just filter out those that fall out of the angle/quadrants required? Does Bresenham have the required properties of visiting all pixels (filling a disc when every integer radius is rasterised) and not visiting pixels twice? – Giovanni Funchal
No, generate only needed part of quadrant (stop when y/x or x/y reaches tan(angle) limit) – MBo
I know Bresenham's but I still don't understand the adaptation that makes it work correctly in my case... I guess code or pseudo code for it would be welcome. – Giovanni Funchal
I think you'll want to use Bresenham on the inner and outer radii and then fill in the raster lines between yourself, basically. However, without having thought about it too deeply, I'm pretty sure your 'finally' bullet point is impossible, in the 'no pixel visited twice' bit. – AakashM

1 Answers

0
votes

Take a look at cvLinearPolar().

It maps the image from the x,y coordinate system, to polar. The resulting image is rows -> angle and columns-> radius. Your rastering at that point would be looping row column order no special functional rastering.

This means every rows is dtheta = 2*Pi/(rowNum) therefore your arc would be startAngle = angle1/dtheta and likewise endAngle = angle2/dtheta.

Similarly your radius calculation drad = maxRad/(columnNum).

so to get your arc from the polar image:

for(int i = maxRad; i > 0; i--) // start at longest radius spiral in
{
 for(int j = startAngle; j < endAngle;j++) angle 
 {
    // do action on polarImage[i,j];
 }

}