OperationsWithSets

Geometry.OperationsWithSets History

Hide minor edits - Show changes to output

Changed line 96 from:
 b = [1.72 3.84 3.05 0.03];
to:
 b = [1.72; 3.84; 3.05; 0.03];
August 06, 2013, at 02:02 PM by Martin Herceg -
Changed line 196 from:
!!!! Extreme point in a given dimension
to:
!!!! Extreme point in a given direction
August 06, 2013, at 02:00 PM by Martin Herceg -
Changed lines 6-14 from:
to:
** [[#SetContainment| Set containment]]
** [[#Distance | Distance to a point ]]
** [[#Projection | Project a point onto the set]]
** [[#Separation | Separation hyperplane]]
** [[#Extreme | Extreme points]]
** [[#Support | Support ]]
** [[#Shoot | Ray shooting ]]
** [[#OuterApprox | Outer approximation using a bounding box ]]

Added line 107:
[[#SetContainment]]
Added line 130:
[[#Distance]]
Added line 154:
[[#Projection]]
Added line 177:
[[#Separation]]
Added line 195:
[[#Extreme]]
Added line 223:
[[#Support]]
Added line 235:
[[#Shoot]]
Added line 256:
[[#OuterApprox]]
August 06, 2013, at 01:52 PM by Martin Herceg -
Added lines 240-270:

!!!! Outer approximation
Computation of the bounding box over the set is implemented in @@outerApprox@@ method:
(:source lang=MATLAB -getcode:) [@
 B = S.outerApprox()
@]
The method returns a polyhedron with lower and upper bounds that are stored internally and can be accessed by referring to @@Internal@@ property
(:source lang=MATLAB -getcode:) [@
B.Internal.lb

ans =

  -0.6775
  -2.9647

B.Internal.ub

ans =

  11.6969
    7.2648
@]
Comparison of the bounding box @@B@@ wih the orignal set @@S@@ can be found on the figure below which was generated with the following command:
(:source lang=MATLAB -getcode:) [@
 S.plot('color', 'salmon');
 hold on
 B.plot('wire', true, 'linestyle', '--', 'linewidth', 2)
 hold off
@]
%width=400%  Attach:pushchair_bbox.jpg %%

August 06, 2013, at 01:39 PM by Martin Herceg -
Changed lines 222-224 from:
The ray-shooting problem is given by @@{ max alpha s.t. alpha*x in Set }@@ and is available in the @@shoot@@ method. As an example, consider computation of the maximum of the set for the point @@x2 = [15; 0]@@

to:
The ray-shooting problem is given by @@{ max alpha s.t. alpha*x in Set }@@ and is available in the @@shoot@@ method. As an example, consider computation of the maximum of the set in the direction of the point @@x2 = [15; 0]@@ which gives the value of @@alpha@@
(:source lang=MATLAB -getcode:) [@
 alpha = S.shoot( x2 )

 alpha =

    0.7586
@]
Multiplying this value with the point @@x2@@ one obtains the point @@v = alpha * x2@@ that lies on the boundary of the set
(:source lang=MATLAB -getcode:) [@
 v = alpha * x2
 
 v =

  11.3788
        0
@]
%width=400%  Attach:pushchair_shoot.jpg %%
August 06, 2013, at 12:48 PM by Martin Herceg -
Changed line 207 from:
One can visually inspect the location of the computed extreme points @@v1@@ and @@v2@@ in the figure below:
to:
One can visually inspect the location of the computed extreme points @@v1.x@@ and @@v2.x@@ in the figure below:
Added lines 209-223:

!!!! Computing a support of the set in a given direction
For a given point @@x@@, the support of a set is given as @@{ max x'*y s.t. y in Set }@@. This feature is implemented in the @@support@@ method. The syntax of the @@support@@ method requires a point @@x@@ which determines the direction and the value of the maximum over the set is returned.
(:source lang=MATLAB -getcode:) [@
S.support(x3)

ans =

  36.3241
@]
Note that computation of the support is available also in the @@extreme@@ method.

!!!! Maximum over the set in a given direction - ray shooting
The ray-shooting problem is given by @@{ max alpha s.t. alpha*x in Set }@@ and is available in the @@shoot@@ method. As an example, consider computation of the maximum of the set for the point @@x2 = [15; 0]@@

August 06, 2013, at 12:29 PM by Martin Herceg -
Changed lines 183-208 from:
to:
!!!! Extreme point in a given dimension
Computation of extreme points for a convex set is implemented in the @@extreme@@ method. The method accepts a point as an argument that specifies the direction in which to compute the extreme point. For instance, for the point @@x2@@, the @@extreme@@ method results in
(:source lang=MATLAB -getcode:) [@
 v1 = S.extreme( x2 )
 
v1 =

    exitflag: 1
        how: 'Successfully solved (SeDuMi-1.3)'
          x: [2x1 double]
        supp: 175.4535
@]
The output variable @@v1@@ contains the status returned from the optimization solver  in @@exitflag@@ and  @@how@@ fields. The extreme point is stored in @@x@@ variable and the field @@supp@@ corresponds to a support of the set given as @@{ max x'*y s.t. y in Set }@@. The extreme point in the direction @@x3 = [0; 5]@@ is given as
(:source lang=MATLAB -getcode:) [@
 x3 = [0; 5];
 v2 = S.extreme( x3 )

 v2 =

    exitflag: 1
        how: 'Successfully solved (SeDuMi-1.3)'
          x: [2x1 double]
        supp: 36.3241
@]
One can visually inspect the location of the computed extreme points @@v1@@ and @@v2@@ in the figure below:
%width=400%  Attach:pushchair_extreme.jpg %%
August 06, 2013, at 11:58 AM by Martin Herceg -
Changed lines 167-184 from:
The @@YSet@@ object implements a method for computing a separation hyperplane from a point which is accessed as @@separate@@ method.
to:
The @@YSet@@ object implements the @@separate@@ method that computes a hyperplane that separates the set from a given point. As an example, consider computation of a separating hyperplane from the set @@S@@ and the point @@x2@@:
(:source lang=MATLAB -getcode:) [@
 He = S.separate(x2)

 He  =

  -3.4346    0.7044  -45.3730

@]
which returns a data corresponding to a hyperplane equation @@{ x |  He*[x; -1] = 0 }@@. To plot the computed hyperplane, a @@Polyhedron@@ object is constructed
(:source lang=MATLAB -getcode:) [@
 P = Polyhedron('He', He)
@]
and plotted.
%width=400%  Attach:pushchair_separate.jpg %%


August 06, 2013, at 10:26 AM by Martin Herceg -
Changed line 144 from:
!!!! Projection of a point to a set
to:
!!!! Point projection onto a set
August 06, 2013, at 10:21 AM by Martin Herceg -
Changed line 121 from:
!!!! Distance to the point
to:
!!!! Distance to a point
Added lines 143-167:

!!!! Projection of a point to a set
Computation of the distance is achieved also in the @@project@@ method which computes the closest point to the set. For the point @@x2@@ the projection operation results in a structure with four fields
(:source lang=MATLAB -getcode:) [@
 res = S.project(x2)

 res =

    exitflag: 1
        how: 'Successfully solved (SeDuMi-1.3)'
          x: [2x1 double]
        dist: 3.5061
@]
The field @@exitflag@@ informs about the status returned from the optimization solver which can be found also in the @@how@@ field. The closed point is computed in @@x@@ field and the value about the distance can be found in @@dist@@ field. One can verify that the computed point by the @@projection@@ operation is the same as by @@distance@@ operation
(:source lang=MATLAB -getcode:) [@
 res.x

ans =

  11.5654
    0.7044
@]

!!!! Separation hyperplane from a point
The @@YSet@@ object implements a method for computing a separation hyperplane from a point which is accessed as @@separate@@ method.
August 06, 2013, at 10:08 AM by Martin Herceg -
Changed line 110 from:
but the point @@x2 = [12; 0]@@ lies not:
to:
but the point @@x2 = [15; 0]@@ lies not:
Changed line 112 from:
x2 = [12; 0];
to:
x2 = [15; 0];
Changed lines 122-142 from:
to:
Computing distance from the set to a given point is achieved using @@distance@@ method. For instance, the distance to the point @@x2@@ that lies outside of the set @@S@@ can be computed as follows
(:source lang=MATLAB -getcode:) [@
 data = S.distance(x2)

ans =

    exitflag: 1
        dist: 0.5932
          x: [2x1 double]
          y: [2x1 double]
@]
The output from the method is a structure with four fields indicating the result of the computing the distance. The field @@exitflag@@ indicates the exit status from the optimization solver, the actual distance is available in @@dist@@ field and fields @@x@@, @@y@@ indicate the coordinates of the two points for which the distance has been computed. It can be extracted from the field @@y@@ which point is the closest to the point @@x2@@ and plotted.
(:source lang=MATLAB -getcode:) [@
data.y

ans =

  11.5654
    0.7044
@]
%width=400%  Attach:pushchair_distance.jpg %%
August 06, 2013, at 09:56 AM by Martin Herceg -
Added lines 120-121:

!!!! Distance to the point
August 06, 2013, at 09:53 AM by Martin Herceg -
Changed lines 97-98 from:

to:
This set will be used next to demonstrate some methods that can be applied to @@YSet@@ objects.

!!!! Set containment test
To check if the point is contained in the set or not, there exist a method @@contains@@. For instance, the point @@x1=[8; 0]@@ lies in the set
(:source lang=MATLAB -getcode:) [@
x1 = [8; 0];
S.contains(x1)

ans =

    1
@]

but the point @@x2 = [12; 0]@@ lies not:
(:source lang=MATLAB -getcode:) [@
x2 = [12; 0];
S.contains( x2 )

ans =

    0
@]
%width=400%  Attach:pushchair_setcontainment.jpg %%
August 06, 2013, at 09:36 AM by Martin Herceg -
Changed lines 1-2 from:
!!Geometric operatioins with convex sets
to:
!!Geometric operations with convex sets
Deleted line 81:
Added lines 84-97:
The @@ConvexSet@@ class offers a couple of methods for use in computational geometry. Consider a following set which is created as an intersection of quadratic and linear constraints
(:source lang=MATLAB -getcode:) [@
 x = sdpvar(2, 1);
 A = [-0.46 -0.03; 0.08 -1.23; -0.92 -1.9; -1.92  2.37];
 b = [1.72 3.84 3.05 0.03];
 constraints = [ 0.2*x'*x-[2.1 0.8]*x<=2; A*x<=b ];
 S = YSet(x, constraints);
@]
which is plotted in salmon color
(:source lang=MATLAB -getcode:) [@
 S.plot('color', 'salmon')
@]
%width=400%  Attach:pushchair_set.jpg %%

August 05, 2013, at 02:47 PM by Martin Herceg -
Added line 36:
!!! Working with multiple sets
Changed line 64 from:
To create a new copy of the @@ConvexSet@@, the @@copy@@ must be employed, otherwise the new object points to the same data stored in the original object
to:
If the sets are stored in an array, some methods can operate on the array, for instance
Changed lines 66-67 from:
Snew = S.copy()
to:
row_array1.isBounded()
column_array2.isEmptySet
()
Added lines 69-80:
If the method is not applicable on the array, it can be invoked for each element in the array using @@forEach@@ method:
(:source lang=MATLAB -getcode:) [@
statement = row_array1.forEach(@isBounded)
@]
The @@forEach@@ method is a fast replacement of for-loop and it can be useful for user-specific operations over an array of convex sets.

To create a new copy of the @@ConvexSet@@, the @@copy@@ must be employed, otherwise the new object points to the same data stored in the original object
(:source lang=MATLAB -getcode:) [@
Snew = S.copy()
@]

August 05, 2013, at 02:36 PM by Martin Herceg -
Changed lines 50-52 from:
(:comment
Note that in general, when constructing a set with nonlinear constraints, an appropriate nonlinear optimization solver needs to be present. Typically, if you have Optimization Toolbox installed on your Matlab distribution, then the problem is passed to FMINCON solver.
:)
to:
(:comment Note that in general, when constructing a set with nonlinear constraints, an appropriate nonlinear optimization solver needs to be present. Typically, if you have Optimization Toolbox installed on your Matlab distribution, then the problem is passed to FMINCON solver. :)
August 05, 2013, at 02:35 PM by Martin Herceg -
Added line 50:
(:comment
Changed lines 52-53 from:
to:
:)
Deleted lines 68-69:

August 05, 2013, at 02:22 PM by Martin Herceg -
Added line 4:
* [[Geometry.OperationsWithSets#MultipleSets | Working with multiple sets ]]
Deleted lines 16-18:
(:comment
Note that in general, when constructing a set with nonlinear constraints, an appropriate nonlinear optimization solver needs to be present. Typically, if you have Optimization Toolbox installed on your Matlab distribution, then the problem is passed to FMINCON solver.
:)
Changed lines 35-36 from:
To create a new copy of the @@ConvexSet@@, the @@copy@@ must be employed, otherwise the new object points to the same data stored in the original object
to:
[[#MultipleSets]]
Consider following two sets created with
the help of YALMIP
Changed lines 38-43 from:
Snew = S.copy()
to:
 z = sdpvar;
 t = sdpvar;
 constraints1 = [ z^2 - 5*t <= 1 ;  0 <= t <= 1 ];
 
S = YSet( [z; t], constraints1);
 constraints2 = [ z^2 + 5*t <= 1 ;  0 <= t <= 1 ];
 R = YSet( [z; t], constraints2);
Added lines 45-67:
which are plotted in different colors
(:source lang=MATLAB -getcode:) [@
 plot(S, 'color', 'lightgreen', R, 'color', 'yellow')
@]
%width=400%  Attach:vase_set.jpg %%
Note that in general, when constructing a set with nonlinear constraints, an appropriate nonlinear optimization solver needs to be present. Typically, if you have Optimization Toolbox installed on your Matlab distribution, then the problem is passed to FMINCON solver.

The above sets can be concatenated into an array using overloaded @@[ ]@@ operators. The column concatenation can be done using brackets or @@vertcat@@ method which are equivalent:
(:source lang=MATLAB -getcode:) [@
column_array1 = [S; R]
column_array2 = vertcat(S, R)
@]
The row concatenation using brackets or @@horzcat@@ method
(:source lang=MATLAB -getcode:) [@
row_array1 = [S, R]
row_array2 = horzcat(S, R)
@]

To create a new copy of the @@ConvexSet@@, the @@copy@@ must be employed, otherwise the new object points to the same data stored in the original object
(:source lang=MATLAB -getcode:) [@
Snew = S.copy()
@]

August 05, 2013, at 01:54 PM by Martin Herceg -
August 05, 2013, at 01:51 PM by Martin Herceg -
Changed line 3 from:
* [[Geometry.OperationsWithSets#BasicProperties | Determining basic properties ]]
to:
* [[Geometry.OperationsWithSets#BasicProperties | Methods for determining basic properties ]]
Changed lines 9-10 from:
!!! Determining basic properties of the '''YSet''' object
Consider the following example where the set is build from nonlinear constraints
to:
!!! Methods for determining basic properties of sets
Consider the following example where the set is built from the following constraints
Changed line 13 from:
 constraints = [ 0 <= x <= 5; 4*x(1)^2 - 2*x(2) >= 0.4; sqrt( x(1)^2 + 0.6*x(2)^2 ) <= 1.3 ];
to:
 constraints = [ 0 <= x <= 5; 4*x(1)^2 - 2*x(2) <= 0.4; sqrt( x(1)^2 + 0.6*x(2)^2 ) <= 1.3 ];
Added lines 16-18:
(:comment
Note that in general, when constructing a set with nonlinear constraints, an appropriate nonlinear optimization solver needs to be present. Typically, if you have Optimization Toolbox installed on your Matlab distribution, then the problem is passed to FMINCON solver.
:)
Changed lines 31-42 from:
 
to:
%width=400%  Attach:plum_pie_set.jpg %%
Note that plotting of general convex sets could become time consuming because the set is sampled with an uniform grid. The value of the grid can be changed using the @@grid@@ option of the @@plot@@ method, for details type
(:source lang=MATLAB -getcode:) [@
help ConvexSet/plot
@]

To create a new copy of the @@ConvexSet@@, the @@copy@@ must be employed, otherwise the new object points to the same data stored in the original object
(:source lang=MATLAB -getcode:) [@
Snew = S.copy()
@]

August 05, 2013, at 01:06 PM by Martin Herceg -
August 05, 2013, at 01:06 PM by Martin Herceg -
Changed line 18 from:
 S.isEmptySet
to:
 S.isEmptySet()
Changed lines 20-21 from:

to:
Another useful property is boundedness which can be checked using the @@isBounded@@ method, i.e.
(:source lang=MATLAB -getcode:) [@
 S.isBounded()
@]
These properties can be veriefied by plotting the set using @@plot@@ method
(:source lang=MATLAB -getcode:) [@
 S.plot('color', 'lightblue', 'linewidth', 2, 'linestyle', '--')
@]
 
August 05, 2013, at 12:42 PM by Martin Herceg -
Added lines 1-28:
!!Geometric operatioins with convex sets

* [[Geometry.OperationsWithSets#BasicProperties | Determining basic properties ]]
* [[Geometry.OperationsWithSets#GeometricMethods | Geometric methods ]]

----

[[#BasicProperties]]
!!! Determining basic properties of the '''YSet''' object
Consider the following example where the set is build from nonlinear constraints
(:source lang=MATLAB -getcode:) [@
 x = sdpvar(2, 1);
 constraints = [ 0 <= x <= 5; 4*x(1)^2 - 2*x(2) >= 0.4; sqrt( x(1)^2 + 0.6*x(2)^2 ) <= 1.3 ];
 S = YSet(x, constraints);
@]
It is very often of interest to check wheter the set is empty or not. In MPT there exist an @@isEmptySet@@ method that checks whether the set is empty
(:source lang=MATLAB -getcode:) [@
 S.isEmptySet
@]



[[#GeometricMethods]]
!!! Geometric methods



Back to [[Geometry| Computational Geometry]] overview.