Finding by Algorithm the smallest circle that will encompass a group of shots

[Adam77K]

I don’t think there’s going to be a solution you can express in a single excel formula. It will have to be some quite heavy coding which you could do in VBA (is that still a thing these days?)

Some discussion on stack overflow.
https://stackoverflow.com/questions/...-other-circles

I like programming puzzles. Maths ones, not so much. This is both.

It would be quite straightforward to find the smallest circle centred on the origin that would encompass the centres (points). Then as all circles are the same diameter just add this to the total. But this doesn’t find your solution if the group is offset.

Interesting puzzle though, good luck.

[Turnup]

Presume you have x,y values for each shot from an arbitrary origin

1) calculate the straight line distance between each shot and all of the others (that's 9 + 8 + 7....) values. Probably easiest using rectangular notation by simply subtracting x from x and y from y and then converting each value into polar notation.

2) Find the three largest values of magnitude (disregard the angle)

3) these three shots form the vertices of a triangle

4) The centre of the triangle is the centre of the shot group (classical geometry)

5) Calculate the circle which will circumscribe the triangle (classical geometry)

6) correct the circle size to allow for the diameter of each shot hole. (I think in practice it is only necessary to consider the shot which is furthest from the circle centre - any circle that encloses the outside edge of this shot must also enclose the outside edge of the others.....I think)

You now have the centre and size of the smallest circle which will encompass all shots.

[Vic Thompson]

thanks for the info to date, I'm reading up on source material and setting up a simple ? Spreadsheet to run through Turnup's suggested solution.

Vic Thompson.

[Turnup]

Upon reflection I don't think step 5 above is correct. I can visualise some groups where the circle would be far too large.

In fact I think the centre of the group can be found more easily by calculating the x,y of the average of all the shot points - this would be easy but is it the centre of the smallest circle?.

[Turnup]

Erk! It seems that this problem has been exercising mathematicians and so for no linear solution has been found. All present methods use iterative algorithms (using a guess to find a better guess until no further improvement can be made). There are algorithms of varying complexity and which take more or less time to find the solution but I don't think any of these can be implemented in a straight spreadsheet - needs programming.

Take a look here

http://www.delphiforfun.org/programs...ing_points.htm

[Vic Thompson]

thanks for the further reply Turnup, I more or less came to the same conclusion as yourself at aroundabouts the time of your latest posting.

I spent hours today working through your suggestions, checking several times that I was using the right aproach (mathematically speaking), but always ending up with the same result, it's a covering circle but not the guaranteed minimum one (then I rushed off to Tesco for an infrequent shopping trip in an attempt to beat the Bank Holiday Monday "last minute closing rush").

I have seen various discussions on the matter, all allude to a complex solution (in my simpleton view : think of an answer, see how good it is, rely on history, think of a better answer, ditto, ad infinitum). Not easy to do in Excel without a sophisticated Macro (one discussion of the problem suggested that 400 to 500 lines of code would be needed in a routine to establish a viable solution to the problem).

Based on my working through your suggested approach, I wondered if I had calculated the "wrong centre" of the triangle as even this "simple definition" is manifold (as it seems to be an open ended definition with multiple answers).

I'm always hopefull and appreciate yours and other informative suggestions as to which way to proceed Excelwise.

Vic Thompson.

[Turnup]

I should have been more precise - the centre I was thinking of is the intersection of the perpendicular bisectors for each side. This finds the point which is the centre of a circumscribing circle. As you say there are other centres, and anyway it is certainly not the correct solution <sigh>.

Coming back to my other idea, take the average of all points. I feels like at least it would be an easy way to make a first guess for an iterative algorithm. In fact without trying it, it feels like the centre of the group would lie on a line passing through the furthest outlying point and the average point.

WRT macros - could be done but don't think this is the most appropriate tool for the job - hard work - embedded VB would be fine.