\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.13.2 - Linear and Quadratic Programming Solver
QP_solver/convex_hull_containment.cpp
// Example: check whether a point is in the convex hull of other points
#include <cassert>
#include <vector>
#include <CGAL/Cartesian_d.h>
#include <CGAL/MP_Float.h>
#include "solve_convex_hull_containment_lp.h"
// choose exact floating-point type
#ifdef CGAL_USE_GMP
#include <CGAL/Gmpzf.h>
typedef CGAL::Gmpzf ET;
#else
#include <CGAL/MP_Float.h>
typedef CGAL::MP_Float ET;
#endif
typedef CGAL::Cartesian_d<double> Kernel_d;
typedef Kernel_d::Point_d Point_d;
bool is_in_convex_hull (const Point_d& p,
std::vector<Point_d>::const_iterator begin,
std::vector<Point_d>::const_iterator end)
{
solve_convex_hull_containment_lp (p, begin, end, ET(0));
return !s.is_infeasible();
}
int main()
{
std::vector<Point_d> points;
// convex hull: simplex spanned by {(0,0), (10,0), (0,10)}
points.push_back (Point_d ( 0.0, 0.0));
points.push_back (Point_d (10.0, 0.0));
points.push_back (Point_d ( 0.0, 10.0));
for (int i=0; i<=10; ++i)
for (int j=0; j<=10; ++j) {
// (i,j) is in the simplex iff i+j <= 10
bool contained = is_in_convex_hull
(Point_d (i, j), points.begin(), points.end());
assert (contained == (i+j<=10));
}
return 0;
}