Building the problem and solving it.

A capsule can be uniquely defined by its two main axis end points $e_1$ and $e_2$ , as well as its radius $r$ . To compute the minimum-volume bounding capsule over one or more polyhedrons, an non-linear optimization problem is defined, then solved using a jacobian-based numerical optimization solver provided through RobOptim and an IPOPT plugin.

The problem that will be solved is:

$min_{e_1, e_2, r} \|e_2 - e_1\| \pi r^2 + \frac{4}{3}\pi r^3$

subject to:

$r - d(p,e_1e_2) \geq p \in \mathcal{P}$

This ensures that the minimum-volume capsule is found while all points of the set $\mathcal{P}$ , which represents one or more polyhedrons, all lie inside the capsule.

Building the problem and solving it.

This part of the tutorial covers how to compute an optimal capsule. The steps are:

Instanciate or load a polyhedron. Here we create a simple cube.

BOOST_AUTO_TEST_CASE (fitter)
{
using namespace roboptim::capsule;
// Build a cubic polyhedron centered in (0,0,0).
polyhedron_t polyhedron;
value_type halfLength = 0.5;
polyhedron.push_back (point_t (-halfLength, -halfLength, -halfLength));
polyhedron.push_back (point_t (-halfLength, -halfLength, halfLength));
polyhedron.push_back (point_t (-halfLength, halfLength, -halfLength));
polyhedron.push_back (point_t (-halfLength, halfLength, halfLength));
polyhedron.push_back (point_t (halfLength, -halfLength, -halfLength));
polyhedron.push_back (point_t (halfLength, -halfLength, halfLength));
polyhedron.push_back (point_t (halfLength, halfLength, -halfLength));
polyhedron.push_back (point_t (halfLength, halfLength, halfLength));
polyhedrons_t polyhedrons;
polyhedrons.push_back (polyhedron);

Compute the convex hull of one or more polyhedrons. This offers the nice property that a lower number of constraints will be added to the optimization problem without affecting the result.

polyhedrons_t convexPolyhedrons;

computeConvexPolyhedron (polyhedrons, convexPolyhedrons);

Instanciate a fitter. This is the main class in this package and is used to find the best fitting capsule over the input polyhedron vector.

Fitter fitter (convexPolyhedrons);

Set initial parameters for the fitter. One very nice way to find a good initial guess is to compute a bounding capsule with least-squares method. This way, the initial capsule enforces all constraints and is not too far from the optimum.

point_t endPoint1, endPoint2;
value_type radius;
computeBoundingCapsulePolyhedron (convexPolyhedrons,
endPoint1, endPoint2, radius);
argument_t initParam (7);
convertCapsuleToSolverParam (initParam, endPoint1, endPoint2, radius);

Run the solver and retrieve the optimal capsule parameters.

fitter.computeBestFitCapsule (initParam);
argument_t solutionParam = fitter.solutionParam ();
std::cout << fitter << std::endl;
}

To see more usage examples, consider looking at the test directory of the project which contains the project's test suite.