subroutine to Minimum bounding box algorithms in 3D

[[e-mail]]

I'm looking for a free subroutine (or library) that finds the minimum bounding box (MBB - the box around a cloud of 3D points with the smallest volume). It should be written in Fortran.

An algorithm to do this was published by Joseph O'Rourke and is cubic in time. I'd also be content with an approximate MBB generated for instance by the algorithms proposed by Gill Barequet, and Sariel Har-Peled.

Any tips about algorithm or flowchart, etc, makes me happy.

[Nathaniel Shaffer]

Post by ***@yahoo.com
I'm looking for a free subroutine (or library) that finds the minimum bounding box (MBB - the box around a cloud of 3D points with the smallest volume). It should be written in Fortran.
An algorithm to do this was published by Joseph O'Rourke and is cubic in time. I'd also be content with an approximate MBB generated for instance by the algorithms proposed by Gill Barequet, and Sariel Har-Peled.
Any tips about algorithm or flowchart, etc, makes me happy.

I wonder if your actual problem is simpler than the MBB problem. Do you
want the axes of the box to be aligned with some particular coordinate
system, or do you want to allow any orientation of the box?

Looking at those references, I understand why you might want a
ready-made code or a streamlined discussion of the algorithm. You might
try making an account and posting at https://scicomp.stackexchange.com/
If you don't get any good answers here or there, you probably just have
to pony up and read the papers thoroughly and do it yourself.

Nathaniel

[David Jones]

Post by Nathaniel Shaffer

Post by ***@yahoo.com
I'm looking for a free subroutine (or library) that finds the
minimum bounding box (MBB - the box around a cloud of 3D points
with the smallest volume). It should be written in Fortran.
An algorithm to do this was published by Joseph O'Rourke and is
cubic in time. I'd also be content with an approximate MBB
generated for instance by the algorithms proposed by Gill Barequet,
and Sariel Har-Peled.
Any tips about algorithm or flowchart, etc, makes me happy.

I wonder if your actual problem is simpler than the MBB problem. Do
you want the axes of the box to be aligned with some particular
coordinate system, or do you want to allow any orientation of the box?

The other extreme of what the question may actually be is the idea of
convex hulls, for which algorithms are summarised at
https://en.wikipedia.org/wiki/Convex_hull_algorithms

[[e-mail]]

Post by David Jones

Post by Nathaniel Shaffer
I wonder if your actual problem is simpler than the MBB problem. Do
you want the axes of the box to be aligned with some particular
coordinate system, or do you want to allow any orientation of the box?

The other extreme of what the question may actually be is the idea of
convex hulls, for which algorithms are summarised at
https://en.wikipedia.org/wiki/Convex_hull_algorithms

The orientation of the axis is not important. The important variable is to minimize the volume of the box and the accuracy of the algorithm. I also prefer Joseph O'Rourke's algorithm.
I know the convex hull and it is not in the problem.

[Robin Vowels]

Post by ***@yahoo.com
I'm looking for a free subroutine (or library) that finds the minimum bounding box (MBB - the box around a cloud of 3D points with the smallest volume). It should be written in Fortran.
An algorithm to do this was published by Joseph O'Rourke and is cubic in time. I'd also be content with an approximate MBB generated for instance by the algorithms proposed by Gill Barequet, and Sariel Har-Peled.
Any tips about algorithm or flowchart, etc, makes me happy.

http://dwoll.de/rexrepos/posts/diagBounding.html

[[e-mail]]

Post by Robin Vowels

Post by ***@yahoo.com
Any tips about algorithm or flowchart, etc, makes me happy.

http://dwoll.de/rexrepos/posts/diagBounding.html

The link contains the two-dimensional code.

[Nathaniel Shaffer]

Post by ***@yahoo.com

Post by Robin Vowels

Post by ***@yahoo.com
Any tips about algorithm or flowchart, etc, makes me happy.

http://dwoll.de/rexrepos/posts/diagBounding.html

The link contains the two-dimensional code.

Here is a Matlab implementation:
https://www.mathworks.com/matlabcentral/fileexchange/18264-minimal-bounding-box

It has four "levels" of reliability. It is not clear to me if the most
robust one is the same as O'Rourke's method. All four start with the
convex hull and then try boxes of various orientations. The level of
robustness seems to correspond to how many orientations are tried.

The code is not commented as nicely as one might hope, but it may be a
useful sample to guide you. Or if you have access to Matlab, you can run
it to verify your own implementation.

[gah4]

Post by Nathaniel Shaffer

Post by ***@yahoo.com

Post by Robin Vowels

Post by ***@yahoo.com
Any tips about algorithm or flowchart, etc, makes me happy.

http://dwoll.de/rexrepos/posts/diagBounding.html

The link contains the two-dimensional code.

https://www.mathworks.com/matlabcentral/fileexchange/18264-minimal-bounding-box
It has four "levels" of reliability. It is not clear to me if the most
robust one is the same as O'Rourke's method. All four start with the
convex hull and then try boxes of various orientations. The level of
robustness seems to correspond to how many orientations are tried.
The code is not commented as nicely as one might hope, but it may be a
useful sample to guide you. Or if you have access to Matlab, you can run
it to verify your own implementation.

I suppose some might have local minuma, so it could be tricky in some cases.

For example, take 1000 points distance R from the origin.
These are on the surface of a sphere of radius R, but
there should be a box with sides slightly less than 2R that
is the smallest, but there will be many close to that size.

[Paul Richard Thomas]

Post by Nathaniel Shaffer

Post by ***@yahoo.com

Post by Robin Vowels

Post by ***@yahoo.com
Any tips about algorithm or flowchart, etc, makes me happy.

http://dwoll.de/rexrepos/posts/diagBounding.html

The link contains the two-dimensional code.

https://www.mathworks.com/matlabcentral/fileexchange/18264-minimal-bounding-box
It has four "levels" of reliability. It is not clear to me if the most
robust one is the same as O'Rourke's method. All four start with the
convex hull and then try boxes of various orientations. The level of
robustness seems to correspond to how many orientations are tried.
The code is not commented as nicely as one might hope, but it may be a
useful sample to guide you. Or if you have access to Matlab, you can run
it to verify your own implementation.

This runs fine with Octave as well. The if construct at line 274 has to be replaced with edges = convhull(x,y);

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

Paul