Circle with thickness drawing algorithm

问题:

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!

回答1:

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);
            }
        }
    }
}

回答2:

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).