CODEWITHSUNDEEP
javaarraysgeometry
NotAPro
NotAPro

Reputation: 129

How to check which points are in a circle?

Okay so say there is a grid, which I have stored as a 2 dimensional array, that is 10 by 10.

int[][] grid = new int[10][10];

The origin of the grid is at the bottom left, like a normal x y plane, and there is a circle of radius 5 in the centre of the grid at (5,5), like so:

Terrible drawing

I want to go through this array and basically check which points are inside the circle, but I do not want to loop through the entire array. By default, every point on a corner is not going to be in the circle, so I would want to ignore those, and similarly the points that are close to the corner, etc.

Just the points that are in the circle. I have a much bigger grid and looping through unnecessary stuff that I already know isn't in the circle would waste time. Is there a way to do this? Because, given that I already know the radius and centre of the circle, there should be a nice easy way to go through those points which are in the circle and change them from 0 to -1, for example.

Otherwise, I would stand to lose 100 - 25π ≈ 21.46% time.

BETTER CLARITY: I already know that I can bound the circle with a square, and loop through the points in that square and check each points distance from the centre of the circle (x^2 + y^2 < r^2), but this is what I am trying to avoid, due to the constant overhead every time of checking the bits that aren't in the circle, when I know they are not in the circle beforehand.

Upvotes: 0

Views: 286

Answers (1)

Oleg Sklyar
Oleg Sklyar

Reputation: 10092

Ok, after a long discussion, here is the solution. You scan across one axis of a quarter slice, compute the extension to which you need to fill that quarter outwards and then fill all 4 quarters at once.

int n = 1000;

// you will need to think yourself about the odd number or elements
int r = n / 2;
int r2 = r * r;

Putting (0,0) at the centre of the matrix in both cases, the optimized solutions can look like this:

int[][] grid0 = new int[n][n];
for (int i = 0; i < r; i++) {
    double m = Math.sqrt(r2 - i * i);
    for (int j = 0; j < m; j++) {
        grid0[r + i][r + j] = 1;
        grid0[r + i][r - j] = 1;
        grid0[r - i][r + j] = 1;
        grid0[r - i][r - j] = 1;
    }
}

As commented elsewhere, the extension of filling the circle is computed in O(n).

Here is the straightforward validation:

int[][] grid1 = new int[n][n];
// you will need to think yourself about the even number
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if ((i - r) * (i - r) + (j - r) * (j - r) < r2) {
            grid1[i][j] = 1;
        }
    }
}

Both produce the same number of filled points.

Time measurements over 10000 executions (with array initialization outside of the time loop):

the optimized one 6.0s

the exhaustive one 15.6s

So, I do admit there is a difference, an astonishing one. Although for a fair comparison, the latter snippet should also be using a quarter slice of the circle.

One can speed up the optimized solution even further using some sort of memory copy routine to fill the values from 0 to the computed point rather than a plain loop, but that is beyond the scope.

Upvotes: 1

Related Questions