How to draw weighted convex hull in Matlab

Question

Suppose I have a Matlab array PE of size Ex1. The elements of PE are between 0 and 1 and they sum up to one.

Take another array PEY of size ExY. The elements of PEY are one or zero. Moreover, for each row, there exists at least a one. Y=3.

For example

clear
E=4;
Y=3;
PE=[1/2; 1/6; 1/6; 1/6];
PEY=[1 0 0; 0 1 1; 1 1 1; 0 1 1];

Now, consider the simplex with vertices (1,0,0), (0,1,0), and (0,0,1)

patch([0 0 1],[0 1 0],[1 0 0],[0.8 0.8 0.8]);
axis equal 
axis([0 1 0 1 0 1])
view(120,30)

I want to draw a convex subset A of such simplex. A is constructed as follows.

STEP 1: We construct an Ex1 cell array PEY_expanded such that, for each e-th row of PEY that has more than a 1, we write down all admissible 1xY vectors containing just a 1 and stack them in PEY_expanded{e}.

PEY_expanded=cell(E,1);

for e=1:E
    if isequal(PEY(e,:),[1 1 1])
       PEY_expanded{e}=[1 0 0; 0 1 0; 0 0 1]; 
    elseif isequal(PEY(e,:),[1 1 0])
       PEY_expanded{e}=[1 0 0; 0 1 0];
    elseif isequal(PEY(e,:),[1 0 1])
       PEY_expanded{e}=[1 0 0; 0 0 1];
    elseif isequal(PEY(e,:),[0 1 1])
       PEY_expanded{e}=[0 1 0; 0 0 1];
    else
       PEY_expanded{e}=PEY(e,:);
    end
end

STEP 2: Take Cartesian product PEY_expanded{1} x PEY_expanded{2} x ... PEY_expanded{E} and get PEY_cartesian.

Note: the code below is specific for E=4 and not general

size_PEY_expanded=zeros(E,1);
for e=1:E
size_PEY_expanded(e)=size(PEY_expanded{e},1);
end

[a,b,c,d]=ndgrid(1: size_PEY_expanded(1),1: size_PEY_expanded(2),...
                 1: size_PEY_expanded(3), 1: size_PEY_expanded(4));

PEY_Cartesian= [PEY_expanded{1}(a,:),PEY_expanded{2}(b,:),...
                PEY_expanded{3}(c,:), PEY_expanded{4}(d,:)];

PEY_Cartesian_rearranged=cell(prod(size_PEY_expanded),1);
for i=1:prod(size_PEY_expanded)
    PEY_Cartesian_rearranged{i}=[PEY_Cartesian(i,1:3); PEY_Cartesian(i,4:6);...
                                 PEY_Cartesian(i,7:9);  PEY_Cartesian(i,10:end)];
end

PEY_Cartesian=PEY_Cartesian_rearranged;

STEP 3: For each possible cell of PEY_Cartesian, for y=1,...,Y, weight PEY_Cartesian{i}(e,y) by PE(e) and then sum across e.

PY=zeros(prod(size_PEY_expanded),Y);
for i=1:prod(size_PEY_expanded)
    for y=1:Y
        temp=0;
        for e=1:E
               temp=temp+PE(e)*PEY_Cartesian{i}(e,y);
        end
        PY(i,y)=temp;
    end
end

STEP 4: Draw the region A that is the convex hull of the rows of PY (black region in the picture)

%Need https://fr.mathworks.com/matlabcentral/fileexchange/37004-suite-of-functions-to-perform-uniform-sampling-of-a-sphere
close all
patch([0 0 1],[0 1 0],[1 0 0],[0.8 0.8 0.8]);
axis equal 
axis([0 1 0 1 0 1])
view(120,30)
hold on
T = delaunayTriangulation(PY);
K = convexHull(T);
patch('Faces',K,'Vertices',T.Points,'FaceColor','k','edgecolor','k');
hold on

QUESTION:

The algorithm above is unfeasible for large E. In my actual case I have E=216, for example. In particular, step 2 is unfeasible. Could you suggest an easier way to proceed? Given that A is a convex region, maybe there is some shortcut I'm unable to see.

How to draw weighted convex hull in Matlab

0 Answers