Reducing the number of iterations in double loop

Question

I have a list of circles (centre and radius), and for each circle, I need to do some processing for all circles whose centres are inside the circle.

I do a simple double loop as

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct Points
{
    double x;
    double y;
    double r;
} Points;

int main()
{

    int num = 10000; // number of circles
    Points c[num];   // circles

    for (int i = 0; i < num; i++)
    {
        for (int j = 0; j < num; j++)
        {
            // checking if the distance of point i and j is small than i's radius
            if (c[i].r > sqrt(pow(c[i].x - c[j].x, 2) + pow(c[i].y - c[j].y, 2)))
            {
                // do the processing
            }
        }
    }

    return 0;
}

The problem is the performance. For 10,000 circles I do 100M iterations.

Answer 1

Consider pre-preprocessing the array into a better datastructure. Here is one thing I would try.

1. Get the max-radius and min and max x and y from the list
2. Make a datastructure that represents a grid of cells using the numbers from (1) as a guide.
3. Put each circle element in a cell in the grid based on its center (some cells have more than one circle).

Now, for any circle you only need to look in the surrounding cells for as big as the max radius. It should cut the search space for each circle considerably

As an alternative, in step 3, put the circle into each cell it touches. So, each circle is in more than one cell. Then, for each circle you just need to process each cell its in.

Answer 2

This is not an answer, but a general advise when finding inner circles:

Your (pseudo-)code says (basically):

let C = centerpoint of your circle;
let R = radius of your circle;
for each point p: 
  if distance(p,C) <= R 
  then treat_as_inside_circle(p)
  else treat_as_outside_circle(p);

This is correct, but performance-wise you can do better (also pseudo-code):

let C = centerpoint of your circle; => (x_C, y_C)
let R = radius of your circle;
for each point p (x_P, y_P) : 
  if ((abs(x_C - x_P) <= R) AND (abs(y_C - y_P) <= R))
  then
       {
         if distance(p,C) <= R
         then treat_as_inside_circle(p);
         else treat_as_outside_circle(p);
       }
  else treat_as_outside_circle(p);

This first checks if p is inside the square (center C, "radius" R), and only in that case, the check is done if p is inside the circle.
(As you can imagine, a point is only present inside a circle, if it is inside the square with same center and "radius" of that circle.)

The big advantage is (performance-wise), that only "simple" calculations are sufficient for checking the square, while performance-wasting calculations (floating point square-root) are needed for checking the circle.

Answer 3

You can limit the number of calculations much faster than by actually finding the actual distance. If any X or Y coordinate is too far from the X,Y center of the circle you're working on, the center of the other circle can't be within that one circle.

So filter out the number of circles you compare with simple > and < on the X and Y coordinates (and experiment with replacing sqrt() with hypot() which is likely superior to sqrt( pow() + pow() ).):

int main()
{
    int num = 10000; // number of circles
    Points c[num];   // circles

    for (int i = 0; i < num; i++)
    {
        double max_x = c[i].x + c[i].r;
        double min_x = c[i].x - c[i].r;
        double max_y = c[i].y + c[i].r;
        double min_y = c[i].y - c[i].r;

        for (int j = 0; j < num; j++)
        {
            // if the point is too far in any one dimension
            // it can't be within the current circle
            if ( ( c[j].x > max_x ) || ( c[j].x < min_x ) ||
                 ( c[j].y > max_y ) || ( c[j].y < min_y ) )
            {
                continue;
            }

            // checking if the distance of point i and j is small than i's radius
            if (c[i].r > hypot(c[i].x - c[j].x, c[i].y - c[j].y))
            {
                // do the processing
            }
        }
    }

    return 0;
}