**Edited by BluePhase, 24 October 2012 - 01:48 PM.**

**1**

# Detecting a radius based on coordinates?

###
#1
Members - Reputation: **147**

Posted 24 October 2012 - 01:47 PM

###
#2
Members - Reputation: **3352**

Posted 24 October 2012 - 02:52 PM

All you need to do for that is loop through all of the points and find the point that has the furthest distance from the center. That distance is the radius of the sphere.

###
#4
Crossbones+ - Reputation: **7121**

Posted 12 November 2012 - 04:45 PM

*I don't suffer from insanity, I'm enjoying every minute of it.*

The voices in my head may not be real, but they have some good ideas!

The voices in my head may not be real, but they have some good ideas!

###
#5
Crossbones+ - Reputation: **16845**

Posted 12 November 2012 - 05:14 PM

The basic algorithm that comes to mind takes time O(N^5) to run. The solution sphere will either touch two points (which will be diametrically opposed), or three points (which will be on the same plane as the center of the sphere) or four points. So loop over all the pairs, triplets and quartets of points, find the minimum sphere that contains them and see if all the other points are in there too.

You can probably do better than this by starting with a sphere large enough to hold all the points and shrinking it "appropriately", depending on how many points of contact you currently have. I think this method should take time O(N), but it could be tricky to implement.

###
#6
Members - Reputation: **1301**

Posted 12 November 2012 - 06:42 PM

A visual example in 2 dimensions:

Note: This technique will almost always generate a non-optimal bounding sphere, which you can see from the diagram, (there is a reasonable margin between the actual points and the calculated circle/sphere). Depending on how you want to use the sphere this may make this technique unsuitable. Though this has the advantage of requiring only 1 distance calculation, which makes it pretty fast.

If you need a tight fit, then something like what Alvaro is alluding to is what you're after.

###
#7
Members - Reputation: **340**

Posted 12 November 2012 - 06:53 PM

You can probably do better than this by starting with a sphere large enough to hold all the points and shrinking it "appropriately", depending on how many points of contact you currently have. I think this method should take time O(N), but it could be tricky to implement.

I don't think that it's possible to do it in O(n) time for dimensions larger than 1 (I think that it's possible to construct a reduction from the diameter problem to the CH problem, but I'm not 100% sure about this). On the other hand an O(n*log(k)) implementation is possible (n is the number of vertices and k is the number of vertices on the convex hull), though it's not that trivial.

**Edited by max343, 12 November 2012 - 06:54 PM.**

###
#8
Crossbones+ - Reputation: **16845**

Posted 12 November 2012 - 08:26 PM

You can probably do better than this by starting with a sphere large enough to hold all the points and shrinking it "appropriately", depending on how many points of contact you currently have. I think this method should take time O(N), but it could be tricky to implement.

I don't think that it's possible to do it in O(n) time for dimensions larger than 1 (I think that it's possible to construct a reduction from the diameter problem to the CH problem, but I'm not 100% sure about this). On the other hand an O(n*log(k)) implementation is possible (n is the number of vertices and k is the number of vertices on the convex hull), though it's not that trivial.

Yes, you are right. The method I was thinking of is not O(n), but something like O(n*log(n)) or O(n*log(k)). I have to think the details through before I can be sure.

###
#9
Members - Reputation: **340**

Posted 13 November 2012 - 07:58 PM

This simple (general position) algorithm should do the trick:

FindMinSphere(S, origSphereVerts) 1. sphereVerts = origSphereVerts, remainingVerts = empty 2. for each i[k] in random pi(1,2,...,length(S)) 2.1 if S[i[k]] is not contained in the sphere spanned by sphereVerts 2.1.1 sphereVerts = FindMinSphere(remainingVerts, EliminateExtraVertex(origSphereVerts + S[i[k]])) 2.2 remainingVerts += S[i[k]] 3. return sphereVerts EliminateExtraVertex(S) 1. X=S 2. if length(S)==5 2.1 X = from the 5 possible spheres in X choose the one that contains all five points 3. return X

**Edited by max343, 13 November 2012 - 07:59 PM.**