File Exchange

image thumbnail

Exact minimum bounding spheres and circles

version 1.4.0.0 (1.08 MB) by Anton Semechko
Compute exact and approximate minimum bounding spheres/circles of 3D/2D point sets

17 Downloads

Updated 07 May 2019

GitHub view license on GitHub

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.

If you find these functions useful or have a suggestion on how to improve the submission, please leave a comment below.

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 .

Comments and Ratings (12)

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

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?

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

Yves Konkel

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

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

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

Exactly what I needed, thanks

D G

sumana

excellent, thank you

Klop Oray

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

Updates

1.4.0.0

- migrated to GitHub

1.3.0.0

- Made changes to return parameters of minimum bounding circles instead of circumcircles for point sets representing vertices of obtuse triangles. Thanks to Yves Konkel for pointing out this bug.

1.2.0.0

- Removed minor bug pointed out by Wang Yong
- Updated 'ExactMinBoundSphere3D.m' to automatically recognize coplanar and collinear point sets
- Updated 'ExactMinBoundCircle.m' to automatically recognize collinear point sets

1.1.0.0

added a function that computes exact minimum bounding circles

MATLAB Release Compatibility
Created with R2015a
Compatible with any release
Platform Compatibility
Windows macOS Linux