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

[Vic Thompson]

Note : this post is also listed in the BBS "General Airgun Section" : I'm after a quick and easy way of taking Excel data in the form of x and y columns of position of individual shot placement on a Target and coming up with the diameter of the smallest circle that will encompass them all. Is there anything that can be done directly using Excel, or if not, any free Software that is easy to download and use that I can put the coordinates into and get the right answer.

Thanks in advance for any helpful suggestions.

Vic Thompson.

[majex45]

Hi
I have seen an App for the Iphone that will do this from photographs. Unfortunately, I don't know what it was called.
The guy using it took a photo of each of his score cards and the program superimposed them one on each other (correcting for the different centres) and worked out score and group centre. I believe it can do other things as well.
Nothing short of miraculous, as far as I'm concerned.

Skynet is coming.

[Daryll]

You can get something similar for the PC, called "On Target PC"

You take a photo of your group, with a scale of some sort in the photo ( i used a tape measure), then you can enter the calibre and put the relevant circle over your shot holes.... it works out the group size..

You get a 15 day free trial, then its $12 for the basic version

https://ontargetshooting.com/

[Vic Thompson]

thanks for the replies to date but I don't have any shot targets to scan, only a list of numbers on a Spreadsheet. At a pinch I could reproduce the target using Power point but I'd prefer something that took the Excel data and produced a scaled shot spread image, but I can't even find anything suitable to do this at the moment.

Vic Thompson.

[PhatMan]

Vic,

Please have a peek here :

http://ballistipedia.com/index.php?t...ring_Precision

Have fun & a good Bank Holiday

Best regards

Russ

[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.

[BigEars]

This is one of the most interesting thread ever. When I think about it, my head hurts.

[zooma]

This is one of the most interesting thread ever. When I think about it, my head hurts.

Absolutely!

[Turnup]

Me too. The thing about hard mathematical problems is that there is often a simple and elegant solution waiting to be found. When a thing is mathematically true there are many ways to get to the answer.