Given a set of points $$={p_{1},..., p_{n}} in $$ ^{3}. The width of $$, denoted as $$(), is defined as the minimum distance between two parallel planes of support of $$conv(); where $$conv() denotes the convex hull of $$. The width in direction $$d, denoted as $$_{d}(), is the distance between two parallel planes of support of $$conv(), which are orthogonal to $$d.
Subject to the applications of the width algorithm, several objects might be interesting:
Note: There might be several optimal build directions. Hence neither the widthplanes nor the direction $$d_{opt} are unique  only the width is.
#include <CGAL/Width_3.h>
The template parameter Traits is a model for WidthTraits_3. We provide the model Width_default_traits_3<Kernel> based on a threedimensional CGAL kernel.
 
traits class.

 
 point type.  
 
 plane type.  
 
 vector type.  
 
 algebraic ring type.  
 
 traits class for the 3D convex hull algorithm. 
 
 
creates a variable width initialized to the width of $$ 
with $$ being the set of points in the range
[first,beyond). Requirement: The value type of InputIterator is Point_3.
 
 
 
creates a variable width initialized to
the width of the polyhedron $$P. Note that the vertex point coordinates
are altered! Precondition: $$P is a convex polyhedron. Requirement: Polyhedron is a CGAL::Polyhedron_3 with facets supporting plane equations where Polyhedron::Point_3 $$ Point_3 and Polyhedron::Plane_3 $$ Plane_3.


 
returns the squared width. For the reason of exact computation not the width itself is stored, but the squared width as a fraction: The numerator in width_num and the denominator in width_denom. The width of the point set $$ is $$sqrt((width_num)/(width_denom)).  

 
The planes e1 and e2 are the two parallel supporting planes, which distance is minimal (among all such planes).  

 
The returned coefficients A,B,C,D,K have the property that widthplane e1 is given by the equation $$Ax+By+Cz+D=0 and widthplane e2 by $$Ax+By+Cz+K=0.  

 
returns a direction $$d_{opt} such that the widthplanes e1 and e2 are perpendicular to $$d_{opt}. The width of the point set is minimal in this direction.  

 
All the build directions are stored in the vector dir. It might happen that a certain body has several different build directions, but it is also possible to have only one build direction.  

 
returns the number of optimal solutions, i.e., the number of optimal build directions. 
CGAL::Width_default_traits_3<K>
WidthTraits_3
Since the width of the point set $$ and the width of the convex hull of $$ ($$conv()) is the same, the algorithm uses the 3D convex hull algorithm CGAL provides.
The widthalgorithm is not incremental and therefore inserting and erasing points cause not an `automatic' update of the width. Instead you have to run the widthalgorithm again even if the point set is extended by only one new point.
advanced 
Large Numbers.
Because there is no need for dividing values during the algorithm, the numbers can get really huge (all the computations are made using a lot of multiplications). Therefore it is strongly recommended to use a number type that can handle numbers of arbitrary length (e.g., leda_integer in combination with the homogeneous representation of the points). But these large numbers have a disadvantage: Operations on them are slower as greater the number gets. Therefore it is possible to shorten the numbers by using the compiler flag DSIMPLIFY. For using this option it is required that the underlying number type provides the `modulo' operation.
Information Output during the Computations.
If during the algorithm the program should output some information (e.g., during the debugging phase) you can turn on the output information by giving the compiler flag DEBUG. In the file width_assertions.h you can turn on/off the output of some functions and additional informations by changing the defined values from 0 (no output) to 1 (output available). But then it is required that the $$<<operator has to been overloaded for Point_3, Plane_3, Vector_3 and RT.
advanced 
#include <CGAL/Homogeneous.h> #include <CGAL/Width_default_traits_3.h> #include <CGAL/Width_3.h> #include <iostream> #include <vector> #include <CGAL/leda_integer.h> typedef leda_integer RT; typedef CGAL::Homogeneous<RT> Kernel; typedef Kernel::Point_3 Point_3; typedef Kernel::Plane_3 Plane_3; typedef CGAL::Width_default_traits_3<Kernel> Width_traits; typedef CGAL::Width_3<Width_traits> Width; int main() { // Create a simplex using homogeneous integer coordinates std::vector<Point_3> points; points.push_back( Point_3(2,0,0,1)); points.push_back( Point_3(0,1,0,1)); points.push_back( Point_3(0,0,1,1)); points.push_back( Point_3(0,0,0,1)); // Compute width of simplex Width simplex( points.begin(), points.end()); // Output of squared width, widthplanes, and optimal direction RT wnum, wdenom; simplex.get_squared_width( wnum, wdenom); std::cout << "Squared Width: " << wnum << "/" << wdenom << std::endl; std::cout << "Direction: " << simplex.get_build_direction() << std::endl; Plane_3 e1, e2; std::cout << "Planes: E1: " << e1 << ". E2: " << e2 <<std::endl; std::cout << "Number of optimal solutions: " << simplex.get_number_of_optimal_solutions() << std::endl; return(0); }