+ 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
    5

    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
    6,759

    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
    Please Avoid Joining My List Of Blocked Users by:

    Saying Please and Thank you.

    Making requests not demands.

    Checking back on your post. I will not edit any post after 4 days.

    Marking threads as closed once your issue is resolved. How? The tools at the top

    Any reputation (*) points appreciated. None of us gets paid here.

    If you found someone's input useful, please take a second to click the * at the bottom left to let them know

  3. #3
    Forum Moderator 6StringJazzer's Avatar
    Join Date
    01-27-2010
    Location
    Tysons Corner, VA, USA
    MS-Off Ver
    Pro 2019
    Posts
    15,159

    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.
    Making the world a better place one fret at a time | | |會 |會 |會 |會 | |:| | |會 |會
    Please read the rules
    If someone helped you, click on the star icon at the bottom of their post
    If your problem is solved, go to Thread Tools and select Mark This Thread Solved
    Don't attach a screenshot--just attach your Excel file! It's easier and will let us experiment with your data, formulas, and code.

  4. #4
    Forum Moderator 6StringJazzer's Avatar
    Join Date
    01-27-2010
    Location
    Tysons Corner, VA, USA
    MS-Off Ver
    Pro 2019
    Posts
    15,159

    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
    11,448

    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
    5

    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
    Forum Moderator 6StringJazzer's Avatar
    Join Date
    01-27-2010
    Location
    Tysons Corner, VA, USA
    MS-Off Ver
    Pro 2019
    Posts
    15,159

    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
    5

    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
    11,448

    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
    5

    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 Guru shg's Avatar
    Join Date
    06-20-2007
    Location
    The Great State of Texas
    MS-Off Ver
    2003, 2010
    Posts
    40,539

    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
    5

    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
    Ipswich, England
    MS-Off Ver
    Excel 2019 (Win 10 - Work) & 365 Subscription (Win 10 - Home)
    Posts
    32,777

    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!

    Forum Rules (updated September 2018): please read them here.
    How to use the Power Query code you've been given: help here. More about the Power suite here.
    Don't forget to say "thank you" to those who have helped you in your thread. If you wish, you can also reward them by clicking on their reputation star bottom left.

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

    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)

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