Geometry /

The `Union`

object is the high level class for representing unions of convex sets. The union can be comprised of any sets derived from the `ConvexSet`

class, such as `YSet`

and `Polyhedron`

objects. To construct the `Union`

object, it suffices to provide the sets concatenated in an array as an argument:

P(1) = Polyhedron('lb', -1, 'ub', 1);

P(2) = Polyhedron('lb', 1);

U = Union(P)

P(2) = Polyhedron('lb', 1);

U = Union(P)

The same applies for `YSet`

objects

x = sdpvar;

S(1) = [ x <= -2 ];

S(2) = [ -2 <= x <= 2 ];

S(3) = [ x >= 2];

U = Union(S)

S(1) = [ x <= -2 ];

S(2) = [ -2 <= x <= 2 ];

S(3) = [ x >= 2];

U = Union(S)

To create union that combines `Polyhedron`

and `YSet`

objects, one can employ `add`

method, for instance

x = sdpvar(2,1);

S = YSet(x, [ x(1) + x(2) <= 1; -2*x(2) + 0.5*x(1) >= 2.3 ]);

P = Polyhedron('A', randn(4,3), 'b', rand(4,1));

U = Union(S)

U.add(P)

S = YSet(x, [ x(1) + x(2) <= 1; -2*x(2) + 0.5*x(1) >= 2.3 ]);

P = Polyhedron('A', randn(4,3), 'b', rand(4,1));

U = Union(S)

U.add(P)

Note that the sets do not have to be in the same dimension. In the above example, the set "S" is in dimension 2 whereas the set "P" is in the dimension 3. Other sets can be added using the `add`

method, e.g.

U.add( Polyhedron('lb', 1, 'ub', 5) )

The set can be also removed from the union. This is achieved with `remove`

method by referring to the index of the set to remove, e.g.

U.remove(3)

It is possible to store arbitrary data with the `Union`

object. The user data can be provided in the extended syntax at the time of construction, e.g.

d.a = -2.5;

d.b = 0.8;

z = sdpvar(2,1);

S(1) = YSet(z, [ cone(z(1),z(2)); 0 <= z <= 1]);

S(2) = YSet(z, [ z(1)-2*z(2) <= 0.4; 0.1*z(2) <= 0.1]);

U = Union('Set', S, 'Data', d)

d.b = 0.8;

z = sdpvar(2,1);

S(1) = YSet(z, [ cone(z(1),z(2)); 0 <= z <= 1]);

S(2) = YSet(z, [ z(1)-2*z(2) <= 0.4; 0.1*z(2) <= 0.1]);

U = Union('Set', S, 'Data', d)

or attached after creation of the object

U.Data.c = 2.1;

There are three properties of the `Union`

object:

`Num`

- indicates the number of sets in the union`Set`

- stored sets of the union in a cell array`Data`

- place for storing arbitrary user data with the union

The properties can be accessed by referring to their names, i.g.

U.Num

U.Set

U.Data

U.Set

U.Data

The `Data`

property can be modified after the object has been created, other properties are not changeable. The properties are useful when extracting information about the union, for instance, consider the union of a box and a circle:

box = Polyhedron('lb', [-2; -2], 'ub', [0; 0]);

x = sdpvar(2,1);

circle = YSet(x, [ norm(x-1, 2) < 3 ] );

U = Union(box);

U.add(circle)

x = sdpvar(2,1);

circle = YSet(x, [ norm(x-1, 2) < 3 ] );

U = Union(box);

U.add(circle)

The total number of sets in the union is given by the property

U.Num

and the individual sets can be acessed by index in the `Set`

property in the order as they were stored

B = U.Set(1)

C = U.Set(2)

C = U.Set(2)

The `PolyUnion`

objects represents unions of polyhedra in the same dimension. The dimension check is the only requirement for construction of `PolyUnion`

objects. To construct a `PolyUnion`

object an union one has to supply an array of polyhedra in the same dimension. In the next example it is shown how to construct an union of three intervals in dimension one:

P(1) = Polyhedron( 'lb', -10, 'ub', -5);

P(2) = Polyhedron( 'lb', -5, 'ub', 5);

P(3) = Polyhedron( 'lb', 5, 'ub', 10);

U = PolyUnion(P)

P(2) = Polyhedron( 'lb', -5, 'ub', 5);

P(3) = Polyhedron( 'lb', 5, 'ub', 10);

U = PolyUnion(P)

In this example an union of two polyhedra is constructed in dimension 2 - the first polyhedron is in V-representation and the second in H-representation:

R = Polyhedron( [-1.0 -0.8; -2.9 1.4; 0.3 -0.7; 1.3 -1.7; -0.1 -0.2], [2.1; 3.4; 0.5; 5.1; 0.8]);

S = Polyhedron( [-4.3 0.3; -6.0 -5.5; 0.0 7.6; -3.8 1.8]);

U = PolyUnion([R, S])

S = Polyhedron( [-4.3 0.3; -6.0 -5.5; 0.0 7.6; -3.8 1.8]);

U = PolyUnion([R, S])

The dimension of the `PolyUnion`

object can be retrieved from `Dim`

property:

U.Dim

other properties are inherited from the `Union`

object:

`Num`

- the number of polyhedra in the union,`Set`

- stored polyhedra in a polyhedron array,`Data`

- arbitrary user data stored.

The number of sets forming in the union can be read in `Num`

property, i.e.

U.Num

To access the individual sets from the `PolyUnion`

object one can use the `Set`

property, for instance the second polyhedron can be read by pointing to it with index 2:

U.Set(2)

If other user data have been stored with the object, it can be accessed in `Data`

property

U.Data

Polyhedra can be added/removed from the `PolyUnion`

object. To add new polyhedra to the union, the dimension must be retained and the added polyhedron must not be empty:

T = Polyhedron('A', [ 2.5 -0.6; 0.1 -0.08; -1.9 -0.4; 1.7 0.8], 'b', [5.5; 3.8; 4.9; 7.5], 'Ae', [ 0.5 -0.2], 'be', 1.2);

U.add(T)

U.add(T)

Removing the polyhedron from the `PolyUnion`

object is based on an index of the set which to remove, i.e.

U.remove(2)

For the usage in computational geometry it is of intereset to exploit the properties of the union of polyhedra, such as convexity and overlaps. If these properties are know at the time of the construction of the `PolyUnion`

object, one can associate these properties directly to the union. The following properties can be attached to the `PolyUnion`

object:

`Convex`

- logical flag indicating if the union convex or not`Overlaps`

- logical flag indicating if the polyhedra in union overlap or not`FullDim`

- logical flag indicating if the union is build from just from full-dimensial polyhedra or not`Bounded`

- logical flag indicating if the union is build from just from bounded polyhedra or not`Connected`

- logical flag indicating if the union convex is connected or disconnected

For instance, in the next example the union of polyhedra is build only from bounded polyhedra that are connected, not-overlapping and build a convex union

P(1) = Polyhedron([0 0; 1 0; 1 1; 0 1]);

P(2) = Polyhedron([1 0; 2 0; 2 1; 1 1]);

P(3) = Polyhedron([0 1; 1 3; 2 1]);

U = PolyUnion('Set', P, 'Bounded', true, 'Connected', true, 'Overlaps', false, 'Convex', true);

P(2) = Polyhedron([1 0; 2 0; 2 1; 1 1]);

P(3) = Polyhedron([0 1; 1 3; 2 1]);

U = PolyUnion('Set', P, 'Bounded', true, 'Connected', true, 'Overlaps', false, 'Convex', true);

Example of a non-convex union:

Q(1) = Polyhedron([0 -2; -1 -1; -1 1; 0 2]);

Q(2) = Polyhedron([0 -2; 1 -1; 1 1; 0 2]);

Q(3) = Polyhedron('V', [-1 -1; -1 1], 'R', [-1 0.2; -1 -0.2]);

Q(4) = Polyhedron('V', [1 -1; 1 1], 'R', [1 0.2; 1 -0.2]);

U = PolyUnion('Set', Q, 'Convex', false, 'Connected', true, 'Bounded', false);

Q(2) = Polyhedron([0 -2; 1 -1; 1 1; 0 2]);

Q(3) = Polyhedron('V', [-1 -1; -1 1], 'R', [-1 0.2; -1 -0.2]);

Q(4) = Polyhedron('V', [1 -1; 1 1], 'R', [1 0.2; 1 -0.2]);

U = PolyUnion('Set', Q, 'Convex', false, 'Connected', true, 'Bounded', false);

If the properties of the union are not provided at the construction, the `PolyUnion`

class contains methods for determining convexity, overlaps, connectivity, full-dimensionality and boundedness. Please note, that some of these methods are computationally expensive and the computation may be time consuming:

U.isConvex()

U.isOverlapping()

U.isConnected()

U.isFullDim()

U.isBounded()

U.isOverlapping()

U.isConnected()

U.isFullDim()

U.isBounded()

Consider the following example, which is constructed out of four polyhedra without specifying any properties. The convexity, overlaps, connectivity, full-dimensionality and boundedness properties of the union can be obtained as

R(1) = Polyhedron('lb', [-2;-2], 'ub', [0; 0]);

R(2) = Polyhedron('A', [-1 0.5; 0.4 -2.5; -7.5 0.2], 'b', [0.4; -0.3; 1.5]);

R(3) = Polyhedron('A', [2.5 1.6; 0.3 -1.2; -0.8 -0.1; 0.7 -1.2; -2.3 -1.4; 0.3 0.3], 'b', [2.3; 4.2; 1.9; 0.5; 1.5; 0.8], 'Ae', [0.1 -3.2], 'be', 0.5 );

R(4) = Polyhedron('V', [0.4 -0.4; -0.1 0.8; 0.1 -1.3]);

U = PolyUnion(R)

U.isFullDim()

U.isBounded()

U.isConnected()

U.isConvex()

U.isOverlapping()

R(2) = Polyhedron('A', [-1 0.5; 0.4 -2.5; -7.5 0.2], 'b', [0.4; -0.3; 1.5]);

R(3) = Polyhedron('A', [2.5 1.6; 0.3 -1.2; -0.8 -0.1; 0.7 -1.2; -2.3 -1.4; 0.3 0.3], 'b', [2.3; 4.2; 1.9; 0.5; 1.5; 0.8], 'Ae', [0.1 -3.2], 'be', 0.5 );

R(4) = Polyhedron('V', [0.4 -0.4; -0.1 0.8; 0.1 -1.3]);

U = PolyUnion(R)

U.isFullDim()

U.isBounded()

U.isConnected()

U.isConvex()

U.isOverlapping()

Back to computational geometry overview.