CGAL 5.5 - Optimal Bounding Box

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:

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 [1].

Functions

template<typename PointRange , typename Output , typename NamedParameters = parameters::Default_named_parameters>
void CGAL::oriented_bounding_box (const PointRange &points, Output &out, const NamedParameters &np=parameters::default_values())
 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 = parameters::Default_named_parameters>
void CGAL::oriented_bounding_box (const PolygonMesh &pmesh, Output &out, const NamedParameters &np=parameters::default_values())
 Extracts the vertices of the mesh as a point range and calls the overload using points as input. More...
 

Function Documentation

◆ oriented_bounding_box() [1/2]

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

#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.

See Oriented Bounding Box Functions for more information.

Template Parameters
PointRangea 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.
Outputeither the type Aff_transformation_3 of the traits class, or std::array<Point, 8> with Point being equivalent to the type Point_3 of the traits class, or a model of MutableFaceGraph
NamedParametersa sequence of Named Parameters
Parameters
pointsthe input range
outthe resulting array of points or affine transformation
npan optional sequence of Named Parameters among the ones listed below
Optional Named Parameters

  • 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 = parameters::Default_named_parameters>
void CGAL::oriented_bounding_box ( const PolygonMesh &  pmesh,
Output &  out,
const NamedParameters &  np = parameters::default_values() 
)

#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
PolygonMesha model of VertexListGraph
Outputeither the type Aff_transformation_3 of the traits class, or std::array<Point, 8> with Point being equivalent to the type Point_3 of the traits class, or a model of MutableFaceGraph
NamedParametersa sequence of Named Parameters
Parameters
pmeshthe input mesh
outthe resulting array of points or affine transformation
npan 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<PolygonMesh>::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.

  • 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