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

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

Function Documentation

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.

See Oriented Bounding Box Functions for more information.

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<Point, 8> 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

point_map 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<geom_traits::Point_3>
geom_traits 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<K>, where K is a kernel type deduced from the point type.
use_convex_hull 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<Point, 8> 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

vertex_point_map 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.
geom_traits 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<K>, where K is a kernel type deduced from the point type.
use_convex_hull 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