Sets¶
Note: This part of the library is recent and under active development. It will be enriched with new functionalities in future releases.
Introduction¶
Ibex provides a structure for representing sets of \(\mathbb{R}^n\) with boxes and performing operations on sets diretly. Another possible name for such a set would be a paving.
The structure is organized as a binary tree. Each leaf represents a box with a status that indicates whether
the box is inside the set, outside the set or potentially crossing the boundary of the set.
The status is a boolean interval (BoolInterval) which possible values are either YES (inside), NO (outside)
or MAYBE (boundary). This is depicted in the figure below:
Example of “set”, obtained from the constraint \(\|(x,y)\|\le5\).¶
A graphical tool: Vibes¶
In all the examples proposed below, we will display boxes (rectangles) to have a visual rendering of the computations.
In the solutions, we propose to use Vibes but you can easily adapt the code to use your favorite graphical tool.
If you want to use Vibes alos, here is a few tips (valid for Linux and MacOS).
First, install Vibes:
gunzip VIBES-XXX.tar.gz
tar xvf VIBES-XXX.tar
cd VIBES-XXX/viewer
cmake .
make
cd ../..
Vibes is based on a client-server approach, the boxes are sent by the client program through a pipe and plot by another program (the viewer).
To run the viewer:
VIBES-XXX/viewer/VIBes-viewer&
Now, copy the client API in the folder of your C++ program:
cp VIBES-XXX/client-api/C++/src/* [my-folder]
In the client program, include the Vibes API:
#include "ibex.h"
#include "vibes.cpp"
using namespace std;
using namespace ibex;
Then, connect to the server with the following instructions.
int main() {
vibes::beginDrawing ();
vibes::newFigure("....");
...
And disconnect before your program terminantes:
vibes::endDrawing();
Finally, to plot a box ([a,b],[c,d]) just call:
vibes::drawBox(a, b, c, d, "...");
What is between the double quotes is the color code of the box. For instance, “b[r]” will paint the box in red and the contour in blue.
Set Creation¶
A set is an instance of Set and can either be initially defined as \(\mathbb{R}^n\) itself or a specific box:
// create the two-dimensional set (-oo,+oo)x(-oo,+oo)
Set set1(2);
// create the two-dimensional set [0,1]x[0,1]
Set set2(IntervalVector(2,Interval(0,1)));
It can also be initialized from a constraint or a system of constraints. In this case, the set is built by performing some computations recursively, until some precision is reached. The second parameter given to the constructor controls this precision.
Note: the computation performed recursively is an application of the forward-backward separator associated to the constraint.
// Create the constraint ||(x,y)||²<=25
NumConstraint c("x","y","x^2+y^2<=25");
// Create the set with a precision of 0.01
Set set(c,0.01);
The result is the following picture, obtained with Vibes. We explain how we have generated this picture in the next section.
Set Exploration¶
The internal structure of sets is not intended to be handled directly by users (and may actually change with time).
If you want to explore a set, you can use the SetVisitor class (following the
visitor design pattern) . This class must implement a visit_leaf
function that will be automatically called for every leaf of the set. It can also optionnaly implement a visit_node
function that is called for every intermediate node in the tree, and tell wether or not to visit children of the current
node by returning true (default) or false.
A typical usage of a set visitor is for listing or plotting the set and we shall illustrate the mechanism for such usage.
The visit_leaf function must take in argument the information that characterizes a leaf, namely, a box (IntervalVector) and a status
(BoolInterval). Here is an example that simply display the box and the status of a leaf in the standard output:
class ToConsole : public SetVisitor {
/**
* The function that will be called automatically on every boxes (leaves) of the set.
*/
void visit_leaf(const IntervalVector& box, BoolInterval status) {
output << box << " : ";
switch (status) {
case YES: output << "in"; break;
case NO: output << "out"; break;
case MAYBE : output << "?"; break;
}
output << endl;
}
};
Now the following code loads a set from a file an lists all the boxes inside:
Set set("set-example");
ToConsole to_console;
set.visit(to_console);
The result is:
([-inf, -9] ; [-inf, inf]) : out
([-9, 9] ; [-inf, -9]) : out
([-9, -4.5] ; [-9, 0]) : ?
([-4.5, 0] ; [-9, -8]) : ?
([-4.5, 0] ; [-8, 0]) : in
([-9, -4.5] ; [0, 9]) : ?
([-4.5, 0] ; [0, 8]) : in
([-4.5, 0] ; [8, 9]) : ?
([0, 4.5] ; [-9, -8]) : ?
([0, 4.5] ; [-8, 0]) : in
([4.5, 9] ; [-9, 0]) : ?
([0, 4.5] ; [0, 8]) : in
([0, 4.5] ; [8, 9]) : ?
([4.5, 9] ; [0, 9]) : ?
([-9, 9] ; [9, inf]) : out
([9, inf] ; [-inf, inf]) : out
|
|
Visiting the set with |
Visiting the set with |
We will now show how to plot a set calculated by Ibex with Vibes.
We create a new class that implements the visit_leaf function as follows:
class ToVibes : public SetVisitor {
public:
/**
* Plot a box within the frame [-max,max]x[-max,max]
*
* The frame avoids, in particular, to plot unbounded OUT boxes.
*/
ToVibes(double max) : frame(2,max*Interval(-1,1)) { }
/**
* Function that will be called automatically on every boxes (leaves) of the set.
*/
void visit_leaf(const IntervalVector& box, BoolInterval status) {
// Intersect the box with the frame
IntervalVector framebox=box & frame;
// Associate a color to the box.
// - YES (means "inside") is in green
// - NO (means "outside") is in red
// - MAYBE (means "boundary") is in blue.
const char* color;
switch (status) {
case YES: color="g"; break;
case NO: color="r"; break;
case MAYBE : color="b"; break;
}
// Plot the box with Vibes
vibes::drawBox(framebox[0].lb(), framebox[0].ub(), framebox[1].lb(), framebox[1].ub(), color);
}
IntervalVector frame;
};
The main code is similar:
vibes::beginDrawing ();
vibes::newFigure("visit");
Set set("set-example");
ToVibes to_vibes(10);
set.visit(to_vibes);
vibes::endDrawing();
And the result is the picture above.
File operations¶
You can save a set into a file and load a set from a file.
To save into a file named “set-example”:
set.save("set-example");
To load a set from a file, use the constructor with string argument:
Set set("set-example");
Set Intersection¶
A set can be intersected with another set that can either be explicit (of type Set) or implicit.
A contractor and a separator are examples of implicit sets. In this case, we talk about
set contraction rather than intersection (but, conceptually, this is two
equivalent terms when dealing with sets).
We consider here intersection of two explicits sets.
The intersection between two sets is obtained with the &= operator.
In the next example, we create two sets from separators, one being a circle or radius 5,
the other being the complementary of a circle of radius 4. The result of the intersection gives a ring.
// Create a first set ||(x,y)||<=5
NumConstraint c("x","y","x^2+y^2<=25");
Set set(c,0.01);
// Create a second set ||(x,y)||>=4
NumConstraint c2("x","y","x^2+y^2>=16");
Set set2(c2,0.01);
// Intersect the first set with the second one
set &= set2;
The result is the following picture.
Note: It should be emphasized that it is always better to handle sets explicitly on last resort. This means that, in this example, it would have been more efficient to create one set from the conjunction of the two constraints.
Set Union¶
The union works similarly. In the next example, we create two sets, one being a circle centered on the origin and the other the circle centered on the point (5,0). Then we perform the union of the two sets.
// Create a first set ||(x,y)||<=5
NumConstraint c("x","y","x^2+y^2<=25");
Set set(c,0.01);
// Create a second set ||(x-5,y)||<=5
NumConstraint c2("x","y","(x-5)^2+y^2<=25");
Set set2(c2,0.01);
// Make the union
set |= set2;
The result is the following picture.
Set Contraction¶
A separator can be used to contract a set.
The operator is recursively applied on the set until some precision is reached (size of boundary boxes).
We illustrate this by calculating again the “ring” but in a different way. We have already shown how to calculate a ring:
by giving a conjunction of the constraints to the constructor of Set
by computing two sets separately, one for each constraint, and then by performing an intersection
We now create a set for one of the constraint and then contracts this set with the other constraint.
double eps=0.01;
// create the set with one of the constraints
NumConstraint c("x","y","x^2+y^2<=25");
Set set(c,eps);
// create the second constraint
NumConstraint c2("x","y","x^2+y^2>=16");
// create a separator for this constraint
SepFwdBwd sep(c2);
// contract the set with the separator
sep.contract(set,eps);
Set Intervals¶
A set interval [S] (or i-set) [Jaulin 2012] is the given of two sets \((S_1,S_2)\) that represent a lower and upper bound (with respect to the inclusion order) of an unkown set S:
A possible notation (that we use in the code below) for the set interval [S] is: \([S_1,S_2]\).
A set interval can be explicitly represented by an instance of the SetInterval class.
It can also be implicitly represented by a separator. Let us explain how.
A separator S have been used so far to represent a “simple” set (not a set interval)
by two complementary contractions \(C_1\) and \(C_1\), being respectively for the inner and outer part.
This means that the set associated to the separator can be seen as the following
degenerated set interval:
where set(C) designates the set associated to C (the insensitive points).
Now, it is possible to change the status of either the inner or outer contraction to
the special value MAYBE. This means that the contracted part is not inside or
outside the set but potentially inside either one. If we change this way the
status of \(C_1\), the separator is now associated to the set interval:
If we change the status of \(C_2\), we obtain:
The next example illustrates the use of separators to contract a set interval with the following information:
the set is enclosed in the circle centered on the origin and of radius 2
the set encloses n little circles centered on different points and or radius 1
A set interval can be visited exactly like a set and we have used the same ToVibes
class as above for producing the picture below.
double eps=0.001;
// Create the distance function between (x,y)
// and the point (cos(alpha),sin(alpha))
Variable x,y,alpha;
Function f(x,y,alpha,sqr(x-cos(alpha))+sqr(y-sin(alpha)));
// Build the initial box
IntervalVector box(2);
box[0]=Interval(-2,2);
box[1]=Interval(-2,2);
// Create the initial i-set [emptyset,[box]]
SetInterval set(box);
NumConstraint ctr(x,y,sqr(x)+sqr(y)<=4);
// Create a separator for the i-set [emptyset,ctr]
// Initially, the i-set is [ctr,ctr]
SepFwdBwd sep(ctr);
// We set the status of the first contraction to
// "maybe" so that the i-set associated to the separator becomes [emptyset,ctr]
// We contract the set with the separator, i.e.,
// we compute [emptyset,[box]] & [emptyset,ctr]
sep.contract(set,eps,MAYBE,NO);
// Number of points
int n=8;
for (int i=0; i<n; i++) {
NumConstraint ctr(x,y,f(x,y,i*2*Interval::pi()/n)<=0.04);
SepFwdBwd sep(ctr);
// We set the status of the second contraction to
// "maybe" so that the i-set associated to the separator becomes [ctr,R^n]
sep.contract(set,eps,YES,MAYBE);
}
