File Exchange

## Exact minimum bounding spheres and circles

version 1.4.0.0 (1.08 MB) by Anton Semechko

### Anton Semechko (view profile)

Compute exact and approximate minimum bounding spheres/circles of 3D/2D point sets

Updated 07 May 2019

The problem of finding minimum bounding spheres (aka minimum enclosing spheres) is frequently encountered in a number of applications, including computer graphics and patter recognition. While a number of relatively simple algorithms exist for finding such spheres, there are no robust implementations of these algorithms in Matlab that can be readily found on-line. Functions contained in this submission are meant to fill this void.

Exact minimum bounding spheres and circles can be computed using the functions ‘ExactMinBoundSphere3D’ and ‘ExactMinBoundCircle’, both implementing Wezlz’s algorithm [1]. Approximate minimum bounding spheres in any dimension can be computed using ‘ApproxMinBoundSphereND’ function, which implements Ritter’s algorithm [2].

For convenience, I also included functions ‘VisualizeBoundSphere’ and ‘VisualizeBoundCircle’ that allow you to visualize input point clouds (or meshes) with their respective minimum bounding sphere/circle (see demo pic).

For demonstration on how to use the functions, download attached .zip file, unpack it into your Matlab path, and enter ‘MinBoundSphereDemo’ into Matlab command window.

Cheers!

REFERENCES:
[1] Welzl, E. (1991), 'Smallest enclosing disks (balls and ellipsoids)', Lecture Notes in Computer Science, Vol. 555, pp. 359-370
[2] Ritter, J. (1990), 'An efficient bounding sphere', in Graphics Gems, A. Glassner, Ed. Academic Press, pp.301-303

### Cite As

Anton Semechko (2019). Exact minimum bounding spheres and circles (https://www.github.com/AntonSemechko/Bounding-Spheres-And-Circles), GitHub. Retrieved .

Otso Brummer

Anton Semechko

### Anton Semechko (view profile)

Hi, Bruno. It would be helpful to see the input data you are feeding into the function that produces this warning message. Send me the data, if possible. My e-mail is listed in the header of the function.

Bruno

### Bruno (view profile)

Hi Anton! Great code. However, is outputing a lot of warnings saying:

"
In ExactMinBoundSphere3D/B_MinSphere (line 167)
In ExactMinBoundSphere3D (line 132)
Warning: Matrix is singular, close to singular or badly scaled. Results may be inaccurate. RCOND = NaN. "

"
In ExactMinBoundSphere3D/B_MinSphere (line 167)
In ExactMinBoundSphere3D (line 132)
Warning: Matrix is singular, close to singular or badly scaled. Results may be inaccurate. RCOND = NaN.
> In FitSphere2Points (line 92) "

Why is this?

Anton Semechko

### Anton Semechko (view profile)

Actually, Yeves, my bad. Your observation was totally correct. I will make necessary changes soon.

Yves Konkel

### Yves Konkel (view profile)

Very good tool, but does not work correctly for N=3 points in 2D. For example: triangle with sides a = b and gamma > 90 deg.

mengya hu

### mengya hu (view profile)

I found the code cannot deal with points from the same line if it is 2D input ( or points from a plane if it is 3D input).

Here I give the solution for the first case:
if polyarea(nr,nc)
%For 2D input, ExactMinBoundCircle can not deal with points
%from the same line.
[R,Cen,xb]=ExactMinBoundCircle([nr nc]);

else
Cen=[mean(nr),mean(nc)];
end

wang yong

### wang yong (view profile)

A litter error, ExactMinBoundCircle :
1. line 41 [R,C]=FitCirc2Points(X); should be [R,C]=FitCircle2Points(X);
2. VisualizeBoundCircle : comment line 6 ,should be "- C : 1-by-2 vector specifying the centroid of the circle."
1-by-3 --->1-by-2

Claire Meyer

### Claire Meyer (view profile)

Exactly what I needed, thanks

D G

sumana

### sumana (view profile)

excellent, thank you

Mikhail Dostoevsky

Klop Oray

### Klop Oray (view profile)

Excellent. Very fast, very efficient and accurate. Much better than another submission rated 4.8 on this site.