1 /* A collection of useful convex polyhedra algorithms: inline functions.
2 Copyright (C) 2001-2010 Roberto Bagnara <bagnara@cs.unipr.it>
3 Copyright (C) 2010-2016 BUGSENG srl (http://bugseng.com)
4
5 This file is part of the Parma Polyhedra Library (PPL).
6
7 The PPL is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3 of the License, or (at your
10 option) any later version.
11
12 The PPL is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software Foundation,
19 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA.
20
21 For the most up-to-date information see the Parma Polyhedra Library
22 site: http://bugseng.com/products/ppl/ . */
23
24 #ifndef PPL_algorithms_hh
25 #define PPL_algorithms_hh 1
26
27 #include "NNC_Polyhedron_defs.hh"
28 #include "Pointset_Powerset_defs.hh"
29 #include <utility>
30
31 namespace Parma_Polyhedra_Library {
32
33 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
34 /*! \brief
35 If the poly-hull of \p p and \p q is exact it is assigned
36 to \p p and <CODE>true</CODE> is returned,
37 otherwise <CODE>false</CODE> is returned.
38
39 \relates Polyhedron
40 */
41 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
42 template <typename PH>
43 bool
44 poly_hull_assign_if_exact(PH& p, const PH& q);
45
46 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
47 /*! \relates Polyhedron */
48 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
49 template <typename PH>
50 bool
poly_hull_assign_if_exact(PH & p,const PH & q)51 poly_hull_assign_if_exact(PH& p, const PH& q) {
52 PH poly_hull = p;
53 NNC_Polyhedron nnc_p(p);
54 poly_hull.poly_hull_assign(q);
55 std::pair<PH, Pointset_Powerset<NNC_Polyhedron> >
56 partition = linear_partition(q, poly_hull);
57 const Pointset_Powerset<NNC_Polyhedron>& s = partition.second;
58 typedef Pointset_Powerset<NNC_Polyhedron>::const_iterator iter;
59 for (iter i = s.begin(), s_end = s.end(); i != s_end; ++i) {
60 // The polyhedral hull is exact if and only if all the elements
61 // of the partition of the polyhedral hull of `p' and `q' with
62 // respect to `q' are included in `p'
63 if (!nnc_p.contains(i->pointset())) {
64 return false;
65 }
66 }
67 p = poly_hull;
68 return true;
69 }
70
71 } // namespace Parma_Polyhedra_Library
72
73 #endif // !defined(PPL_algorithms_hh)
74