Filled circle in matrix(2D array)

Question

Which algorithm to use to get points of filled circle?

int start_X = 30; // center point
int start_Y = 30;

int r = 5;

// current point
int x; 
int y;

if(?==true)
{
map2D[x][y] = 1; // for filled circle points
}

Solution 1

You get the equation of a circle:

where a & b are the center point coordinates. All x & y points that satisfy this equation are part of the circle. To see if a certain point (x1, y1) is, check if

((x1 - start_X) * (x1 - start_X) + (y1 - start_Y) * (y1 - start_Y)) <= r * r

The <= sign is to include the points that lie inside the circle, too. You can safely limit the point ranges in the intervals [start_X - r; startX + r] and [start_Y - r; startY + r].

Solution 2

You can search over a square region 2r by 2r with center (start_X,start_Y):

std::vector< std::pair<int> > circlePoints;

for(int i = start_X - r; i <= start_X + r; i++)
{
   for(int j = start_Y - r; j <= start_Y + r; j++)
   {
       if((i-r)*(i-r) + (j-r)*(j-r) <= r*r)
       {
         circlePoints.push_back(std::pair<int>(i,j));
       }
   }
}

Solution 3

This is a complete solution in Java. You can easily convert it to C++. Start with an empty matrix predefined with all 0's and fill it with 1's if that the point(x,y) lies inside a circle else fill the outer circle with 9's. (Why 9 - just so that you see circle clearly drawn in the matrix). Below code works fine for the matrix of the odd size. Let me know if anyone has a better solution.

  private static void drawCircle(int[][] emptyMatrix, int diameter) {
    int startX = diameter/2;
    int startY = diameter/2;
    int radius = diameter/2;
    drawCircleRecursive(emptyMatrix, diameter, startX, startY, radius, radius);

    System.out.println("Filled matrix: ");
    for (int i = 0; i < emptyMatrix.length; i++) {
      for (int j = 0; j < emptyMatrix[0].length; j++) {
        System.out.print(emptyMatrix[i][j] + " ");
      }
      System.out.println();
    }
  }

  private static void drawCircleRecursive(int[][] emptyMatrix, int d, int startX, int startY, int x, int y) {

    if(x >= emptyMatrix.length || y >= emptyMatrix[0].length || x < 0 || y < 0 || emptyMatrix[x][y] == 1)
      return;
    else if(emptyMatrix[x][y] == 9)
      return;

    int r = d/2;
    if (((x - startX) * (x - startX) + (y - startY) * (y - startY)) <= (r * r))
      emptyMatrix[x][y] = 1; 
    else 
      emptyMatrix[x][y] = 9;

    drawCircleRecursive(emptyMatrix, d, startX, startY, x+1, y);  // down
    drawCircleRecursive(emptyMatrix, d, startX, startY, x, y+1);  // right
    drawCircleRecursive(emptyMatrix, d, startX, startY, x-1, y);  //up
    drawCircleRecursive(emptyMatrix, d, startX, startY, x, y-1);  //left
    drawCircleRecursive(emptyMatrix, d, startX, startY, x-1, y-1); // diagonal up-left
    drawCircleRecursive(emptyMatrix, d, startX, startY, x+1, y+1); // diagonal right-down
    drawCircleRecursive(emptyMatrix, d, startX, startY, x+1, y-1);  // diagonal left-down
    drawCircleRecursive(emptyMatrix, d, startX, startY, x-1, y+1);  // diagonal right-up


  }

Solution 4

if you wanna go stright to all point in the circle without checking, this is the way.

SatY = CenterY;//StartY + R
        for (int i = StartX; i < EndX; i++)
        {
            int StartY = (int)(SatY - Math.Sqrt(Math.Abs((R + i - StartX) * (R - i + StartX))));
            int EndY = (int)(SatY + Math.Sqrt(Math.Abs((R + i - StartX) * (R - i + StartX))));
            for (int j = StartY; j < EndY; j++)
            {
                // Do Job
            }
        }

View more solutions