Geometry.OperationsWithPolyhedra History
Hide minor edits - Show changes to output
Added lines 23-33:
For further help on the methods of the @@Polyhedron@@ class, type @@help@@ at the Matlab prompt. For instance, to obtain the help description for Minkowski summation in @@plus@@ method, type
(:source lang=MATLAB -getcode:) [@
help Polyhedron/plus
@]
or display the Matlab documentation that contains additional examples on the geometric methods
(:source lang=MATLAB -getcode:) [@
mptdoc
@]
and search for the specific method there.
Added lines 15-16:
** @@plus@@ - Minkowski summation
** @@minus@@ - Pontryagin difference
Deleted line 22:
Added lines 9-20:
** @@affineHull@@ - affine hull
** @@affineMap@@ - affine maps
** @@invAffineMap@@ - inverse affine maps
** @@grid@@ - regular grid of the polytope
** @@meshGrid@@ - grid given as coordinates for 2D polytopes
** @@mldivide@@ - set difference
** @@normalize@@ - normalization of H-representation
** @@project@@ - project a point onto a set
** @@projection@@ - orthogonal projection onto axis
** @@slice@@ - cuts of polyhedra
** @@triangulate@@ - triangulation
** @@volume@@ - computing a volume
Changed line 251 from:
Computation of the Chebyshev center corresponds to inscribing a circle inside a polyhedron which is implemented in the @@chebyCenter@@ method. The circle is described as {$ \{ x ~|~ \| x-x_c \|_2 \le r \} $} where {$x_c$} is the center and {$ r $} is the radius. Consider the following polyhedron
to:
Computation of the Chebyshev center corresponds to inscribing the largest ball inside a polyhedron which is implemented in the @@chebyCenter@@ method. The ball is described as {$ \{ x ~|~ \| x-x_c \|_2 \le r \} $} where {$x_c$} is the center of the ball and {$ r $} is the radius. Consider the following polyhedron
Changed line 255 from:
The data of the circle can be computed by calling
to:
The data of the ball can be computed by calling
Changed line 265 from:
where the field @@x@@ represents the center and @@r@@ is the radius. The field @@exitflag@@ is the status returned from the optimization solver. As the circle is a convex set, it can be represented as @@YSet@@ object and plotted together with the polyhedron
to:
where the field @@x@@ represents the center and @@r@@ is the radius. The field @@exitflag@@ is the status returned from the optimization solver. As the ball is a convex set, it can be represented as @@YSet@@ object and plotted together with the polyhedron
Changed line 251 from:
Computation of the Chebyshev center corresponds to inscribing a circle inside a polyhedron which is implemented in the @@chebyCenter@@ method. The circle is described as {$ x | \| x-x_c \|_2 \le r $} where {$x_c$} is the center and {$ r $} is the radius. Consider the following polyhedron
to:
Computation of the Chebyshev center corresponds to inscribing a circle inside a polyhedron which is implemented in the @@chebyCenter@@ method. The circle is described as {$ \{ x ~|~ \| x-x_c \|_2 \le r \} $} where {$x_c$} is the center and {$ r $} is the radius. Consider the following polyhedron
Changed line 251 from:
Computation of the Chebyshev center corresponds to inscribing a circle inside a polyhedron which is implemented in the @@chebyCenter@@ method. The circle is described as ${ x | \| x-x_c \|_2 \le r $} where {$x_c$} is the center and {$ r $} is the radius. Consider the following polyhedron
to:
Computation of the Chebyshev center corresponds to inscribing a circle inside a polyhedron which is implemented in the @@chebyCenter@@ method. The circle is described as {$ x | \| x-x_c \|_2 \le r $} where {$x_c$} is the center and {$ r $} is the radius. Consider the following polyhedron
Changed line 227 from:
To test wheter the polyhedron @@P@@ contains the origin {$x_0 = [0; 0] $}, the function @@contains@@ is invoked
to:
To test wheter the polyhedron @@P@@ contains the origin @@x0 = [0; 0] @@, the function @@contains@@ is invoked
Changed line 236 from:
The answer is yes, so the point {$x_0$} is contained inside the polyhedron. What about the point {$x_1 = [3; 0] $}?
to:
The answer is yes, so the point {$x_0$} is contained inside the polyhedron. What about the point @@x1 = [3; 0] @@?
Changed lines 251-252 from:
to:
Computation of the Chebyshev center corresponds to inscribing a circle inside a polyhedron which is implemented in the @@chebyCenter@@ method. The circle is described as ${ x | \| x-x_c \|_2 \le r $} where {$x_c$} is the center and {$ r $} is the radius. Consider the following polyhedron
(:source lang=MATLAB -getcode:) [@
P5 = Polyhedron([ 1.8 -4.8; -7.2 -3.4; -4.2 1.2; 5.8 2.7]);
@]
The data of the circle can be computed by calling
(:source lang=MATLAB -getcode:) [@
data = P5.chebyCenter()
data =
exitflag: 1
x: [2x1 double]
r: 3.1497
@]
where the field @@x@@ represents the center and @@r@@ is the radius. The field @@exitflag@@ is the status returned from the optimization solver. As the circle is a convex set, it can be represented as @@YSet@@ object and plotted together with the polyhedron
(:source lang=MATLAB -getcode:) [@
x = sdpvar(2,1);
S = YSet(x, norm(x - data.x) <= data.r);
P5.plot('wire', true, 'linewidth', 2);
hold on
S.plot('color', 'lightgreen');
plot(data.x(1), data.x(2), 'ko', 'MarkerSize', 10, 'MarkerFaceColor', 'k');
@]
%width=500% Attach:chebycenter.jpg %%
Added line 217:
Note that conversion between H- and V-representations is numerically expensive and can become time-consuming for polyhedra with large number of facets or vertices. The numerical computation is delegated to an external CDD solver that should be present at the installation path. ( If not, type @@tbxmanager install cddmex@@ to install it.)
Added lines 221-245:
The @@Polyhedron@@ class implements the @@contains@@ method which tests whether a point (or a set of points) is contained inside a polyhedron. Consider the following polyhedron in V-representation
(:source lang=MATLAB -getcode:) [@
V = [ -1.7 -0.4; -0.4 0.7; 1.2 -0.8; 0 0.8; 1.3 0.9; -0.3 0.6];
P4 = Polyhedron(V);
@]
To test wheter the polyhedron @@P@@ contains the origin {$x_0 = [0; 0] $}, the function @@contains@@ is invoked
(:source lang=MATLAB -getcode:) [@
x0 = [0; 0];
P4.contains( x0 )
ans =
1
@]
The answer is yes, so the point {$x_0$} is contained inside the polyhedron. What about the point {$x_1 = [3; 0] $}?
(:source lang=MATLAB -getcode:) [@
x1 = [3; 0];
P4.contains( x1 )
ans =
0
@]
The test containment for the points {$x_0$} and {$x_1$} is visualized in the figure below.
%width=500% Attach:contains.jpg %%
Changed line 133 from:
to:
* H-representation (by inequalities and equalities)
Changed line 135 from:
to:
* V-representation (by vertices and rays)
Added lines 137-216:
which can be converted vice-versa. The conversion from H- to V-representation is achieved via @@computeVRep@@ method. Consider the following polyhedron which is created in H-representation
(:source lang=MATLAB -getcode:) [@
P2 = Polyhedron('lb', [-1; -2], 'ub', [3; 4])
Polyhedron in R^2 with representations:
H-rep (redundant) : Inequalities 4 | Equalities 0
V-rep : Unknown (call computeVRep() to compute)
Functions : none
P2.hasVRep
ans =
0
@]
To compute the V-representation, the method @@computeVRep@@ method is called
(:source lang=MATLAB -getcode:) [@
P2.computeVRep
Polyhedron in R^2 with representations:
H-rep (redundant) : Inequalities 4 | Equalities 0
V-rep (redundant) : Vertices 4 | Rays 0
Functions : none
@]
To obtain the vertices and rays, one has to refer to @@V@@ and @@R@@ properties
(:source lang=MATLAB -getcode:) [@
P2.V
ans =
3 -2
-1 -2
-1 4
3 4
P2.R
ans =
Empty matrix: 0-by-2
@]
Note that the method @@computeVRep@@ is executed automatically when queried for vertices or rays using @@V@@ or @@R@@ properties.
The conversion from V- to H-representation is achieved via @@computeHRep@@ method. Consider the following triangle
(:source lang=MATLAB -getcode:) [@
P3 = Polyhedron([4, -1; 4, 5; 8, 3])
Polyhedron in R^2 with representations:
H-rep : Unknown (call computeHRep() to compute)
V-rep (redundant) : Vertices 3 | Rays 0
Functions : none
P3.hasHRep
ans =
0
@]
that comprises of three vertices. The H-representation can be computed by
(:source lang=MATLAB -getcode:) [@
P3.computeHRep
Polyhedron in R^2 with representations:
H-rep (redundant) : Inequalities 3 | Equalities 0
V-rep (redundant) : Vertices 3 | Rays 0
Functions : none
@]
and the facets can be extracted by pointing to @@H@@, @@He@@ properties (or @@A@@, @@Ae@@, @@b@@, @@be@@)
(:source lang=MATLAB -getcode:) [@
P3.H
ans =
1.0000 2.0000 14.0000
-1.0000 0 -4.0000
1.0000 -1.0000 5.0000
P3.He
ans =
Empty matrix: 0-by-3
@]
When queried for facets, the method @@computeHRep@@ is executed automatically.
Changed line 111 from:
to:
Added lines 76-123:
Polyhedra in the array can be removed
(:source lang=MATLAB -getcode:) [@
row_array1(2) = []
@]
The [[#basicProperties|basic methods]] operate onto arrays
(:source lang=MATLAB -getcode:) [@
row_array2.isEmptySet
ans =
0 0
column_array1.isFullDim
ans =
1
1
column_array2.isBounded
ans =
1
1
@]
If the method cannot be executed on an array, the @@forEach@@ function can be applied. For instance, to compute the [[#Grid|grid]] function cannot be evaluated on an array and one observes an error
(:source lang=MATLAB -getcode:) [@
row_array2.grid(5)
Error using ConvexSet/grid (line 22)
This method does not support arrays. Use the forEach() method.
@]
In this case, the @@forEach@@ method can be applied that executes the function on each polyhedron in the array. For more help on @@forEach@@ function type
(:source lang=MATLAB -getcode:) [@
help IterableBehavior
@]
The correct syntax for the above example using @@grid@@ function is given as
(:source lang=MATLAB -getcode:) [@
N = 5;
output = row_array2.forEach(@(x) grid(x, N), 'UniformOutput', false)
@]
To create a new copy of a @@Polyhedron@@ object, or an array of polyhedra, the method @@copy@@ must be invoked otherwise the new object point to the same data, i.e.
(:source lang=MATLAB -getcode:) [@
Qnew = Q.copy()
@]
Changed lines 56-75 from:
to:
Polyhedra can be grouped into column or row arrays. For this purpose in MPT there exist overloaded @@horzcat@@ and @@vertcat@@ operators or @@[ ]@@ brackets. Consider the two following polyhedra
(:source lang=MATLAB -getcode:) [@
Q = Polyhedron('V', [1, -1; 0, -4; 2.5 -3]);
R = Polyhedron('V', [2.5, -3; -1, 4; 1, -1; -1, 2]);
@]
The row array of polyhedra @@Q@@, @@R@@ can be created twofold
(:source lang=MATLAB -getcode:) [@
row_array1 = [Q, R]
row_array2 = horzcat(Q, R)
@]
Similarly, the column array is created as
(:source lang=MATLAB -getcode:) [@
column_array1 = [Q; R]
column_array2 = vertcat(Q, R)
@]
Each polyhedron in the array can be extracted using indices, e.g.
(:source lang=MATLAB -getcode:) [@
row_array1(1)
column_array1(2)
@]
Changed lines 24-25 from:
to:
Changed lines 32-33 from:
to:
Changed lines 40-41 from:
to:
Added lines 47-49:
(:source lang=MATLAB -getcode:) [@
P1.plot()
@]
Added line 6:
** [[#FacetVertex| Facet and vertex enumeration ]]
Changed lines 14-20 from:
The @@Polyhedron@@ object can be created in two forms
* H-representation
Attach:Geometry.Sets/polyhedronHrep.png
* V-representation
Attach:Geometry.Sets/polyhedronVrep.png
to:
The @@Polyhedron@@ class contains methods that are very useful for determining the basic properties such as
* emptyness - @@isEmptySet@@
* boundedness - @@isBounded@@
* full-dimensionality - @@isFullDim@@
As an example, consider the lower-dimensional polyhedron in the dimension 3
(:source lang=MATLAB -getcode:) [@
P1 = Polyhedron( 'A', [1 -2.1 -0.5; 0.8 -3.1 0.9; -1.2 0.4 -0.8], 'b', [1; 4.9; -1.8], 'Ae', [1 -0.1 0], 'be', 3)
@]
To query, if the set is empty or nor, use
(:source lang=MATLAB -getcode:) [@
P1.isEmptySet
ans =
0
@]
From the construction it is evident that the polyhedron is lower-dimensional because it contains one equality constraint. This fact can be checked using the method
(:source lang=MATLAB -getcode:) [@
P1.isFullDim
ans =
0
@]
Boundedness property can be queried by
(:source lang=MATLAB -getcode:) [@
P1.isBounded
ans =
0
@]
method. One can plot the polyhedron to verify that the above properties are true
%width=500% Attach:P1.jpg %%
Added lines 60-68:
[[#FacetVertex]]
!!!! Facet and vertex enumeration
The @@Polyhedron@@ object can be created in two forms
* H-representation
Attach:Geometry.Sets/polyhedronHrep.png
* V-representation
Attach:Geometry.Sets/polyhedronVrep.png
Changed line 74 from:
to:
Changed line 15 from:
Attach:polyhedronHrep.png
to:
Attach:Geometry.Sets/polyhedronHrep.png
Changed line 17 from:
Attach:polyhedronVrep.png
to:
Attach:Geometry.Sets/polyhedronVrep.png
Added lines 13-17:
The @@Polyhedron@@ object can be created in two forms
* H-representation
Attach:polyhedronHrep.png
* V-representation
Attach:polyhedronVrep.png
Changed lines 3-6 from:
* [[Geometry.OperationsWithPolyhedra#BasicProperties | Methods for determining basic properties ]]
Geometry.OperationsWithPolyhedra#MultipleSets | Working with multiple polyhedra ]]
* [[Geometry.OperationsWithPolyhedra#GeometricMethods | Geometric methods ]]
to:
* [[#BasicProperties | Methods for determining basic properties ]]
* [[#MultipleSets | Working with multiple polyhedra ]]
* [[#GeometricMethods | Geometric methods ]]
Changed lines 11-14 from:
Back to Geometry.Geometry| computational geometry overview]].
to:
[[#BasicProperties]]
!!! Methods for determining basic properties
[[#MultipleSets]]
!!! Working with multiple polyhedra
[[#GeometricMethods]]
!!! Geometric methods
[[#SetContainment]]
!!!! Set containment
[[#ChebyCenter]]
!!! Chebyshev center
Back to [[Geometry| Computational Geometry]] overview.
Added lines 1-15:
!!Geometric operations with polyhedra
* [[Geometry.OperationsWithPolyhedra#BasicProperties | Methods for determining basic properties ]]
* [[Geometry.OperationsWithPolyhedra#MultipleSets | Working with multiple polyhedra ]]
* [[Geometry.OperationsWithPolyhedra#GeometricMethods | Geometric methods ]]
** [[#SetContainment| Set containment]]
** [[#ChebyCenter | Chebyshev center ]]
----
Back to [[Geometry.Geometry| computational geometry overview]].