Sample routines from the Geometric
Bounding Toolbox 7.3
Prof. Sandor M. Veres, sandy1@sysbrain.com, UK
1
CONVH CONVH
Purpose
The purpose of CONVH is to compute convex hull of points.
Usage
function [H,acc]=convh(V,typ);
where the variables used are:
V[0] - set of points
Brief Description of the Algorithm (not included)
Convex hull computation for a set of points means determining all the equations
of the hyperplane facets of the p olytope which forms the convex hull. The algorithm
of ‘convh’ is based on succesive inclusion of points into the convex hull one-by-one.
The subroutine ‘p conv’ is performing the inclusion of one further. ‘convh’ is first
looking for the vertices of a large simplex among the points given and then always
includes the farthest lying point into the polytope using ‘p conv’. if the initial
simplex is lower dimensional than that of the space where the pints are defined,
then switches to to a lower dimensional space and calls itself to compute the convex
hull, the lower dimensional representation obtained is finally converted back to the
oriinal dimension. See Chapter 1 on the format of polytope representations in GBT.
Example
The following demo generates a random set of points in 3D and displays the
projected 2D wireframe views of their convex hull:
V=rand(6,3);P=convh(V);view2d(P,[1,2,3]); % no.figs=1
Detailed Description of the Algorithm (not included)
2
0 0.2 0.4 0.6 0.8
0
0.2
0.4
0.6
0.8
1
Projection to 1−2 axes
0 0.2 0.4 0.6 0.8
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Projection to 1−3 axes
0 0.2 0.4 0.6 0.8 1
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Projection to 2−3 axes
Figure 1: Demo figure to routine CONVH .
DEFBOX DEFBOX
Purpose
The purpose of DEFBOX is to generate an axis aligned box.
Usage
function P=defbox(vertex1,vertex2);
where the variables used are:
vertex1[-1] - lowest position corner of the box
Brief Description of the Algorithm
The algorithm is based on building up lists of vertices in a way as binary number
are build from 0 and 1, except these are replace by lower-corner and upper conrner
components respectively. The number of vertices thus becomes 2
d
where d is the
dimension of the space. The 2d facet ineqaalities are formed by unit vectors and
components of the lower and upper corners given.
Example
The following code defines a box with diagonal points [0.4,0.5,1] and [1.2,1.4,2]
and displays its projected wireframe views:
3
P=defbox([0.4,0.5,1],[1.2,1.4,2]);view2d(P,[1 2 3]);% no.figs=1
Detailed Description of the Algorithm (not included)
0.4 0.6 0.8 1 1.2 1.4
0.4
0.6
0.8
1
1.2
1.4
Projection to 1−2 axes
0.4 0.6 0.8 1 1.2 1.4
1
1.2
1.4
1.6
1.8
2
Projection to 1−3 axes
0.4 0.6 0.8 1 1.2 1.4
1
1.2
1.4
1.6
1.8
2
Projection to 2−3 axes
Figure 2: Demo figure to routine DEFBOX .
4
DIAMETER DIAMETER
Purpose
The purpose of DIAMETER is to compute diameter of a polytope.
Usage
function [diam,ds,de]=diameter(P);
where the variables used are:
P[[1 eps;1 1]] - polytope
Brief Description of the Algorithm (not included)
The diameter for a polytope is computed by comparing distances of all pairs of
vertices. The choice of the maximum is by double application of the efficient routine
‘max’ provided by MATLAB. A similar routine, but acting on a set of points, is
‘diamet’ .
Example
The following code finds the diameter of a random polygone and plots its 2D
wireframe views with the diameter:
V=rand(10,2);P=convh(V);[diam,ds,de]=diameter(P);
view2d(P,[1 2]); X=[ds’;de’];line(X(:,1),X(:,2)); % no.figs=1
Detailed Description of the Algorithm (not included)
5
