Parma Polyhedra库：顶点枚举 [英] Parma Polyhedra Library: Vertex Enumeration

问题描述

我正在尝试使用 Parma Polyhedra库 [1] 枚举（凸）多边形的顶点，例如，我有一个由四个约束指定的矩形：

I'm trying to use the Parma Polyhedra Library [1] to enumerate the vertices of a (convex) polytope, e.g., I have a rectangle specified by four constraints:

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

如何生成顶点？

推荐答案

PPL中的每个形状都有两种表示形式：1）Constraint_System，2）Generator_System。对于凸多面体，发生器系统将包含一组发生器，它们可以是1）点，2）线，3）射线。对于凸多面体，生成器集将是所有点。您可以按以下方式获得生成器表示形式：

Each shape in PPL has dual representations: 1) Constraint_System, 2) Generator_System. For a convex-polyhedra, the generator system will contain the set of generators which can either be 1) Point, 2) Line, 3) Rays. For the convex polytope, the set of generators would be all points. you can get the generator representation as follows:

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;
}

这篇关于Parma Polyhedra库：顶点枚举的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！