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

1. ## 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.

2. ## 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

3. ## 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:
`Please Login or Register  to view this content.`

4. ## 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. ## 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.

6. ## 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. ## 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. ## 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. ## 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. ## 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. ## 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

12. ## 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

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

You're welcome.

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

#### 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