 CGAL 5.3 - Optimal Bounding Box
Oriented Bounding Box Functions

The function oriented_bounding_box computes an approximation of the optimal bounding box, which is defined as the rectangular box with smallest volume of all the rectangular boxes containing the input points.

Internally, the algorithm uses an optimization process to compute a transformation (rotation) $${\mathcal R}_b$$ such that the axis-aligned box of the rotated input point set has a volume that is as small as possible given a fixed maximal number of optimization iterations.

Input

The input can be either a range of 3D points, or a polygon mesh.

Output

The result of the algorithm can be retrieved as either:

• the best affine transformation $${\mathcal R}_b$$ that the algorithm has found;
• an array of eight points, representing the best oriented bounding box ( $${\mathcal B}_b$$) that the algorithm has constructed, which is related to $${\mathcal R}_b$$ as it is the inverse transformation of the axis-aligned bounding box of the transformed point set. The order of the points in the array is the same as in the function CGAL::make_hexahedron() , which can be used to construct a mesh from these points.
• a model of MutableFaceGraph

Note that when returning an array of points, these points are constructed from the axis-aligned bounding box and some precision loss should therefore be expected if a kernel not providing exact constructions is used.

The algorithm is based on a paper by Chang, Gorissen, and Melchior .

## Functions

template<typename PointRange , typename Output , typename NamedParameters >
void CGAL::oriented_bounding_box (const PointRange &points, Output &out, const NamedParameters &np)
The function oriented_bounding_box computes an approximation of the optimal bounding box, which is defined as the rectangular box with smallest volume of all the rectangular boxes containing the input points. More...

template<typename PolygonMesh , typename Output , typename NamedParameters >
void CGAL::oriented_bounding_box (const PolygonMesh &pmesh, Output &out, const NamedParameters &np)
Extracts the vertices of the mesh as a point range and calls the overload using points as input. More...

## ◆ oriented_bounding_box() [1/2]

template<typename PointRange , typename Output , typename NamedParameters >
 void CGAL::oriented_bounding_box ( const PointRange & points, Output & out, const NamedParameters & np )

#include <CGAL/Optimal_bounding_box/oriented_bounding_box.h>

The function oriented_bounding_box computes an approximation of the optimal bounding box, which is defined as the rectangular box with smallest volume of all the rectangular boxes containing the input points.

Template Parameters
 PointRange a model of Range. The value type may not be equal to the type Point_3 of the traits class if a point map is provided via named parameters (see below) to access points. Output either the type Aff_transformation_3 of the traits class, or std::array with Point being equivalent to the type Point_3 of the traits class, or a model of MutableFaceGraph NamedParameters a sequence of Named Parameters
Parameters
 points the input range out the resulting array of points or affine transformation np an optional sequence of Named Parameters among the ones listed below
Optional Named Parameters
 a property map associating points to the elements of the point range Type: a model of ReadablePropertyMap with value type geom_traits::Point_3 Default: CGAL::Identity_property_map an instance of a geometric traits class Type: a model of OrientedBoundingBoxTraits_3 Default: a default-constructed object of type CGAL::Oriented_bounding_box_traits_3, where K is a kernel type deduced from the point type. Parameter used in the construction of oriented bounding box to indicate whether the algorithm should first extract the extreme points (points that are on the 3D convex hull) of the input data range to accelerate the computation of the bounding box. Type: Boolean Default: true
Examples:
Optimal_bounding_box/obb_example.cpp, Optimal_bounding_box/obb_with_point_maps_example.cpp, and Optimal_bounding_box/rotated_aabb_tree_example.cpp.

## ◆ oriented_bounding_box() [2/2]

template<typename PolygonMesh , typename Output , typename NamedParameters >
 void CGAL::oriented_bounding_box ( const PolygonMesh & pmesh, Output & out, const NamedParameters & np )

#include <CGAL/Optimal_bounding_box/oriented_bounding_box.h>

Extracts the vertices of the mesh as a point range and calls the overload using points as input.

Template Parameters
 PolygonMesh a model of VertexListGraph Output either the type Aff_transformation_3 of the traits class, or std::array with Point being equivalent to the type Point_3 of the traits class, or a model of MutableFaceGraph NamedParameters a sequence of Named Parameters
Parameters
 pmesh the input mesh out the resulting array of points or affine transformation np an optional sequence of Named Parameters among the ones listed below
Optional Named Parameters
 a property map associating points to the vertices of pmesh Type: a class model of ReadablePropertyMap with boost::graph_traits::vertex_descriptor as key type and Point_3 as value type Default: boost::get(CGAL::vertex_point, pmesh) Extra: If this parameter is omitted, an internal property map for CGAL::vertex_point_t should be available for the vertices of pmesh. an instance of a geometric traits class Type: a model of OrientedBoundingBoxTraits_3 Default: a default-constructed object of type CGAL::Oriented_bounding_box_traits_3, where K is a kernel type deduced from the point type. Parameter used in the construction of oriented bounding box to indicate whether the algorithm should first extract the extreme points (points that are on the 3D convex hull) of the input data range to accelerate the computation of the bounding box. Type: Boolean Default: true