c++ - 帕尔马多面体库 : Vertex Enumeration

Question

我正在尝试使用 Parma Polyhedra 库 [1]枚举(凸)多面体的顶点，例如，我有一个由四个约束指定的矩形:

Constraint_System cs;
cs.insert(x >= 0);
cs.insert(x <= 3);
cs.insert(y >= 0);
cs.insert(y <= 3);
C_Polyhedron ph(cs);

我如何生成顶点？

Answer 1

PPL 中的每个形状都有双重表示:1) Constraint_System，2) Generator_System。对于凸多面体，生成器系统将包含一组生成器，这些生成器可以是 1) 点、2) 线、3) 射线。对于凸多胞形，生成器集将是所有点。您可以获得生成器表示如下:

Generator_System gs = ph.generators(); // Use ph.minimized_generators() to minimal set of points for the polytope
for(Generator_System::const_iterator it = gs.begin(); it != gs.end(); it++) {
  const Generator& g = *it;
  assert(g.is_point()); // Assertions will fail for unbounded polyhedra
  std::cout << g;
}