3.8

3.8 | 7 ratings Rate this file 24 downloads (last 30 days) File Size: 4.45 KB File ID: #13758

Minimum Radius Bounding Sphere

by John D'Errico

 

24 Jan 2007 (Updated 04 Jun 2010)

Code covered by the BSD License  

Minimum radius bounding sphere around a 3d set of points

Download Now | Watch this File

File Information
Description

MINBOUNDSPHERE is an extension of my MINBOUNDCIRCLE code, to run on 3-d data. It computes the minimum radius enclosing sphere around 3-d data.

>> xyz = randn(1000,3);
>> tic,[c,r] = minboundsphere(xyz),toc
Elapsed time is 0.049200 seconds.

c =
    -0.096207 -0.12586 0.090616

r =
       4.0176

Note that the generated sphere must pass through at least 2 of the points provided.

MINBOUNDSPHERE should return the correct finite radius sphere even for only 2 or 3 points, or where the points are nearly collinear or coplanar, so that the circum-sphere would normally have infinite or near infinite radius.

Use is made of convhulln to improve run time. If there is a perceived need, I could allow the user to turn off the call to convhulln when desired, or modify the convhulln call to be compatible with older Matlab releases. Please send me e-mail if this feature would be of value.
Acknowledgements

The author wishes to acknowledge the following in the creation of this submission:
Minimum Enclosing Circle, Minimum Radius Bounding Circle
This submission has inspired the following:
insphere

MATLAB release MATLAB 7.3 (R2006b)
Zip File Content  
Other Files license.txt,
minboundsphere.m
Tags for This File  
Everyone's Tags
Tags I've Applied
Add New Tags Please login to tag files.
Comments and Ratings (15)
26 Jan 2007 good job

Is it possible to fit a elliposid instead of just a sphere? With an ellipsoid, we can get the major axis and minor axis radius.
26 Jan 2007 John D'Errico

I could supply ellipse/ellipsoid codes, but the algorithms I've tried so far will have the flaw of not being as robust as my circle and sphere codes. These circle and sphere codes should always succeed, and will do so quickly.

My tests show that the ellipse code I wrote failed to converge a significant fraction of the time (perhaps 20% of my tests failed to produce viable results.) This seems unacceptable to me. An alternative algorithm that I tried was always convergent to "a" solution, but it did not produce the optimal solution on my test problems. I'm still playing with options.

John
17 Jun 2007 good job

Good, but won't work in my 6.5. Error was found in:
dfun = @(A) (A(:,[1 1 1 1]) - A(:,[1 1 1 1])').^2;

Guess the handle is the problem. Don't know how to deal with it though. Does the author have a version that can work in old Matlab? Thanks.

11 Oct 2007 Javier Leonardo

Hi, thanks for the submission, I am looking exactly for this. There is a flaw in the program, please try with the points (in this order)

0.8402 0.9155 0
0.8019 0.4046 0
0.5566 0.0901 0
0.7524 0.9361 0

for some permutations you get the correct answer, what may indicate a problem in the active/inactive set replacement rule (how is the removed vertex chosen? I think this is not a simple (if even possible in all cases) choice)
11 Oct 2007 John D'Errico

Javier,

The problem is, you are using a code designed for 3 dimensional data on a 2-d problem. Note that all of the points in your example lie in the (x,y) plane, with z == 0. If instead, you had used minboundcircle, you would find that other code works perfectly well on your 2-d data.

xy = [0.8402 0.9155;0.8019 0.4046;0.5566 0.0901;0.7524 0.9361]

[c,r] = minboundcircle(xy(:,1),xy(:,2))
c =
      0.69715 0.50323
r =
      0.43638

Its always best to use the right tool for the problem.

John
18 Oct 2007 Javier Leonardo

John, thanks for your answer,
I used a planar example because it was easier to visualize, yet my point is that the algorithm does not always work (this was concluded from looking into your code rather than trying with different point sets). You can confirm this with the following 3-D set of points:

xyz=[0.8402 0.9155 0;...
0.8019 0.4046 -0.1;...
0.5566 0.0901 0.2;...
0.7524 0.9361 0;...
0.435 0.3004 0.1];

It is always best to provide tools stating clearly their limitations (not every 3-D set of points is processed correctly by your program). I think it is useful to be able to determine beforehand when your tool can be used.
23 Oct 2007 Chris Tumbler

I keep getting the following error on line 229: "identifier" expected, "(" found." !

Can you help me change this?
23 Oct 2007 John D'Errico

Chris - you are using version 6.5 of Matlab or earlier. This code assumes version 7 or above, as stated in the Matlab release info. John
27 Aug 2008 Ahmed Joubair

Hi John,

when I execute the program, Matlab give me this error:
??? Undefined command/function 'minboundsphere'.

Can you help and tel me how to execute the program correctly please?

Thank you
15 Dec 2008 Kenneth Eaton  
25 Jan 2010 Zacharias Voulgaris

Beautiful and quite handy program. Thank you for sharing. Is there a version of it for N-dimensional space by any chance?
25 Jan 2010 John D'Errico

Zacharias - Sorry, but the algorithm I used is not extensible to higher dimensions. John
26 Jan 2010 Danubio Genova

Nice piece of code, worked fine for me in most of cases, except with this particular set of values:
xyz = [ 1.5447 0.2179 0.4047
    1.6148 0.2996 0.3463
    1.7549 0.3502 0.4008
    1.8366 0.4202 0.4514
    1.8833 0.4241 0.4047
    1.9027 0.3307 0.3346
    1.9533 0.4202 0.4047
    1.8638 0.4202 0.4475
    1.8249 0.4202 0.4358
    1.8444 0.4086 0.3619
    2.1595 0.4436 0.2879
    2.1751 0.4397 0.4202
    1.9689 0.4436 0.4981
    1.8560 0.4514 0.5058
    1.8716 0.4591 0.4358
    1.8599 0.4981 0.2490
    1.9455 0.4280 0.4202
    1.9416 0.4319 0.5759
    1.9883 0.4864 0.5914
    2.1128 0.5019 0.5292
    1.5720 0.5175 0.2412
    1.7899 0.4475 0.4514
    1.8755 0.4008 0.5720
    1.9572 0.4202 0.5720
    2.0973 0.4903 0.5019]
For this particular set of values, I got no answer. Not sure why, perhaps a but in the while loop. I'm using Matlab R2008a.
04 Jun 2010 Ehsan Farvardin

Hello John,

It's a very useful code and thanks a lot for that, but it seems have some bugs, for example in the following case it does not answer and the computer hangs. Could you please help in this regard, Do you have a newer version?

Thanks,
Ehsan

3.491834239 2.195503364 -99.91489808
-14.8661948 20.1143378 -96.82153514
33.54810241 -2.038040551 -94.18264816
-0.290805412 0.038305205 99.99956982
1.022380071 4.183167964 -99.9072362
-29.53129477 -0.066219568 -95.54003477
-37.61880927 89.67977141 23.28870517
10.99795718 -74.77880457 -65.47652499
0.134616194 -23.02919513 -97.31206529
-2.278262119 21.51388327 97.63176915
13.71165869 6.999563317 99.71587936
-2.810567447 23.12651431 102.499906
40.76230005 3.189373794 104.8749043
10.307283 5.058084974 279.6389005
11.48914994 8.788461457 99.72277505
-16.00915742 4.964012678 103.6532563
-23.28792047 85.73540456 210.5991223
20.46716934 -62.27731383 130.7104151
10.69016245 -15.70266532 102.0584289
8.518571966 24.38610524 277.5078799
-68.68544478 132.1548134 136.9781804
-79.7002622 142.9061141 138.8341982
-50.65168387 129.614687 140.4175304
-70.95502857 130.8604945 256.9268611
-70.16711728 133.3474121 136.9827775
-88.49932218 130.7977796 139.6030984
-93.35183088 184.6453742 210.9003424
-64.18177101 85.97022863 157.6412043
-70.6997756 117.0199943 138.5398801
-72.14750259 143.7458413 255.5061807
154.7298244 21.42315576 2.954352509
141.879204 33.96633987 5.119706568
175.7692121 18.45967502 6.966927451
152.0819766 19.91311705 142.89448
153.0012065 22.81452098 2.959715827
131.6136341 19.83994971 6.016756826
125.9523739 82.6621434 89.19687478
159.9841104 -32.4588598 27.06121367
152.3797717 3.765866818 4.776335465
150.6907569 34.9460217 141.2370196
102.314324 66.65937404 241.6241259
87.6279008 80.99444159 244.0988163
126.3593386 63.2725389 246.2099259
99.28821231 64.93361551 401.5557003
100.3387607 68.24950572 241.6302555
75.89582082 64.84999569 245.1240166
69.42580923 136.6467885 340.1870085
108.3192224 5.079927687 269.1748244
99.6285496 46.47961524 243.7063922
97.69824695 82.11407796 399.6614597
226.1454626 -69.05105174 72.97839372
215.1306452 -58.29975107 74.83441148
244.1792235 -71.59117809 76.41774367
223.8758788 -70.34537063 192.9270745
224.6637901 -67.85845298 72.98299085
206.3315852 -70.4080855 75.60331171
201.4790765 -16.56049091 146.9005557
230.6491364 -115.2356365 93.64141758
224.1311318 -84.18587083 74.5400934
222.6834048 -57.46002379 191.5063941
277.2516636 84.21447208 53.44935933
262.5652404 98.54953963 55.92404969
301.2966781 80.82763695 58.03515927
274.2255519 82.48871355 213.3809337
275.2761003 85.80460376 53.45548884
250.8331604 82.40509373 56.94924998
244.3631488 154.2018865 152.0122419
283.256562 22.63502573 81.00005781
274.5658892 64.03471329 55.53162557
272.6355865 99.66917601 211.4866931
127.1125844 120.3126842 -133.6828742
112.4261612 134.6477518 -131.2081839
151.157599 116.9258491 -129.0970743
124.0864727 118.5869257 26.24870008
125.1370211 121.9028159 -133.6767447
100.6940812 118.5033059 -130.1829836
94.22406961 190.3000987 -35.11999164
133.1174828 58.7332379 -106.1321758
124.42681 100.1329255 -131.600608
122.4965073 135.7673882 24.35445955
-84.7391857 146.0498725 -90.31270487
-97.58980603 158.5930566 -88.14735081
-63.69979798 143.0863917 -86.30012993
-87.38703346 144.5398337 49.62742266
-86.46780362 147.4412377 -90.30734155
-107.855376 144.4666664 -87.25030055
-113.5166362 207.2888601 -4.070182598
-79.48489964 92.1678569 -66.20584371
-87.08923833 128.3925835 -88.49072192
-88.77825315 159.5727384 47.96996219

04 Jun 2010 John D'Errico

Sorry for the problems with this code. It had a cycling problem that caused it to get trapped at times. That problem should now be resolved. Updated version just submitted.
Please login to add a comment or rating.
Updates
04 Jun 2010

Improved the robustness of the code, avoiding the cycling trap that the old code fell into.
Tag Activity for this File
Tag Applied By Date/Time
minimum John D'Errico 22 Oct 2008 08:58:16
optimum John D'Errico 22 Oct 2008 08:58:16
radius John D'Errico 22 Oct 2008 08:58:16
bounding John D'Errico 22 Oct 2008 08:58:16
bound John D'Errico 22 Oct 2008 08:58:16
sphere John D'Errico 22 Oct 2008 08:58:16
enclose John D'Errico 22 Oct 2008 08:58:16
enclosing John D'Errico 22 Oct 2008 08:58:16

Contact us at files@mathworks.com