newbie question - point containment within polyhedron
Hi all How do I check if a point is contained within a polyhedron? Firstly, how do i represent the point? in terms of X, Y, Z where these are declared to be of type Variable? Would someone have any example code snippets to illustrate related points? thanks Manoj Rajagopalan
Manoj Rajagopalan wrote:
Hi all
How do I check if a point is contained within a polyhedron? Firstly, how do i represent the point? in terms of X, Y, Z where these are declared to be of type Variable?
Hi. // Supposing that you are working in a 3 dimensional space. using namespace Parma_Polyhedra_Library; Variable x(0); Variable y(1); Variable z(2); // Now, create your polyhedron: C_Polyhedron ph(3, UNIVERSE); ph.add_constraint(x + 3*y >= z) ph.add_constraint(x >= 0) ph.add_constraint(2*y +2*z <= 5) // Then, create a point, which is a Generator, // e.g., having coordinates (1, 1, 1). Generator g = point(x + y + z); // Finally, compute the relation between // the polyhedron and the generator. Poly_Gen_Relation rel = ph.relation_with(g); // If the point is contained in the polyhedron, then // the polyhedron "subsumes" the point (i.e., adding // the point to the polyhedron won't change the polyhedron). if (rel == Poly_Gen_Relation:subsumes()) std::cout << "The point is contained in ph" << std::endl;
Would someone have any example code snippets to illustrate related points?
thanks Manoj Rajagopalan
Have a look in ppl/tests/Polyhedron/relations1.cc, as well as the documentation for methods Polyhedron::relation_with(...). Cheers, Enea.
Manoj Rajagopalan wrote:
Hi all
How do I check if a point is contained within a polyhedron?
Dear Manoj, a point is just one kind of polyhedra generator. To compute the relation between a polyhedron and a generator, you do something like Poly_Gen_Relation rel = ph.relation_with(g), assuming `ph' is the polyhedron and `g' is the point you are interested in. If `rel' so computed turns out to be equal to Poly_Gen_Relation::subsumes(), then you know `ph' subsumes `g', i.e., that adding the generator `g' to `ph' would not change `ph', i.e., that `ph' already contains `g'.
Firstly, how do i represent the point? in terms of X, Y, Z where these are declared to be of type Variable?
You can do something like Generator g = point(X + 2*Y - 3*Z).
Would someone have any example code snippets to illustrate related points?
You can find more examples in the library's documentation and in the `tests' directory of the PPL distribution.
thanks Manoj Rajagopalan
All the best, Roberto -- Prof. Roberto Bagnara Computer Science Group Department of Mathematics, University of Parma, Italy http://www.cs.unipr.it/~bagnara/ mailto:bagnara@cs.unipr.it
participants (3)
-
Enea Zaffanella -
Manoj Rajagopalan -
Roberto Bagnara