• @Andreas_Rozek - this is my function, implementing an Andres circle. Heavily based on example implementations on French Wikipedia .

    I think it can probably be optimised more, and ultimately I also want to draw this a bit at a time. My best approach to that so far is having an array per octant and pushing/unshifting on each iteration for each circle so that I can step through later, but I think I can improve on that.

    I spent a lot of thinking about allocating a fixed length array for the coordinates, but I've come to the conclusion that it isn't possible to know the length a priori (at least, I think that is the case).

    const drawThickRing = function (x_centre, y_centre, r, thickness) {
      // Uses the Andres circle drawing algorithm to draw a ring
      // with outer radius r and a specified thickness.
    
      var x, y, d;
      for (let t = 0; t < thickness; t++) {
        r--;
        x = 0;
        y = r;
        d = r - 1;
    
        while (y >= x) {
          g.setPixel(x_centre + x, y_centre - y);
          g.setPixel(x_centre + y, y_centre - x);
          g.setPixel(x_centre + y, y_centre + x);
          g.setPixel(x_centre - x, y_centre + y);
          g.setPixel(x_centre + x, y_centre + y);
          g.setPixel(x_centre - y, y_centre + x);
          g.setPixel(x_centre - y, y_centre - x);
          g.setPixel(x_centre - x, y_centre - y);
    
          if (d >= 2 * x) {
            d -= 2 * x + 1;
            x++;
          } else if (d < 2 * (r - y)) {
            d += 2 * y - 1;
            y--;
          } else {
            d += 2 * (y - x - 1);
            y--;
            x++;
          }
        }
      }
    };
    
    drawThickRing(85, 85, 70, 10);
    
  • this looks as if you would draw concentric rings with an increasing radius. How can you prove, that discretisation does not produce small "holes" in your ring?

    Addendum: I'm currently reading the french Wikipedia entry (well, after translation into german - my french is not good enough for maths) and it seems to be a characteristic of that algorithm that no holes are left

  • Yes, that is exactly how I came to that algorithm. I had been trying to create a solid ring. At one point in desperation I started with the same polygon approach you tried, but I stopped when I hit the point limit.

    It isn't described on the English wikipedia, I don't think I saw it on the German one either even though it lists many more circle drawing algorithms than the English one.

    I haven't been able to read the original paper by Andres, it is paywalled, but I have read some of his later papers* and others that expand on the work. If you want to see the proof (or just out of interest) they can be found online.

    • I say read, but I don't understand most of it. It took me a long time before I even remembered how the notation for sets worked.
About