tags:

views:

711

answers:

9

If a circle is defined by the X, Y of it's center and a Radius, then how can I find a Circle that encompasses a given number of circles? A single circle that is the smallest possible circle to completely contain 2 or more circles of any size and location.

At first I tried just encompassing 2 circles by finding the midpoint of the centers and that being the midpoint of the new circle while the radius was equal to the half of the radius of the 2 initial circles and half the distance between their centers, but somehow it always turned out to be a little off. The problem always seemed to be a problem with finding the radius, but I have such a headache about this I can't make it work.

I don't necessarily need a method for finding a circle that encompasses 3 or more circles. I can find a circle that encompasses 2, take that circle and encompass it with another, and another, and the final circle should encompass all circles given throughout the steps.

+5  A: 

Its termed Minimum Enclosing Circle ("MEC"), or sometimes "smallest enclosing circle".

A nice site: http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/Center/centercli.htm

Will
I think it's not exactly what he's looking for: MEC looks for the smallest circle that contains a (finite) set of points. He looks for a circle that contains other circles. It's probably a good starting point, though.
nikie
I'm not sure that will work here? The OP wants to enclose circles which, unlike "big points", could each have a different radius.
thekindamzkyoulike
I've implemented MEC for http://www.azspcs.net/Contest/PointPacking/ so can say that it is definitely translatable to this problem; the programmer will have to take acount for different sized circles, obviously
Will
I'm curious: Finding a circle through 3 points is pretty simple, but finding a circle that touches 3 other circles yields a system of 3 quadratic equations, and my computer algebra system can't find a solution for it. What makes you so sure MEC can be simply translated to this problem? Also, IIRC MEC can be simplified by just looking at the points on the convex hull. That won't work with circles.
nikie
The MEC algorithms work by taking a large bounding circle and shrinking it. You can represent the circles not as points representing their centres but as points on their perimeter; you could simply use points at sufficiently small distances apart, or you could do the maths to put the point on the furthest point of the perimeter from the centre of the bounding circle, etc.
Will
+1  A: 

Just understand the equations of the circle and derive an equation (or a series) for find the answer then start implementing. Perhaps we will be able to help you in that given you have done something.

Chathuranga Chandrasekara
+4  A: 

Given two circles, with centers [x1,y1], [x2,y2], and radii R1 and R2. What is the center of the enclosing circle?

Assume that R1 is no larger than R2. If the second circle is the smaller, then just swap them.

  1. Compute the distance between centers of the circles.

    D = sqrt((x1-x2)^2 + (y1-y2)^2)

  2. Does the first circle lie entirely inside the second circle? Thus if (D + R1) <= R2, then we are done. Return the larger circle as the enclosing circle, with a center of [x1,x2], with radius R2.

  3. If (D+R1) > R2, then the enclosing circle has a radius of (D+R1+R2)/2

In this latter case, the center of the enclosing circle must lie along the line connecting the two centers. So we can write the new center as

center = (1-theta)*[x1,y1] + theta*[x2,y2]

where theta is given by

theta = 1/2 + (R2 - R1)/(2*D)

Note that theta will always be a positive number, since we have assured that (D+R1) > R2. Likewise, we should be able to ensure that theta is never larger than 1. These two conditions ensure that the enclosing center lies strictly between the two original circle centers.

woodchips
whilst the two circle case is trivial, it does not extrapolate to efficiently finding the centre of N circles.
Will
I agree that this algorithm need not extend to n circles. However, the direct question was for a minimal circle that encloses two circles.
woodchips
Agreed, it was the OP who was imagining a 2-circle solution easily efficiently extended to N :)
Will
+2  A: 

I'm going to recommend against this, now
See the discussion below.

Original thoughts

I would consider an iterative push-pull method.

  1. Guess where to put the center (simplest would be the mean position of all centers)
  2. Compute the vectors to the farthest point on each circle. These are always in the direction to the center of that circle and have length distance_to_center_of_circle[i]+radius_of_circle[i] and form the vector sum as you go. Also note that the necessary radius at the current location is the maximum of these lengths.
  3. Propose a step of (say) 1/5 or 1/10 of the vector sum from 2, and redo the computations from 2 for the new point
  4. If the new point needs a smaller circle than the old, make the new point the current point, otherwise, split the difference, reduce the size of the proposed step (say half it).
  5. goto 3

You're done when it stops[+] converging.

Nikie poked at it until...

As requested clarifying step two. Call the position to be tested \vec{P} (a vector quantity).[++] Call the centers of each circle \vec{p}_i (also vector quantities) and the radius of each circle is r_i. Form the sum \sum_i=1^n \hat{p_i - P}*|(p_i-P)|+r_i).[+++] Each element of the sum points in the direction from the current evaluation point towards the center of the circle in question, but is longer by r_i. The sum itself it a vector quantity.

The radius R need to enclose all the circle from P is the max(|p_i-P|_r_i).

Pathological case

I don't think the particular case nikie's brought up is a problem, but it has put me onto a case where this algorithm fails. The failure is one of failing to improve a solution, rather than one of diverging, but still...

Consider four circles all of radius 1 positioned at

(-4, 1)
(-5, 0)
(-4, 1)
( 5, 0)

and a starting position of (-1, 0). Symmetric by design so that all distances lie along the x axis.

The correct solution is (0, 0) with radius 6, but the vector calculated in step 2 be about ::calculates furiously:: (-.63, 0), pointing in the wrong direction resulting in never finding the improvement towards the origin.

Now, the algorithm above would actual pick (-2, 0) for the starting point, which gives an initial vector sum of ::calculates furiously:: about +1.1. So, a bad choice of step size on (3) would result in a less than optimal solution. ::sigh::

Possible solution:

  • In (3) throw a random fraction between (say +1/5 and -1/5) possibly weighted towards the positive size.
  • In (4) if the step is rejected, simply return to step three without altering the step size limits.

However, at this point it is not much better than a pure random walk, and you don't have an easy condition for knowing when it has converged. Meh.

[+] Or slows to your satisfaction, of course. [++] Using latex notation. [+++] Here \hat{} means the normalized vector pointing in the same direction as the argument.

dmckee
+1 for a concrete and vivid suggestion. I think there are cases where it might not converge to the optimal solution, because 2 circles are equally far from the current center, and moving the center to either one will increase the radius. (Imagine finding the circle for 3 center points that form an obtuse, isocles triangle)
nikie
@nikie I'm having a hard time convincing myself either way. If it *can* get stuck you could take a Monte Carlo approach to shaking it loose. Whether that is worth it or not depends on how badly you really need the minimum.
dmckee
@dmckee: To convince yourself, draw two points A and B, 3 units apart. Then draw a circle with a radius of 2 units around each point. Call one of the circle-circle intersection points C. Imagine A and B are given input points and C is the current estimated center. Obviously C is not optimal. But all points between C and A are outside the circle around B, so moving towards A will move the center farther away from B, so it would increase the radius. (and vice versa for B). Thus, the algorithm would terminate.
nikie
@nikie I don't think this case is a problem. The vector sum in step 2 now points in the direction of D at the center of AB, so I believe it keeps working in the right direction. The place it might get stuck is if there are two, non-equivalent local minima. (The algorithm I adapted this from is fairly robust (though we use it on noise data which does admit pathological cases).)
dmckee
@dmckee: I think I misunderstood your algorithm. Could you clarify step (2)? If you simply add up all the vectors from the current center location to the input center points, how would this ever converge? (For example, assume all radii are 0. You start with the mean position. If you take the vector sum from the mean position to each of the input points, you will always get 0.)
nikie
@dmckee: First, in response to your clarification: take \sum_i=1^n \hat{p_i - P}*|(p_i-P)|+r_i). If r_i=0, then the expression reduces to \sum_i=1^n (p_i - P). Convergence is reached if this expression is 0. This is the case if P is the mean over p_i.
nikie
But you can easily fix this. Roughly speaking: Start at an arbitrary location, and move in the direction of the tangent point that has the maximum distance. (That's how I misread your algorithm at first). You need some special handling when there's more than one point with maximum distance.
nikie
@nikie: Nice. The special handling might be to use the vector sum of the offending direction.
dmckee
A: 

So if you don't need the exact circle this approximation might do.

  1. Take the average of all your centers of the circles call this point X
  2. Let R1 be the maximum distance from X to a circle center.
  3. Let R2 be the maximum radius of the circles

The all the circles must fall inside the circle centered at X with radius R1+R2

Michael Anderson
-1: Will not give the *smallest* possible circle.
kigurai
Indeed it wont, but it is likely to give a better result than the iterative method outlined in the last paragraph of the OP. Hence my assumption that an easy but inexact method would be acceptable.
Michael Anderson
A: 
  1. Average the centres of each circle to find the centre of the encompassing circle.

  2. For each circle, take the distance from the centre to the centre of the encompassing circle. Add the radius of the circle.

  3. Find the maximum of those distances, that's the radius of the encompassing circle.

Cameron MacFarland
Thanks for the -1 vote. Care to comment on why I got it?
Cameron MacFarland
I didn't downvote, but your suggestion is simply wrong. The question wasn't how to find **any** encompassing circle, but **the smallest possible** circle.
nikie
This produces an encompassing circle, but not necessarily the smallest encompassing circle, which is the difficult part of the problem. Try a few cases with at least three circles with different radii and it will become quite obvious.
kigurai
In fact, it won't even find the optimal solution for two or three circles, if they don't have the same radius.
nikie
+1  A: 

Since my inexact solution was not liked. Heres a way to get the exact solution. But its slow ( O(N^4)? ) and computationally nasty. (Unlike the inexact method)

First you need to know that given three circles we can find a circle tangential to them all than contains all three. This is one of the circles of Apollonius. You can get the algorithm from mathworld.

Next you can show that the smallest enclosing circle for N circles is tangential to at least 3 of the N circles.

To find this circle we do the following

  1. loop through all triples of circles - O(N^3)
  2. find the enclosing Apollonius circle of those 3 circles - computationally nasty
  3. if it encloses all the circles add it to a list of potentials - check is O(N)
  4. Solution is potential with smallest radius

There may be some tricks to speed this up, but it should give you the exact solution. Some of the "tricks" for getting Smallest Enclosing Circle algorithms to linear time may be applicable here, but I suspect they would not be trivial adaptions.

Michael Anderson
Oops made an error in here, to smallest circle enclosing three circles is either, one of the circles (if the others are contained in it), a circle tangential to two of them (if the other is contained within this circle) or a circle tangential to all three (an Apollonius circle). Note that this doesn't effect the running time, but does change step 2 slightly.
Michael Anderson
+1 for the mathworld link.
nikie
+1  A: 

I've taken what some of you had to say and here's the solution I discovered:

public static Circle MinimalEnclosingCircle(Circle A, Circle B) {
            double angle = Math.Atan2(B.Y - A.Y, B.X - A.X);
            Point a = new Point((int)(B.X + Math.Cos(angle) * B.Radius), (int)(B.Y + Math.Sin(angle) * B.Radius));
            angle += Math.PI;
            Point b = new Point((int)(A.X + Math.Cos(angle) * A.Radius), (int)(A.Y + Math.Sin(angle) * A.Radius));
            int rad = (int)Math.Sqrt(Math.Pow(a.X - b.X, 2) + Math.Pow(a.Y - b.Y, 2)) / 2;
            if (rad < A.Radius) {
                return A;
            } else if (rad < B.Radius) {
                return B;
            } else {
                return new Circle((int)((a.X + b.X) / 2), (int)((a.Y + b.Y) / 2), rad);
            }
        }

Circle is defined by the X, Y of it's center and a Radius, all are ints. There's a constructor that is Circle(int X, int Y, int Radius). After breaking out some old trig concepts, I figured the best way was to find the 2 points on the circles that are farthest apart. Once I have that, the midpoint would be the center and half the distance would be the radius and thus I have enough to define a new circle. If I want to encompass 3 or more circles, I first run this on 2 circles, then I run this on the resulting encompassing circle and another circle and so on until the last circle is encompassed. There may be a more efficient way to do this, but right now it works and I'm happy with that.

I feel weird answering my own question, but I could not have come to this solution without everybody's ideas and links. Thanks everybody.

Corey Ogburn
Actually I tested this for: Circle(25,30,20) and Circle(45,30,40) and it just returns the second Circle (which is incorrect).
Chris Redford
I'm not sure how you came to that, I created those 2 circles and the circle that's returned for me is Circle(45, 29, 40). It's integer math which explains why it's slightly off, but this is correct. Please take a look at my project at http://coreyogburn.com/page/Circle-Library.aspx to see the implementation I'm testing with. If you still see a problem, please let me know there or here.
Corey Ogburn
Never mind. The problem was the drawing program I was using. It was halving the radii of the circles. Circle(45, 30, 40) is indeed a correct Circle. Sorry about the confusion.
Chris Redford
I appreciate the double check.
Corey Ogburn
A: 

This is not a trivial problem. I haven't read all the answers above, so if I repeat what someone has already said, the fault is mine.

Each circle c_i is defined by 3 parameters x_i,y_i,r_i

3 parameters need to be found x*,y*,r* for the optimal circle C*

C* is such that it contains c_i for all i

Let d_i = ||(x,y)-(x_i,y_i)|| + r_i

Then if r is radius of a circle that contains all c_i, then r >= d_i for all i

We want r to be as small as possible

So, r* = max(d_i)

Thus we want to minimize the max of d_i

So (x*,y*) are given by the arg min of max(d_i). And once (x*,y*) are found, r* can be readily computed and will equal max(d_i). This is a minimax problem.

To make things easier to understand consider just 2 circles, how can we find (x*,y*)?

(x*,y*) can be found by finding the (x,y) that minimize (d_1 - d_2)^2. In the general case

let e_ij = (d_i - d_j)^2

Then define e = \sum e_ij for i != j (there are n Choose 2 terms in this sum)

(x*,y*) = arg min of e

And this is what needs to be solved for.

Tip: if r_i = 0 for all i, then this reduces to the traditional minimum enclosing circle problem when the input is a bunch of points, and we want to find minimum circle that covers all of them.

morpheus