Page 1 of 2 12 LastLast
Results 1 to 15 of 30

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

  1. #1
    Join Date
    Aug 2000
    Location
    Crawley, West Sussex, UK
    Posts
    4,661

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

    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.

  2. #2
    Join Date
    Mar 2008
    Location
    Eastbourne
    Posts
    666

    App

    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.

  3. #3
    Join Date
    Apr 2012
    Location
    Ramsey, Cambs
    Posts
    1,819
    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/

  4. #4
    Join Date
    Aug 2000
    Location
    Crawley, West Sussex, UK
    Posts
    4,661
    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.

  5. #5
    Join Date
    Jul 2015
    Location
    Hastings
    Posts
    1,498
    Vic,

    Please have a peek here :

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

    Have fun & a good Bank Holiday

    Best regards

    Russ

  6. #6
    Join Date
    May 2006
    Location
    Morley, Leeds
    Posts
    1,954
    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.

  7. #7
    Turnup's Avatar
    Turnup is offline Dialling code‎: ‎01344
    Join Date
    Nov 2012
    Location
    Crowthorne
    Posts
    5,491
    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.
    True freedom includes the freedom to make mistakes or do foolish things and bear the consequences.
    TANSTAAFL

  8. #8
    Join Date
    Aug 2000
    Location
    Crawley, West Sussex, UK
    Posts
    4,661
    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.

  9. #9
    Turnup's Avatar
    Turnup is offline Dialling code‎: ‎01344
    Join Date
    Nov 2012
    Location
    Crowthorne
    Posts
    5,491
    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?.
    True freedom includes the freedom to make mistakes or do foolish things and bear the consequences.
    TANSTAAFL

  10. #10
    Turnup's Avatar
    Turnup is offline Dialling code‎: ‎01344
    Join Date
    Nov 2012
    Location
    Crowthorne
    Posts
    5,491
    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
    True freedom includes the freedom to make mistakes or do foolish things and bear the consequences.
    TANSTAAFL

  11. #11
    Join Date
    Aug 2000
    Location
    Crawley, West Sussex, UK
    Posts
    4,661
    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.
    Last edited by Vic Thompson; 28-05-2018 at 04:47 PM.

  12. #12
    Turnup's Avatar
    Turnup is offline Dialling code‎: ‎01344
    Join Date
    Nov 2012
    Location
    Crowthorne
    Posts
    5,491
    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.
    True freedom includes the freedom to make mistakes or do foolish things and bear the consequences.
    TANSTAAFL

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

  14. #14
    Join Date
    Mar 2010
    Location
    Rossendale and Formby
    Posts
    5,595
    Quote Originally Posted by BigEars View Post
    This is one of the most interesting thread ever. When I think about it, my head hurts.
    Absolutely!
    Rossendale Target Shooting Club. Every Tuesday and Thursday evening 7 - 10pm.

  15. #15
    Turnup's Avatar
    Turnup is offline Dialling code‎: ‎01344
    Join Date
    Nov 2012
    Location
    Crowthorne
    Posts
    5,491
    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.
    True freedom includes the freedom to make mistakes or do foolish things and bear the consequences.
    TANSTAAFL

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •