Issue with rounding a vector to stay within a circle?

Question

I'm creating a tile-based map from a circle. I'd like to add some features on the edges of the circle, and I'm currently doing this by comparing the length of a vector and checking if it's less than the radius of the circle.

There appears however to be a slight bug when rounding the distance from any particular diagonal direction.

I've marked every position that the code outputs for the expression if(distance < size) on the provided image. The green points are the ones that are expected and I consider the edge of a circle - the red ones are additional ones that are not expected.

My best guess is that this is a rounding error affected by the length of diagonal lines. I've already attempted to change the way the 'distance' variable is rounded because of this by rounding with Math.Floor and Math.Ceiling but sadly with no change in outcome.

    // i, j is any particular position on the map, can be negative or positive
    var x = i;
    var y = j;

    var v = new Vector2(x, y);
    var distance = (int)v.Length();
    var size = diameter / 2;

    if (distance <= size)
    {
      if (distance == size)
      {
         // green point on image
      }
      else
      {
         // inside the green circle on image
      }
     }

The expected outcome is that it only gives the green pixels on the provided image as the correct edges.

Image with a brief overview of the bug:

Image with the bug in action:

Answer 1

I think you are objecting to the double pixels along the edge.

TL;DR: Directly compute y from x (or x from y) in each octant using the equation of the circle to prevent multiple pixels in each row / column.

I think your expectations come from being used to seeing the rasterization technique of the Midpoint circle algorithm, which manages to draw circles that don't have the objectionable double pixels.

It does so by dividing the circle into 8 parts called octants. In the first quadrant (where x and y are both positive), it's broken into the first octant where x > y and the second octant where y < x. Here: A picture's worth a thousand words. This picture excerpted from Wikipedia.

I won't get too far into the details, but let's just say that, in the 1st octant, there's only one pixel in each row, and in the 2nd octant, there's only one pixel in each column. I think that's your objective -- to achieve the same.

To do this in the 2nd octant, for a given column x, you can compute the unique corresponding y for a circle of a given radius. You would, of course, need to have an if condition to handle the cases for the various octants because in the 1st octant, you'd need to compute a unique x for a given y. (Circles are highly symmetric; it isn't too bad to handle all the cases with a bit of cleverness. I will try to do so in the code below in a straightforward way.)

Basically, if you can perform a check for each dx,dy pair in the grid. If the dy is the same as the dy you computed from the circle equation, then you can light it up. You just have to be careful about which octant you're in to ensure you don't get multiple pixels per row/column.

One last thing before delving into the implementation. You'll probably want a radius that ends in ~.5, because circles with exact integer diameters have one stray pixel at the tippy-top that is ugly. You can either use a ~.5 radius, or put the center at ~.5 coordinates -- one of the two; it's up to you. In my example, I add 0.5 to the radius. You can work out these minor details however you wish.

Here's code:

static void DrawCircle(int[,] grid, int cx, int cy, int radius) {
    int width = grid.GetLength(0);
    int height = grid.GetLength(1);
    int radius_squared = (int)(((double)radius + 0.5)*((double)radius + 0.5));
    for (int y = 0; y < height; ++y)
    {
        for (int x = 0; x < width; ++x)
        {
            int dx = x - cx;
            int dy = y - cy;

            // These three conditions transform all 8 octants into the same octant,
            // where dx and dy are positive and dx <= dy, so they can all be
            // handled with the same calculation.
            if (dx < 0) dx = -dx;
            if (dy < 0) dy = -dy;
            if (dy < dx)
            {
                // swap dx and dy
                int temp = dx;
                dx = dy;
                dy = temp;
            }

            // This now represents "2nd octant" in the picture I provided.
            // directly compute the dy value of the edge of the circle given dx.
            int edgedy = (int)Math.Sqrt(radius_squared - dx * dx);

            // Put a 1 in the cell if it's on the edge, else put a 0.
            // You can modify this as needed, of course.
            grid[x, y] = (dy == edgedy) ? 1 : 0;
        }
    }
}

Result: