Optimize circle inside circle detection algorithm lower than O(n²)

Question

I am trying to do a function that takes a list of circles, and returns only a list of circles that are fully overlapped (one inside another). The problem is that the algorithm is at least O(n²), due to the nested for's in getConcentricCircles function, and taking ages for large datasets. Is there any way to optimize it?

EDIT: I don't know if this would help, but I use the algorithm to detect false positives in iris and pupil detection. If a circle is fully inside another circle, it is likely that that is the pupil and the outside is the iris. They should be concentric, what would simplifiy a lot, but it happens that the pupil in the human eye is not exactly in the center of the iris, that is why I do this.

EDIT 2: I have replaced isCircleInCircle with Peter Lawrey's solution, mine was not correct for some cases

Function to check if a circle is inside a circle:

private static boolean isCircleInCircle(Circle a, Circle b) {
    // the circle is inside if the distance between the centre is less than the difference in the radius
    double dx = a.getX() - b.getX();
    double dy = a.getY() - b.getY();
    double radiusDifference = a.getRadius() - b.getRadius();
    double centreDistanceSquared = dx*dx + dy*dy; // edited
    return radiusDifference * radiusDifference > centreDistanceSquared;
}

Then I check every element of the list with each other, and save only the overlapping circles (and the overlapped circle):

public HashSet<Circle> getConcentricCircles(List<Circle> circleList) {
    HashSet<Circle> toReturn = new HashSet<Circle>();

    for (Circle circle : circleList) {
        for (Circle toCheck : circleList) {
            // if the circles are not the same and one is inside another,
            if (!toCheck.equals(circle) && isCircleInCircle(circle, toCheck)) {
                // add both to the hashset
                toReturn.add(circle);
                toReturn.add(toCheck);
            }
        }
    }
    return toReturn;
}

Answer 1

The complexity of this algorithm can't be reduced below O(n^2). Imagine a regular grid, whose points are the centers of circles and radius of a circle is 1 and the distance between the neighboring grid points is 2. No circle is contained in any other circle. To prove this you have to check every circle against every other. If you don't prove every combination then, there exist circles a and b, which weren't tested against each other. So now let the matrix look only a bit different: circle a is a bit smaller than b and they share the same center. So you didn't find that a is contained in b and hence your algorithm would be incorrect. So much for the proof of the complexity.

To help speeding up your program, you have to concentrate on the average case: That means small circles are contained in larger ones. Build up a directed graph, whose nodes represent the circles and whose edges indicate that the source circle contains the target circle. Start with the circle with the largest radius. Build the graph using depth first search. If you know that circle a is contained in another circle. Then try find a circle b that is contained in a. If b exists, first go on with b. When there is nothing more contained in b make one step back and go on with all circles that haven't been included in another found circle. This gives you a complexity of O(nlog(n)) in the best case. This is due to the management of the remaining nodes while searching for contained nodes and the sorting by radius. The best case here is that all circles have the same center and different radius.

EDIT:
The answer of Aki reminded me of another way to speed this up. In the average case the circles will form clusters, where one circle is partly overlapped by some others. So you can first compute a partition of dependent sets (no I don't mean independen sets as this would be NP-hard). This reduces the data size that the above algorithm has to use.

Then there is another improvement possible when it comes to finding candidates that may be overlapped completely. Since the circles are contained in a plane, spatial data structures like R-trees or quadtrees can be used to find the candidates, that may be overlapped completely, more efficient.

However I don't think that this will reduce worst case complexity, Even these suggestions will improve performance in the worst case mentioned above. The new worst case might be circles, whose centers are the points of a regular grid, but having a radius that is very large when comparing it to the distance between the points in the regular grid.

Answer 2

If the distribution of the circles allow, one could divide the circles into few or more slots based on their location -- and then restrict the testing into the same or nearby slots.

As it turns out, that the question is for realtime eye-detection with sufficiently low number of eyes, the complexity will not make an issue. One can easily spend an order of 10M floating point operations per frame in RT, which would suggest a dataset of <1000 circles (with the optimized innerloop).

An optimized innerloop would calculate:

(x0-x1)^2 + (y0-y1)^2 < (r0-r1)^2

for every pair of circles, checking if either fully encompasses the other. The formula is quite well suited for parallelism and also the weird cases can be ruled out by increasing a counter for every circle that passes the above test. In the end it should be 1.

Answer 3

Two points:

1. Your algorithm isn't correct as it stands. Consider the circle in this diagram:

   

   The four compass points of the small circle are within the larger circle, but it is not contained by it. This problem can be solved with the better circle-in-circle tests described by Alan and Peter.

2. Your problem description isn't entirely clear. Should the output be:

   1. A list of every pair of circles where the first is contained in the second.
   2. A list of every circle that is entirely overlapped by at least one other.
   3. A list of every circle that is entirely overlapped by some combination of other circles.

   The first of these clearly doesn't have a better worst-case running time than O(N^2) because all the circles might be arranged concentrically, so the first circle contains every other, the second contains every other except the first, etc. and since the output is (N^2) the running time can't be any better.

   The second might have a better worst-case running time, but I'm not too confident of that.

   The third sounds like a nightmare to solve.

If you can guarantee that the amount of overlapping is low then you can probably get a better running time by creating a list of the minimum (leftmost) and maximum (rightmost) x position of each circle and sorting it. Work through the list, adding the circles to the working set as you encounter their left edge and removing them as your encounter their right edge. As each circle is added to the set, compare it with only the other circles currently in the set.

This is still worst-case O(n^2), unless you can make sufficient guarantees about the distribution and size of the circles, but it should be a big step up.

Answer 4

My first impression to see if a circle is inside another would be to know

1. the centre point of the two circles.
2. the two radii of the circles.
3. if C1 to C2 + R2 > R1 then its outside, otherwise its inside.

This should simplify your logic a lot.

Edit: to improve the complexity,

1. order by radius (large to small)
2. first for loop go from large to small
3. second for loop go from large to small
4. once you find a inner circle within the outer you can remove this circle from the outer loop
5. reason is as the first outer circle is encapsulating the this inner circle, you don't care if anything else falls in this circle, only if it is outside the larger one subsequently.

This will get your list of circles which is surrounded by a larger circle.

Answer 5

What are your datasets like? Checking every circle against every other circle is inherently O(n^2), in order to reduce complexity you need some metric to prevent having to check each circle against each other.

There are various broadphase algorithms which may be helpful, depending on the distribution of circles. For example, if the space occupied by circles is much larger than the typical radius and the circles are distributed relatively evenly through that space, spatial partitioning using a quadtree can help minimise checking containment between objects which are distant from each other.

Answer 6

While not an answer to your question you can make the check much faster using the following.

private static boolean isCircleInCircle(Circle a, Circle b) {
    // the circle is inside if the distance between the centre is less than the difference in the radius
    double dx = a.getX() - b.getX();
    double dy = a.getY() - b.getY();
    double radiusDifference = a.getRadius() - b.getRadius();
    // double centreDistance = Math.sqrt(dx*dx + dy+dy);
    // return radiusDifference > centreDistance;
    double centreDistanceSquared = dx*dx + dy+dy;
    return radiusDifference * radiusDifference > centreDistanceSquared;
}

private static boolean isPointInCircle(Point center, int outsideRadius, Point toCheck) {
    // distance between two points is sqrt((x1-x2)²+(y1-y2)²)
    double dx = center.getX() - toCheck.getX();
    double dy = center.getX() - toCheck.getY();
    double distSquared = dx * dx + dy * dy;
    // if the distance is less than the radius, then the point is inside
    return distSquared < outsideRadius * outsideRadius;
}

Note: the first method doesn't need the second any more.