CODEWITHSUNDEEP
algorithmfortrancomputational-geometrybounding-box
ALIN
ALIN

Reputation: 62

Minimum bounding box algorithm in 3D

The minimum bounding box (MBB) is the box around a cloud of 3D points with the smallest volume.

Joseph O'Rourke published [2] a cubic-time algorithm to find the minimum-volume enclosing box of a 3-dimensional point set. O'Rourke's approach uses a 3-dimensional rotating calipers technique.

I read the article and wiki (Minimum bounding box algorithms) [1]. Due to the extremely complicated, I gained nothing. Furthermore, the execution steps of the algorithm are my next problem.

I want to write O'Rourke's algorithm by Fortran.

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

Upvotes: 3

Views: 4118

Answers (1)

user1196549
user1196549

Reputation:

Just a hint about the spirit of the algorithm.

In the first place you need to compute the convex hull of the points set, an O(N Log N) process in 2 and 3D. This gives a convex polygon (described by a ring of vertices) or polyhedron (described as a planar graph).

The next step is combinatorial and consists in trying all the positions that are potentially the tightest. In 2D, a minimum bounding box is flush with an edge, and it suffices to try the directions of all edges in turn (you rotate the polygon so that the edge becomes horizontal, and construct the AABB).

The 3D case is more elaborate and uses the fact that a tightest box is flush with two edges of the polyhedron, on two adjacent faces of the box (the box is not necessarily flush with a face). This property allows to generate a finite number of orientations by trying all pairs of edges, and as above, bring the edges in two coordinate planes and construct the AABB. This takes a little of spherical trigonometry.

Upvotes: 2

Related Questions