Unions

Geometry.Unions History

Hide minor edits - Show changes to output

August 06, 2013, at 02:33 PM by Martin Herceg -
Added lines 173-175:
 U.isFullDim()
 U.isBounded()
 U.isConnected()
Deleted lines 177-179:
 U.isConnected()
 U.isFullDim()
 U.isBounded()
August 06, 2013, at 02:32 PM by Martin Herceg -
Changed line 179 from:
to:
%width=400%  Attach:polyunion3.jpg %%
August 06, 2013, at 02:30 PM by Martin Herceg -
Added lines 146-147:
%width=400%  Attach:polyunion1.jpg %%
Added lines 156-157:
%width=400%  Attach:polyunion2.jpg %%
August 06, 2013, at 02:28 PM by Martin Herceg -
Changed line 34 from:
 U.add(Polyhedron)
to:
 U.add( Polyhedron('lb', 1, 'ub', 5) )
August 06, 2013, at 02:26 PM by Martin Herceg -
Added line 74:
%width=400%  Attach:circlebox.jpg %%
August 05, 2013, at 11:47 AM by Martin Herceg -
Changed lines 155-159 from:
 U.isConvex
U.isOverlapping
U.isConnected
U.isFullDim
U.isBounded
to:
 U.isConvex()
U.isOverlapping()
U.isConnected()
U.isFullDim()
U.isBounded()
Changed lines 168-172 from:
 U.isConvex
U.isOverlapping
U.isConnected
U.isFullDim
U.isBounded
to:
 U.isConvex()
U.isOverlapping()
U.isConnected()
U.isFullDim()
U.isBounded()
August 02, 2013, at 12:23 PM by Martin Herceg -
Changed lines 66-71 from:
The @@Data@@ property can be modified after the object has been created, other properties are not changeable.


[[#PolyUnion]]
!!!
The '''PolyUnion''' object - unions of polyhedra
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:
to:
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:
Changed lines 68-71 from:
 P(1) = Polyhedron( 'lb', -10, 'ub', -5);
 P(
2) = Polyhedron( 'lb', -5, 'ub', 5);
 P(3) = Polyhedron( 'lb', 5, 'ub', 10);
 U = PolyUnion
(P)
to:
 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
)
Changed line 74 from:
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:
to:
The total number of sets in the union is given by the property
Changed lines 76-78 from:
 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])
to:
 U.Num
Changed line 78 from:
The dimension of the @@PolyUnion@@ object can be retrieved from @@Dim@@ property:
to:
and the individual sets can be acessed by index in the @@Set@@ property in the order as they were stored
Changed lines 80-81 from:
 U.Dim
to:
 B = U.Set(1)
 C = U.Set(2)
Changed lines 83-87 from:
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.
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:
to:



[[#PolyUnion]]
!!! The '''PolyUnion''' object - unions of polyhedra
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:
(:source lang=MATLAB -getcode:) [@
 P(1) = Polyhedron( 'lb', -10, 'ub', -5);
 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:
(:source lang=MATLAB -getcode:) [@
 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])
@]
The dimension of the @@PolyUnion@@ object can be retrieved from @@Dim@@ property:
(:source lang=MATLAB -getcode:) [@
 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.
(:source lang=MATLAB -getcode:) [@
 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:
(:source lang=MATLAB -getcode:) [@
 U.Set(2)
@]
If other user data have been stored with the object, it can be accessed in @@Data@@ property
(:source lang=MATLAB -getcode:) [@
 U.Data
@]

August 02, 2013, at 11:55 AM by Martin Herceg -
Added lines 125-137:
 U.isConvex
 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
(:source lang=MATLAB -getcode:) [@
 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)
August 02, 2013, at 10:14 AM by Martin Herceg -
Added lines 122-129:
@]
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:
(:source lang=MATLAB -getcode:) [@
 U.isConvex
 U.isOverlapping
 U.isConnected
 U.isFullDim
 U.isBounded
August 02, 2013, at 09:55 AM by Martin Herceg -
Changed lines 115-122 from:
to:
Example of a non-convex union:
(:source lang=MATLAB -getcode:) [@
 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);
@]
August 02, 2013, at 09:37 AM by Martin Herceg -
Added lines 108-116:
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
(:source lang=MATLAB -getcode:) [@
 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);
@]

August 02, 2013, at 09:28 AM by Martin Herceg -
Added lines 101-108:

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

August 02, 2013, at 09:15 AM by Martin Herceg -
Changed lines 92-100 from:
to:
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:
(:source lang=MATLAB -getcode:) [@
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)
@]
Removing the polyhedron from the @@PolyUnion@@ object is based on an index of the set which to remove, i.e.
(:source lang=MATLAB -getcode:) [@
U.remove(2)
@]
August 02, 2013, at 08:59 AM by Martin Herceg -
Changed lines 84-91 from:
to:
The dimension of the @@PolyUnion@@ object can be retrieved from @@Dim@@ property:
(:source lang=MATLAB -getcode:) [@
 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.
August 02, 2013, at 08:49 AM by Martin Herceg -
Added line 84:
August 02, 2013, at 08:47 AM by Martin Herceg -
Added lines 77-82:
@]
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:
(:source lang=MATLAB -getcode:) [@
 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])
August 02, 2013, at 08:37 AM by Martin Herceg -
Changed line 58 from:
* @@Set@@ - indicates the stored sets of the union in a cell array
to:
* @@Set@@ - stored sets of the union in a cell array
Added lines 71-77:
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:
(:source lang=MATLAB -getcode:) [@
 P(1) = Polyhedron( 'lb', -10, 'ub', -5);
 P(2) = Polyhedron( 'lb', -5, 'ub', 5);
 P(3) = Polyhedron( 'lb', 5, 'ub', 10);
 U = PolyUnion(P)
@]
July 31, 2013, at 03:26 PM by Martin Herceg -
Added lines 50-54:
or attached after creation of the object
(:source lang=MATLAB -getcode:) [@
 U.Data.c = 2.1;
@]

July 31, 2013, at 03:25 PM by Martin Herceg -
Changed lines 36-37 from:

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.
to:
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.
Added lines 38-42:
 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.
(:source lang=MATLAB -getcode:) [@
Changed line 51 from:
 There are three properties of the @@Union@@ object:
to:
There are three properties of the @@Union@@ object:
Changed line 53 from:
* @@Set@@ - stores the sets of the union in a cell array
to:
* @@Set@@ - indicates the stored sets of the union in a cell array
Changed line 61 from:
to:
The @@Data@@ property can be modified after the object has been created, other properties are not changeable.
July 31, 2013, at 03:20 PM by Martin Herceg -
Changed lines 10-57 from:
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. There are three properties of the @@Union@@ object
to:
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:
(:source lang=MATLAB -getcode:) [@
 P(1) = Polyhedron('lb', -1, 'ub', 1);
 P(2) = Polyhedron('lb', 1);
 U = Union(P)
@]
The same applies for @@YSet@@ objects
(:source lang=MATLAB -getcode:) [@
 x = sdpvar;
 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
(:source lang=MATLAB -getcode:) [@
 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)
@]
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.
(:source lang=MATLAB -getcode:) [@
 U.add(Polyhedron)
@]

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.
(:source lang=MATLAB -getcode:) [@
 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)
@]

 There are three properties of the @@Union@@ object:
* @@Num@@ - indicates the number of sets in the union
* @@Set@@ - stores the 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.
(:source lang=MATLAB -getcode:) [@
 U.Num
 U.Set
 U.Data
@]

July 31, 2013, at 02:27 PM by Martin Herceg -
Added lines 7-14:

[[#Union]]
!!! The '''Union''' object - unions of general convex sets
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. There are three properties of the @@Union@@ object


[[#PolyUnion]]
!!! The '''PolyUnion''' object - unions of polyhedra
July 31, 2013, at 02:18 PM by Martin Herceg -
Added lines 1-10:
!! Objects for representation of unions of sets

* [[Geometry.Unions#Union | The '''Union''' object - unions of general convex sets]]
* [[Geometry.Unions#PolyUnion | The '''PolyUnion''' object - unions of polyhedra]]

----



Back to [[Geometry.Geometry|computational geometry]] overview.