Smallest circle around N points

[RWiersma]

I've been asked to determine the diameter of the smallest circle possible that includes all N points on a plane.

It seems like an easy problem, until you experiment with it... then suddenly you notice increased hair-loss, increased caffeine consumption, etc.

I experimented with a handful of ad-hoc solutions, then I googled the issue and discovered the Elzinga-Hearn Algorithm (Link).

I'm in the middle of implementing EHA into a VI, but it seems like the long and complicated road to an easy problem.

Does anyone have any experience or suggestions with this?

[Ben]

Without looking ato our link or thinking about it too much...

Find the distance between all piars of points. Find the the two point with the largest distance. Use "Fit to  sphere" (Z= 0) and it should return the center point and the radius of the circle.

Not sure if that will work...

Ben 

[johnsold]

Interesting problem.

The algorithm seems relatively straightforward except for the extreme cases.  I would accelerate the process by starting with the points which have minimum and maximum values of x and y, or values near to those. If your coordinates are in arrays, LV makes it easy to find these.   It seems likely that the points with extreme coordinates are close to the circle.

Lynn 

[RWiersma]

Ben,

Thank you for the reply. Your response was my the same as my first reaction, too.

That method is easily beaten, however, with the following dataset: 

The farthest two points are (0,1) and (0,-1). They have a spread of 2. The center of those two points is (0,0), and the inclusive circle would have a radius of 1. I didn't draw the circle on the chart, but you can see that the right-most edge of the circle would intersect (1,0), which is shy of the (1.5,0) point.

Message Edited by RWiersma on 01-29-2010 02:18 PM

[JÞB]

---

Ben wrote:

Without looking ato our link or thinking about it too much...

Find the distance between all piars of points. Find the the two point with the largest distance. Use "Fit to  sphere" (Z= 0) and it should return the center point and the radius of the circle.

Not sure if that will work...

Ben 

---

Won't work-  points not  the line you defined have a sin component in their distance relationship from the endpoints L1, L2.  Imagine Point S that is equidistant from L1 and L2. (on a line orthagonal to your line crossing the mid-point)  the Length boundary specified (Diameter of your circle will not be violated until point s is 1/2^-2 times your circle radius.

[JÞB]

I offered criticism of an approach earlier---- Now that I'm home my mind can freely wander through the tangle of this issue and, if it leads to no conclusion so be it! Musings

• A) The smallest possible Circle MUST contain at least Two Points But they need not share a line where the midpoint of the line is the circle's origin (only in the case where MORE than two points are equidistant from the origin.)
  • Given A all points that are on the smallest possible circle are equidistant from each other when, and only when exaclty 3 points are on the circumfrence of the circle.

So, we have at least 2 "special" cases

1. Where the distibution is oblong along the major axis defined by the the two points with the greatest distance between them  (and the smallest circle will fit Ben's proposed method - 'Tis good to look for "special" cases-- they can save programming cost)  
2. Where the distribution is oblong along the major axis passing through any point on the circle and the midpoint of two other points that are:
   1.  each equidistant from the first.OR
   2. close enough to in-line that the circle is large compared to the distibution (e.g if three points on a distrubution boundry (Have = max x or y) NO circle can be constructed with all three pointsAnd we revert to SC 2.1

Hmmmm mulling

Back to it later

Message Edited by Jeff Bohrer on 01-29-2010 04:34 PM

Message Edited by Jeff Bohrer on 01-29-2010 04:38 PM

Message Edited by Jeff Bohrer on 01-29-2010 04:40 PM

[JÞB]

Find the Min and Max of the CONSTELATION [C]

Find any arbitrary Point O such that point OsubX and Point OsubY are <min[C]] and min[C] And -Osubx and-OsubY are > max[C]] and max[C] (Put the constelation in the first Quadrant of a Cartesian plane)

Rotate O with respect to the mean XY of [C] measure Rho[C] & Theta[Max&min] for each O (moving in a circle about the geometrical mean of the constellation) 

For each Angle of O-[C] Measure the Min and Max. you can extract the Rho Theta and solve for the hypotenuse (A^2+B^2=C^2) {or, the Distance between your instantaineous axis of investigation}

The Max [IAI] (instantaneous Axis of Investigation) is the diameter of the smallest circle that contains all of constellation [C]

QED 

Proof is left to the student as practice

[JÞB]

---

Jeff Bohrer wrote:

Find the Min and Max of the CONSTELATION [C]

Find any arbitrary Point O such that point OsubX and Point OsubY are <min[C]] and min[C] And -Osubx and-OsubY are > max[C]] and max[C] (Put the constelation in the first Quadrant of a Cartesian plane)

Rotate O with respect to the mean XY of [C] measure Rho[C] & Theta[Max&min] for each O (moving in a circle about the geometrical mean of the constellation) 

For each Angle of O-[C] Measure the Min and Max. you can extract the Rho Theta and solve for the hypotenuse (A^2+B^2=C^2) {or, the Distance between your instantaineous axis of investigation}

The Max [IAI] (instantaneous Axis of Investigation) is the diameter of the smallest circle that contains all of constellation [C]

QED 

Proof is left to the student as practice

---

The Max IAI describes a Chord though the circle

The Mean of the The angle Max and Min for THAT chord will contain the origin of the smallest crcle

[JÞB]

To conclude:

Let [C] be a constellation of Points

Let M be an arbitray point within [C] 

Let [D] be the distance from M to each point in [C]

let O be an arbitrary point with a distance from M greater than Max[D]

Rotate O around M 180 Deg obvsere the Max Delta Theta O to[C]

if and only if the two extremele angle points are equidistant from O describe a line bisecting the chord between the two extreem points. and note the distance between the extreem points [Dea].  The endpoints gatherd in this step will contain ALL of the points on the desired circles circumferance(and posibly a few others)

Sort the array of distances in decending order.  There will be a single of intersection of the Lines bisecting the chords And all enpoints that are on the circle's circumferance will be equidistant from one of this intersection.  The The equidistance test for contstucting the test origin line will  remove all trivial intersections and there will be more than 1 chord described UNLESS only two points are on the circumferance. (special case 1) but that chord will be a diameter of the circle.

 For instance points on the circumferance at 1, -1 and 180 deg will yield two chords of length nearly = to Diameter.   

[RWiersma]

Jeff,

Thank you for the informative post. I'm working to make a VI implementation of your notes, as we speak.

I'm not entirely sure I follow what you've written, but I'm working through it. I think it's going over my head, but I'm looking for a taller ladder. 🙂

Thanks again.

-RW

PS: Where does this information originate?