6

Currently I am using Bresenham's circle drawing algorithm, which draws circles fine, however I would like a relatively fast and efficient way to draw a circle with a specified thickness (since Bresenham's method only draws a single pixel thickness). I realise that I could simply draw multiple circles with different radii, but I believe this would be very inefficient (and efficiency is important because this will be running on an Arduino where every microsecond is precious). I am currently using the following code:

void circle(byte xc, byte yc, int radius, Colour colour) {
  int x = -radius, y = 0, err = 2 - 2 * radius;
  while(x < 0) {
    setPixel(xc - x, yc + y, colour);
    setPixel(xc - y, yc - x, colour);
    setPixel(xc + x, yc - y, colour);
    setPixel(xc + y, yc + x, colour);
    radius = err;
    if(radius <= y) {
      err += ++y * 2 + 1;
    }
    if(radius > x || err > y) {
      err += ++x * 2 + 1;
    }
  }
}

How could I modify this to allow for specification of the circle's thickness? PS I don't want to use any external libraries, please!

  • 2
    The usual approach is to draw 2 circles (inner and outer) then fill the gap using an appropriate filling rule (eg http://en.wikipedia.org/wiki/Even%E2%80%93odd_rule). – oakad Jan 03 '15 at 13:51
  • Yes but wouldn't that be fairly slow? –  Jan 03 '15 at 13:54
  • 3
    You can use a "compressed" the intermediary: create an array of linked lists to represent the target surface (so each linked list represents a scan line). Use Bresenham's algorithm to put nodes for each "black" pixel into each relevant scan line list. Traverse the resulting structure having the filling rule in mind to draw on the target surface (there will be only 2 - 4 nodes in each list). – oakad Jan 03 '15 at 14:06
  • Ok what do you mean? My level of graphics programming is fairly low, therefore I understood none of that. –  Jan 03 '15 at 14:33

2 Answers2

5

If you scan along octants as explained for the Midpoint circle algorithm, your major coordinate y will always increase by one. You can then draw two circles at once, because their major coordinates are in sync.

Instead of placing pixels, you draw horizontal (and vertical) lines between the points of the inner and outer circle, which have the same y (or x) coordinate. You do so until the outer circle reaches the diagonal.

You keep the state with x and err for two circles, the inner circle i and the outer circle o. After the inner circle has reached the diagonal, the inner point lies on that diagonal. This means you are drawing eight adjoining octant sectors.

This idea is very similar to what @oakad proposed in the comments, but without the need for keeping a list. The Midpoint circle algorithm might be slower than the Bresenham algorithm, so there's probably room for improvement, but the low memory footprint is an advantage.

The code below will draw a hollow circle with the given inner and outer radii. The line width is ro - ri + 1, so that even equal radii will print a circle that is one pixel wide. It won't print anything if the inner radius is smaller than the outer radius.

void xLine(int x1, int x2, int y, int colour)
{
    while (x1 <= x2) setPixel(x1++, y, colour);
}

void yLine(int x, int y1, int y2, int colour)
{
    while (y1 <= y2) setPixel(x, y1++, colour);
}

void circle2(int xc, int yc, int inner, int outer, int colour)
{
    int xo = outer;
    int xi = inner;
    int y = 0;
    int erro = 1 - xo;
    int erri = 1 - xi;

    while(xo >= y) {
        xLine(xc + xi, xc + xo, yc + y,  colour);
        yLine(xc + y,  yc + xi, yc + xo, colour);
        xLine(xc - xo, xc - xi, yc + y,  colour);
        yLine(xc - y,  yc + xi, yc + xo, colour);
        xLine(xc - xo, xc - xi, yc - y,  colour);
        yLine(xc - y,  yc - xo, yc - xi, colour);
        xLine(xc + xi, xc + xo, yc - y,  colour);
        yLine(xc + y,  yc - xo, yc - xi, colour);

        y++;

        if (erro < 0) {
            erro += 2 * y + 1;
        } else {
            xo--;
            erro += 2 * (y - xo + 1);
        }

        if (y > inner) {
            xi = y;
        } else {
            if (erri < 0) {
                erri += 2 * y + 1;
            } else {
                xi--;
                erri += 2 * (y - xi + 1);
            }
        }
    }
}
M Oehm
  • 28,726
  • 3
  • 31
  • 42
  • So I could modify it so that I can specify an thickness for the circle, and then derive the inner and outer radii from that? So replace "int inner, int outer" with "int radius, int thickness" and then do inner=radius-thickness? –  Jan 03 '15 at 16:43
  • @indeed: Yes, of course. You can either write a front-end to this function or you could use your function signature and calculate inner. This code treats the same inner and outer as having a thickness of 1, so you'll probably want `inner = outer - thickness + 1`. – M Oehm Jan 03 '15 at 16:50
  • Actually, something interesting is happening. It is producing different circles than my original code, which sort of makes it incompatible with the rest of my project. Why is this? –  Jan 04 '15 at 12:14
  • Yes, over a radius of 25 they differ in some of the pixels they draw. Which method would you say is more accurate? –  Jan 04 '15 at 12:32
  • The two algorithms are slightly different. For example the one I posted always increases `y` by one. That's why I chose it, because it allows me to line up thze scan lines for the two circles. So I think the difference is in the error calculation. I think both algorithms are only approximations. You can check which is more accurate by calculating the distance of the midpoints and comparing it to the radius. (On a hunch, I'd say that the midpoint algorithm is a bit more accurate, whereas Bresenham is faster.) – M Oehm Jan 04 '15 at 12:38
  • Ok, I did some analysis and it looks like your method is about 0.0015 pixels close to an average of distance=25 for a radius of 25 –  Jan 04 '15 at 13:03
  • I think there’s a mistake in the error calculation. It should be `erro += 2 * (y - xo) + 1;` and `erri += 2 * (y - xi) + 1;` (you put the `)` in the wrong place). I noticed this when comparing the output of bresenham, midpoint and this algorithm. It’s especially noticeable at radius 23. This algorithm was differing from midpoint and resulted in a circle more similar to bresenham. – Indiana Kernick May 04 '19 at 00:15
0

The solution below can be slow, however, it is very simple.

First, draw the inner and outern circles using Bresenham's algorithm. Then, check condition:

if (pow(i - centre, 2) + pow(j - centre, 2) <= pow(outern_radius,2) &&
            pow(i - centre, 2) + pow(j - centre, 2) >= pow(inner_radius,2))

If it is satisfied, setPixel(i,j).

Karol Borkowski
  • 532
  • 7
  • 19