File Exchange

image thumbnail

Minimal Bounding Box

version 1.1.0.0 (5.04 KB) by Johannes Korsawe
Minimal bounding box around points in the (x,y,z) space

21 Downloads

Updated 16 Feb 2015

View Version History

View License

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

With this function one can easily compute the minimal box (with right angles) around a set of points in 3d.
The extremal property of the box is determined either in terms of volume, surface or sum of edgelengths.

The calculation is based on heuristics only, but a huge number of tests did not show any counterexamples yet.

The algorithm behind the function is subdivided into three levels of accuracy with differing runtimes.

x = rand(10000,1);
y = rand(10000,1);
z = rand(10000,1);

tic;[rotmat,cornerpoints,volume,surface] = minboundbox(x,y,z,'v',3);toc
Elapsed time is 10.772170 seconds.

volume =
0.9993
surface =
5.9974

My thanks to John d'Errico and Roger Stafford for numerous discussions about proofs and algorithms in this context.

John also wrote minboundrect from the FEX, which heavily influenced this submission.

Also in this archive i included a small plot function (plotminbox) to show the resulting box via connecting the cornerpoints.

Cite As

Johannes Korsawe (2021). Minimal Bounding Box (https://www.mathworks.com/matlabcentral/fileexchange/18264-minimal-bounding-box), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (23)

Yiren Sun

Can this be applied to 2D points? Many thanks

qi fan

Perfect, thanks!

Alex Nimmo Smith

Great function - thank you! However, I ran into a problem when inputting a point cloud that used single rather than double precision causing convhulln to fail. Changing the preprocess data section to:
% preprocess data
x = double(x(:));
y = double(y(:));
z = double(z(:));

fixed this. I hope this helps.

YANXIN ZHOU

maho

danesh danesh

Bruno Ghini

deru jian

Olivier Pasquier

Thanks a lot

liang

ibtissem jbira

i need the algorithm of this code :
I did not understand how you calculated BOO
at the beginning you start with calucul of its convex hull but after I understood nothing !!!

Johannes Korsawe

Ishan,
i tested the code on the latest release R2014b and it worked. No idea what is going wrong on your side. The error has to be debugged on your system line by line.
Regards, Johannes

Ishan

Johannes,

Indeed, I replaced it with convhulln and the necessary argument. However, the error persists.

Are there any online resources available which can guide me through the process which you have used to program this function?

I am planning to write an updated version of your function which will be compatible for more recent versions of MATLAB. If I can gain a clear understanding of the background, perhaps I will be able to release it on FEX.

Any help would be much appreciated!

Thank you for your time,
Ishan

Johannes Korsawe

Ishan,
i wrote an update for releases >= 2010a. Perhaps convhull failed in your test.
Best, Johannes

Ishan

On MATLAB 2014a, I am encountering the following error:

Error using *
Inner matrix dimensions must agree.

Error in minboundbox>minrect (line 310)
rot_i = Rmat(-edgeangles(i));xyr = xy*rot_i;

Error in minboundbox>checkbox (line 274)
rot2 = minrect(x_i,y_i,metric); % find the optimal
rotation around z-axis

Error in minboundbox (line 170)
[d, rotmat, minmax] =
checkbox(alpha(i),beta(i),gamma(i),xyz,metric,d,rotmat,minmax);

Could someone please help me understand what flags to look for (or tests to run) in order to debug this? For input, I've used Johannes example of 10000x1 rand vectors.

Wolfgang

fourar redha

Matt Kindig

A simple fix to reduce the run-time is to replace the line:

rot_i = Rmat(-edgeangles(i));

with these lines:
theta = -edgeangles(i);
rot_i = [cos(theta), sin(theta); -sin(theta) cos(theta)];

In my testing, this reduces the run-time by a factor of ~2.

Shunzhou

jia

Steven

Nice work. Thank you.

Mark

This file saved me a ton of work, and has worked great for all of my tests, thanks!

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

Community Treasure Hunt

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

Start Hunting!