+ Reply to Thread
Results 1 to 14 of 14

Find Diameter of Circle that Encompasses Points in a X-Y Coordinate Chart

  1. #1
    Registered User
    Join Date
    11-22-2019
    Location
    Illinois
    MS-Off Ver
    Excell 2013
    Posts
    9

    Find Diameter of Circle that Encompasses Points in a X-Y Coordinate Chart

    If I have a list of X and Y coordinates how can I find the minimum diameter of a circle that encompasses all points?

    x(") y(") Point

    1.81 2.57 1
    0.66 0.46 2
    0.24 0.9 3
    -0.8 0.59 4
    2.54 2.92 5

    For example here is a list of five points each defined by its X and Y coordinates. I want to find the diameter of the smallest circle that would have all points either touching or inside the circle.

    Thanks in advance for any help you can provide.

  2. #2
    Forum Expert
    Join Date
    12-14-2012
    Location
    London England
    MS-Off Ver
    MS 365 Office Suite.
    Posts
    8,448

    Re: Find Diameter of Circle that Encompasses Points in a X-Y Coordinate Chart

    You only need three points to define a circle.

    http://www.ambrsoft.com/TrigoCalc/Circle3D.htm
    My General Rules if you want my help. Not aimed at any person in particular:

    1. Please Make Requests not demands, none of us get paid here.

    2. Check back on your post regularly. I will not return to a post after 4 days.
    If it is not important to you then it definitely is not important to me.

  3. #3
    Administrator 6StringJazzer's Avatar
    Join Date
    01-27-2010
    Location
    Tysons Corner, VA, USA
    MS-Off Ver
    MS365 Family 64-bit
    Posts
    24,532

    Re: Find Diameter of Circle that Encompasses Points in a X-Y Coordinate Chart

    First determine a rectangle that encloses all points. This can be done by finding the minimum and maximum values of x and y.

    A circle circumscribed around the rectangle will be the smallest circle that can enclose all points. This circle will have a diameter that is equal to a diagonal of the rectangle.

    The diagonal of the rectangle can be calculated as the distance between two opposite corners.

    If x values are in column A and y values are in column B, this formula gives the diameter:

    Formula: copy to clipboard
    Please Login or Register  to view this content.
    Last edited by 6StringJazzer; 11-22-2019 at 04:31 PM.
    Jeff
    | | |會 |會 |會 |會 | |:| | |會 |會
    Read the rules
    Use code tags to [code]enclose your code![/code]

  4. #4
    Administrator 6StringJazzer's Avatar
    Join Date
    01-27-2010
    Location
    Tysons Corner, VA, USA
    MS-Off Ver
    MS365 Family 64-bit
    Posts
    24,532

    Re: Find Diameter of Circle that Encompasses Points in a X-Y Coordinate Chart

    I have taken a second look at this and determined that my solution will give a circle that ecompasses all points, but not necessary the smallest circle that will do so.

  5. #5
    Forum Guru
    Join Date
    04-13-2005
    Location
    North America
    MS-Off Ver
    2002/XP and 2007
    Posts
    15,803

    Re: Find Diameter of Circle that Encompasses Points in a X-Y Coordinate Chart

    How much of this is geometry, how much is algorithm development, and how much is actually specific to Excel? I put "smallest circle that encloses a list of x y points" into my favorite search engine, and found this page on Wikipedia that seems to describe the problem: https://en.wikipedia.org/wiki/Smallest_circle_problem A list of algorithms is given (most of them appear to be various "trial and error" looping algorithms). I did not look at them in any detail, since I don't know if you are already familiar with these or not or exactly what help you would need to implement any of them.
    Quote Originally Posted by shg
    Mathematics is the native language of the natural world. Just trying to become literate.

  6. #6
    Registered User
    Join Date
    11-22-2019
    Location
    Illinois
    MS-Off Ver
    Excell 2013
    Posts
    9

    Re: Find Diameter of Circle that Encompasses Points in a X-Y Coordinate Chart

    Perhaps I've underestimated the complexity of this problem. I've read the Wikipedia link and though it describes the problem it leaves my head spinning trying to understand the solutions or how they might be implemented in Excel.

    As to "How much of this is geometry, how much is algorithm development, and how much is actually specific to Excel?" I had no clue. It now seems more related to geometry / algorithm then Excel. Being new to this forum I don't know if that makes my question inappropriate on this forum (?).

    I appreciate all your responses and still hope there's a solution out there.

  7. #7
    Administrator 6StringJazzer's Avatar
    Join Date
    01-27-2010
    Location
    Tysons Corner, VA, USA
    MS-Off Ver
    MS365 Family 64-bit
    Posts
    24,532

    Re: Find Diameter of Circle that Encompasses Points in a X-Y Coordinate Chart

    Can you tell us why you need to do this? Sometimes people need to get rid of ice so they ask how to make an ice pick, and we figure out they really need a blowtorch.

  8. #8
    Registered User
    Join Date
    11-22-2019
    Location
    Illinois
    MS-Off Ver
    Excell 2013
    Posts
    9

    Re: Find Diameter of Circle that Encompasses Points in a X-Y Coordinate Chart

    Sure, the X,Y coordinates are points of impact on a target. The smallest-circle is known in the shooting sports as the group size of a string of shots.

    It's useful in determining the combination of powder type, powder charge, bullet design and weight, primer, and a host of other variables in developing a cartridge that performs best in a specific firearm.

    I want the group size reported to 2 decimal places.

  9. #9
    Forum Guru
    Join Date
    04-13-2005
    Location
    North America
    MS-Off Ver
    2002/XP and 2007
    Posts
    15,803

    Re: Find Diameter of Circle that Encompasses Points in a X-Y Coordinate Chart

    If for a competition or something, where someone will hate you all year for giving the turkey/prize to the wrong competitor because you calculated the group size wrong, then you probably do need a robust algorithm.

    What's the maximum number of shots that will ever be considered? Part of the complexity in the Wikipedia solutions is that the Wikipedia article focuses on efficient algorithms, but your sample problem only has 5 points. With so few points, we don't need the most efficient possible algorithms like we would if there were hundreds or thousands of points. Any of the simpler but less efficient algorithms will do just fine for 5 or so points.

    I searched the internet again for "smallest circle problem calculator" and found this page: http://personal.kent.edu/~rmuhamma/C.../centercli.htm The proposed O(n^2) time algorithm from this page looks like it would be easy enough to implement.
    This one has several implementations that may work. Unfortunately, VBA being a dying language, it does not get a mention: https://www.nayuki.io/page/smallest-enclosing-circle Follow through to the pdf that is a slideshow from a lecture describing the algorithms. If you are not required to use Excel or other spreadsheet for this, one of those preprogrammed calculators (if you trust the page author to get it right) might be easier than figuring this out in Excel/VBA.

  10. #10
    Registered User
    Join Date
    11-22-2019
    Location
    Illinois
    MS-Off Ver
    Excell 2013
    Posts
    9

    Re: Find Diameter of Circle that Encompasses Points in a X-Y Coordinate Chart

    This will be a part of a larger spreadsheet I'm working on. The max points I envision is 30, but far more likely to be 5 or 10. This will be for me and a few friends, not even a turkey at stake.

    Thanks for the links. It may be a couple days before I can take time to digest the info.

    Decades ago I did some Fortran and extensive programming in Applesoft Basic. Nothing in VBA, so I'll be starting at ground zero.

  11. #11
    Forum Expert shg's Avatar
    Join Date
    06-20-2007
    Location
    The Great State of Texas
    MS-Off Ver
    2003, 2010
    Posts
    40,678

    Re: Find Diameter of Circle that Encompasses Points in a X-Y Coordinate Chart

    Here's a hack. There are linear-time (O(n)) algorithms; I used a brute-force O(n^4) one. Still, it ratchets through 30 shots at interactive rates.

    B
    C
    D
    2
    ctrx
    ctry
    radius
    3
    -0.06
    1.19
    5.95
    4
    5
    Shot
    x
    y
    6
    1
    3.8
    2.4
    7
    2
    -1.2
    3.0
    8
    3
    -2.8
    -2.4
    9
    4
    -2.4
    1.5
    10
    5
    -4.7
    2.5
    11
    6
    -5.0
    2.1
    12
    7
    0.3
    3.7
    13
    8
    0.9
    3.6
    14
    9
    -2.2
    1.1
    15
    10
    1.6
    0.8
    16
    11
    -1.1
    -3.4
    17
    12
    -0.9
    -4.7
    18
    13
    4.3
    2.1
    19
    14
    3.9
    -2.9
    20
    15
    -3.3
    3.8
    21
    16
    0.3
    -0.8
    22
    17
    -1.6
    0.3
    23
    18
    -4.1
    2.5
    24
    19
    -5.0
    4.5
    25
    20
    4.4
    2.0
    26
    21
    1.8
    -1.5
    27
    22
    3.2
    1.2
    28
    23
    0.3
    4.4
    29
    24
    -0.1
    3.6
    30
    25
    5.0
    4.3
    31
    26
    2.4
    2.2
    32
    27
    1.1
    -4.3
    33
    28
    2.2
    -3.0
    34
    29
    -2.7
    -0.5
    35
    30
    -2.2
    4.0
    Attached Files Attached Files
    Last edited by shg; 11-24-2019 at 06:17 PM. Reason: Better B27 pic
    Entia non sunt multiplicanda sine necessitate

  12. #12
    Registered User
    Join Date
    11-22-2019
    Location
    Illinois
    MS-Off Ver
    Excell 2013
    Posts
    9

    Re: Find Diameter of Circle that Encompasses Points in a X-Y Coordinate Chart

    That looks perfect for my needs. And graphed on a B27C too.

    Now I just need to learn how to incorporate into my spreadsheet.

    Thank You! And thanks to all of you helping me.
    Tom

  13. #13
    Forum Moderator AliGW's Avatar
    Join Date
    08-10-2013
    Location
    Retired in Ipswich, Suffolk, but grew up in Sawley, Derbyshire (England)
    MS-Off Ver
    MS 365 Subscription Insider Beta Channel v. 2404 (Windows 11 22H2 64-bit)
    Posts
    79,369

    Re: Find Diameter of Circle that Encompasses Points in a X-Y Coordinate Chart

    If that takes care of your original question, please select Thread Tools from the menu link above and mark this thread as SOLVED.
    Ali


    Enthusiastic self-taught user of MS Excel who's always learning!
    Don't forget to say "thank you" in your thread to anyone who has offered you help.
    You can reward them by clicking on * Add Reputation below their user name on the left, if you wish.

    Forum Rules (updated August 2023): please read them here.

  14. #14
    Forum Expert shg's Avatar
    Join Date
    06-20-2007
    Location
    The Great State of Texas
    MS-Off Ver
    2003, 2010
    Posts
    40,678

    Re: Find Diameter of Circle that Encompasses Points in a X-Y Coordinate Chart

    You're welcome.

+ Reply to Thread

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Similar Threads

  1. Replies: 1
    Last Post: 02-22-2017, 01:46 PM
  2. How to draw circle and points (from x-y data)
    By Hrki87 in forum Excel General
    Replies: 2
    Last Post: 10-31-2014, 04:42 AM
  3. Equation for a circle given 3 points
    By rlawler in forum Excel General
    Replies: 6
    Last Post: 09-01-2014, 11:33 PM
  4. Circle within Circle Chart
    By meetukalra in forum Excel Charting & Pivots
    Replies: 5
    Last Post: 07-18-2014, 06:47 AM
  5. Formula for calculating Mid Point between two points in the Circle
    By rcmanivannan in forum Excel Formulas & Functions
    Replies: 7
    Last Post: 07-08-2013, 08:20 AM
  6. [SOLVED] Calculating distant between two coordinate points
    By nyen in forum Excel General
    Replies: 3
    Last Post: 04-16-2012, 05:58 AM
  7. How do I set up a circle within a circle chart?
    By Ken in forum Excel Charting & Pivots
    Replies: 3
    Last Post: 08-04-2006, 07:45 AM

Bookmarks

Posting Permissions

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

Search Engine Friendly URLs by vBSEO 3.6.0 RC 1