Convex Hull algorithm without built-in function

I have found on mathworks a convex hull algorithm, which uses randomly defined vectors as an input. I have tried to change random vectors to another ones, which I want to use. Unfortunately, the program says 'indeces on the right sight are not compatible with indeces on left side', giving me error at ind(1) = find(V == P1(:,1));

And I don't know what I need to change to make this program work with user-defined vectors, not random ones. So, I would be very glad for any help with this question.

x = random('Normal',0,1,1,10);

y = random('Normal',0,1,1,10);

InputData = [x',y'];

[V,I,vertices] = ConvexHull(InputData);

figure(46)

plot(InputData(:,1),InputData(:,2),'.','Color','red');

hold on

plot(V(:,1),V(:,2),'Marker','^','LineStyle','--','Color','#7E2F8E')

title('SuperOutput');

xlabel('x');

ylabel('y');

legend('InputData','Convex hull');

function [V,I,n] = ConvexHull(InputData)

V = [InputData(1:3,:)]; I = [1:3]';

for k = 4:length(InputData)

pk = InputData(k,:);

sup_ver = [];

ind = [];

index = [];

for i = 1:length(V)

vi = V(i,:);O = [];

for j = 1:length(V)

if (i ~= j)

vj = V(j,:);

O(j) = det([1,pk;1,vi;1,vj]);

end

end

O(O == 0) = [];

if ((numel(unique(sign(O))) == 1) == 1)

sup_ver = [sup_ver;vi];

end

end

if (isempty(sup_ver) == 0)

P1 = sup_ver(1,:);

P2 = sup_ver(2,:);

P3 = pk;

s = det([P1 - P2;P3 - P1]);

n = 1;

while (n <= length(V))

P = V(n,:);

if ((P ~= P1) & (P ~= P2) & (P ~= pk) & ((s * det([P3 - P;P2 - P3]) >= 0) & (s * det([P1 - P;P3 - P1]) >= 0) & (s * det([P2 - P;P1 - P2]) >= 0)) == 1)

V(n,:) = [];

I(n) = [];

n = n - 1;

end

n = n + 1;

end

ind(1) = find(V == P1(:,1));

ind(2) = find(V == P2(:,1));

index = find(InputData == pk(:,1));

if (ind(2) - ind(1) == 1)

V = [V(1:ind(1),:);pk;V(ind(1) + 1:end,:)];

I = [I(1:ind(1));index;I(ind(1) + 1:end)];

else

V = [pk;V];

I = [index;I];

end

end

end

V = vertcat(V,V(1,:));

I = vertcat(I,I(1));

end

Answer 1

[Satwik]

Hi Andrey,

The 'find' function returns indices of elements that match a condition, but if the condition involves comparing entire rows (as it seems to be in this case), it will not behave as expected. To workaround this issue, we can use the 'ismember' function with the 'rows' option, to correctly compare entire rows and find their indices. Here is an example of the above approach using user defined vectors as input:

x = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]; % User-defined x-coordinates
y = [0, 2, 1, 3, 5, 4, 6, 5, 7, 8]; % User-defined y-coordinates
InputData = [x', y'];

[V, I, vertices] = ConvexHull(InputData);
figure(46)
plot(InputData(:,1), InputData(:,2), '.', 'Color', 'red');
hold on
plot(V(:,1), V(:,2), 'Marker', '^', 'LineStyle', '--', 'Color', '#7E2F8E')
title('SuperOutput');
xlabel('x');
ylabel('y');
legend('InputData', 'Convex hull');

function [V, I, n] = ConvexHull(InputData)
    V = InputData(1:3, :);
    I = (1:3)';
    for k = 4:length(InputData)
        pk = InputData(k, :);
        sup_ver = [];
        for i = 1:size(V, 1)
            vi = V(i, :);
            O = [];
            for j = 1:size(V, 1)
                if i ~= j
                    vj = V(j, :);
                    O(j) = det([1, pk; 1, vi; 1, vj]);
                end
            end
            O(O == 0) = [];
            if numel(unique(sign(O))) == 1
                sup_ver = [sup_ver; vi];
            end
        end
        if ~isempty(sup_ver)
            P1 = sup_ver(1, :);
            P2 = sup_ver(2, :);
            P3 = pk;
            s = det([P1 - P2; P3 - P1]);
            n = 1;
            while n <= size(V, 1)
                P = V(n, :);
                if all(P ~= P1) && all(P ~= P2) && all(P ~= pk) && ...
                   (s * det([P3 - P; P2 - P3]) >= 0) && ...
                   (s * det([P1 - P; P3 - P1]) >= 0) && ...
                   (s * det([P2 - P; P1 - P2]) >= 0)
                    V(n, :) = [];
                    I(n) = [];
                    n = n - 1;
                end
                n = n + 1;
            end
            ind1 = find(ismember(V, P1, 'rows'));
            ind2 = find(ismember(V, P2, 'rows'));
            index = find(ismember(InputData, pk, 'rows'));
            if ind2 - ind1 == 1
                V = [V(1:ind1, :); pk; V(ind1 + 1:end, :)];
                I = [I(1:ind1); index; I(ind1 + 1:end)];
            else
                V = [pk; V];
                I = [index; I];
            end
        end
    end
    V = [V; V(1, :)];
    I = [I; I(1)];
end

You may refer to the following documentation for more information on the 'ismember' function:

https://www.mathworks.com/help/matlab/ref/double.ismember.html

I hope this helps!