version 1.2.0.0 (268 KB) by
John D'Errico

Suite of tools to compute minimal bounding circles, rectangles, triangles, spheres, incircles, etc.

**Editor's Note:** This file was selected as MATLAB Central Pick of the Week

I've written quite a few separate tools to generate a minimal bounding object of some ilk. So if you have a set of points in the plane, and wish to generate the minimal bounding...

- rectangle

- triangle

- general quadrilateral

- circle

- parallelogram

- semi-circle

there is a tool in here to solve your task efficiently. You will also find minboundsphere, for 3-d data. Inscribed objects are also supported, computed by incircle and insphere.

Caveat - if you have only an image, don't expect these tools to work directly. (The image processing toolbox can do much here anyway - look there first.) In order to use these tools, I require a set of extracted points.

John D'Errico (2021). A suite of minimal bounding objects (https://www.mathworks.com/matlabcentral/fileexchange/34767-a-suite-of-minimal-bounding-objects), MATLAB Central File Exchange. Retrieved .

Created with
R2007b

Compatible with any release

**Inspired:**
Minimal Bounding Box, Polarizability_GUI5

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!Create scripts with code, output, and formatted text in a single executable document.

yichen heDear Doctor John,

I have been using the code you were uploaded here, they were really helpful to me. However I found it lacks the code of 'minboundellipse', which is extremely significant to me. I don't know if I can use 'minboundcircle' to substitute it, because I found it can draw an ellipse but it didn't show the long axis and the short axis.Could you please answer the question or upload the 'minboundellipse' to me? Thanks a lot!!!

Sincerely,

Yichen He

Lukas VadovicJane BatDear John, is there a way to use the incircle function without having the 'linprog' as I do not have the Optimization Toolbox?

Cris LuengoJohn,

This is a nice collection!

For the minimum bounding rectangle, there is a more efficient algorithm. It is usually referred to as "rotating callipers". The idea is that you can determine the width and height of the rotated rectangle perpendicular to one edge by finding the antipodal pair. And you can find the antipodal pair for edge n+1 based on the antipodal pair for edge n by looking at only a few points. So you go around the convex hull just once, and find all the pairs. I wrote about this algorithm here: https://www.crisluengo.net/archives/408

Asatur KhurshudyanAnton VogelDear John,

I second the requests for the code to 'minboundellipse'. Would you perhaps mind sending it to me in a personal message ?

kind regards

arnoldHi John,

very nice code. But the function 'minboundellipse' seems to be missing, as others have indicated. Couldn't find it anywhere else so I guess it got forgotten when you last uploaded the files.

regards, Arnold

William WarrinerMichael SapperSimilar to Brett Shoelson's case below, I found some cases where minboundquad needs another check before keeping the area.

With some ugly cases, qx and qy have huge values (like 10^18), so it's simple enough to modify the check:

if (A_i < quad area) && all([qxi qyi] < 1e15)

% keep this one

(etc)

and yes, I second kurene13's recommendation below to update nedges to size(edges,1)

Brett Shoelson@John, others:

The minboundtri function in this suite recently came in very handy for some code I generated for a customer. It worked perfectly--until it didn't. Digging in, I found that in the cases that failed, the points were very tightly clustered. This led in some cases to trifun (in the call to fminsearch) returning areas that were just barely greater than 0... O(10-16). The resulting acceptable triangles were nearly straight lines that clearly did not bound the input points.

I modified the code slightly to enforce a minTriArea constraint. At line 134, I added the && condition A_i > minTriArea (which I set at 10e-5), as below:

% new metric value for the current interval. Is it better?

if A_i<area && A_i > minTriArea % minTriArea = 10e-5

% keep this one

[area,tpoly] = trifun(xy3);

tpoly = tpoly*rot' + repmat(xy0,4,1);

end

The function is now working perfectly for all of my cases.

Thanks!

Brett

aggieprofHi, I tried the minboundsphere routine:

clc; close all; clear variables;

xyz = rand(10000,3);

mean(xyz)

[center,radius] = minboundsphere(xyz)

Results: the mean of the randomly generated coordinates are: 0.5006 0.5030 0.5005 (as expected).

However, the center and radius generated by the routine minboundsphere are likely wrong:

center =

0.5768 0.4376 0.4068

radius =

0.7977

As stated in the minbounddemo.m,

% The sphere should have approximate center [.5 .5 .5]

% and approximate radius sqrt(3)/2 = .86603...

Anybody having the same problem?

Jerry ZhangMichael SapperChenghaoI also need the minimum bounding ellipse function. This file is absent from the folder. Would you like to send it to me?

ChenghaoFFKI need minimum bounding ellipse Function. please send to me..

kurene13You have a bug in minboundquad(). Add nedges = size(edges,1); on line 123.

Otherwise great work. Thank you

daeze zezezezeplz someone can help me to excute in VBA the matlab code that determine the minimun bounding circle .Thank you

Soledad77Quite good! that's what I need, thanks for your help!

Daihui YangsalRicardoVery good work. Could you please send me the minboundellipse code. Or help to develop a similar code,as I need to find the minimum ellipse that circunscribes a few data points.

Yi ZhangVery useful! Any update on removing the outliers before finding the circle?

deru jianBrandonGreat for my 2D tasks. I am going to try to make a 3D version of your minboundrect(). Wish me luck!!

M. F.Works like a charm!

Ryan SnowdenJohn,

Code worked perfectly for a min bounded rectangle around my disc image. For my purposes though I also need to be able to transform my disc shape so that it has the same dimensions as its bounding rectangle. Do you have any advice for how I could achieve this once the bounding rectangle has been generated?

ideasensorDear John, many thanks! Could you please name a reference paper for the minimum bounding circle used in your code minboundcircle.m? Thanks again!

Image AnalystI second Tom Trantor's request for a version that finds the largest shape WITHIN a polygon (except that I don't want the shape to bulge through in between vertices). For one project I need the smallest exterior rectangle, and the largest interior rectangle that can fit inside an irregular shape (a binary image). Here is one algorithm: http://cgm.cs.mcgill.ca/%7Eathens/cs507/Projects/2003/DanielSud/

Daniel Leventhalthere is a bug in minboundquad, after line 122 and before line 127 (edgelist = nchoosek(1:nedges,4);). nedges needs to be reset to account for edges eliminated in the preceding step. Need to add "nedges = length(edgeangles);" after line 122 to fix, I think.

Once I did that, works great! Solved a big problem for me.

Ryan PriceHi, thanks for this. I believe I have also found a typo in minboundcircle(). On line 136 you set radius = old.radius(1); when in fact I think you meant to type radius = old.rads(1); Otherwise you produce an error: Reference to non-existent field 'radius'.

PeteAndrew ChuangYuriconvhulln is failing in minboundsphere if there are some points with the same XYZ. I have to run minboundsphere(unique(xyz,'rows')) to avoid convhulln crashing. Here is example:

minboundsphere([ 0.8726 0.4577 -0.1708

0.8761 0.4610 -0.1411

0.8761 0.4610 -0.1411

0.8761 0.4610 -0.1411

0.8761 0.4610 -0.1411

])

John D'ErricoHi Tom,

The problem is as you point out, that the insphere code uses a dot product to find the distance to each facet. Then it is a simple call to linprog, with one slack variable for each facet.

A similar idea for edges though trips up becasue each edge has two normals. So then the distance to each edge is now the sqrt of the sum of squares of a pair of dot products. While I can avoid the sqrt, such a formulation would involve quadratic equality constraints for each slack variable. Clearly this is not solvable by linprog, or even quadprog. Fmincon would be needed, so a bit more nasty of a problem using a similar formulation to the one in insphere. Certainly one could use the existing insphere code to find decent starting values for such an iterative solution, but it is still a bit more work.

I'll need to think if there is another scheme that might apply.

John

Tom TranterHi John,

Thanks for this submission, it's helped me a lot with a problem I'm working on. I was wondering if the insphere function could be adapted to find the largest sphere bound within the edges of the polygon rather than the faces, as if the polygon were a cage with the sphere bulging through the hollow faces. I'm not too sure how to approach this as the edge normals are not defined in 3D.

Thanks,

Tom

Anton SemechkoHi John, I sent you an e-mail to the electronic address provided on your Matlab profile. In that e-mail I attached a point cloud for which 'minboundsphere' fails almost consistently.

John D'ErricoAnton,

Please send me some cases where it fails, and I will fix it.

John

Anton SemechkoHi John, I ran your 'minboundsphere' function a number of times (for 8 different meshes) and observed that occasionally it fails to produce a minimum bounding sphere that encloses all of the points. In some of these cases, the distance for 5% of the points is a factor of 1.1 greater than the computed radius.

Anton SemechkoThanks John! Great submission. I found your function to find minimum bounding spheres especially useful.

John D'ErricoSebastien,

I can't replicate the cycle that you found with those points, but with only 7 digits printed, the numbers I used were not the same as those you used.

Regardless, I used your idea of maintaining a history that should catch any such problem. I need only keep a small subset of the active sets to catch a cycle, so there is no problem. I've posted a new version to appear tomorrow.

Sebastien RoyNice suite, but minboundcircle can hit an infinite loop in the while section. It happens with this set:

X =

-253.0569

-253.0408

-252.0122

-251.9961

Y =

21614210

21614212

21614210

21614212

This set results in an oscillation between two wrong solutions.

Maybe the function could track the active sets already considered and jump out of the loop if a repeated state is found. Unfortunately, such solution can lead to a huge stack of past active sets.

SpiggeVery useful suite John, thanks. Sometimes one would like to exclude outliers, i.e., points far out from the group of interest. If I were to include say only 90% of the total number of points in a bounding circle, what would be the best strategy you recon?

John D'ErricoWhy modify any code, a silly thing to do since it is completely unnecessary? You must first identify the points of interest. Once that is done, pass those locations into the code. All of this takes little more than a single call to find on your part.

Tallha Akramhi,

Code works find for the data points. How can i modify current code for image data?

John D'Erricominboundrect returns a polygon, so the vertices of the bounding rectangle in (x,y) coordinates, as a polygon in the standard form that matlab uses in any tool that works with a polygon (look for example at inpolygon.)

MaayanHi, I'm trying to use the miniboundrect file but i don't understand how the vectors of points that i receive from the function define the minimal rectangle.

SvenJohn, just a heads-up that MATLAB 2013a pre-release doesn't like calling convhull with those short options any more...

Error using convhull

CONVHULL no longer supports or requires Qhull-specific options.

Please remove these options when calling CONVHULL.

Error in minboundrect (line 102)

edges = convhull(x,y,{'Qt'}); % 'Pp' will silence the warnings

John D'ErricoSorry, but I may have put a code for a bounding ellipse in there in the past, but I won't leave code in there with which I am not satisfied. This is the case of the bounding ellipse.

Doctor61Hi John,

Thanks for your share. I agree with Venkat, 'minboundellipse.m' would have helped me a lot with a case I have in hand.

BenHi John,

minboundellipse.m is in the demo but not in the downloaded zip file. Could you add it? Thanks!

Carlos Martinez-Ortizxiuwei zhangVenkat RDear John,

A file 'minboundellipse.m' is missing I suppose.

regards,

Venkat