CGAL 6.1.1 - Optimal Bounding Box

Loading...
Searching...
No Matches
Functions
Oriented Bounding Box Functions
Reference Manual » Optimal 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 = 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.
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.

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

  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

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

  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

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