Convex Hull algorithm without built-in function

2 次查看（过去 30 天）

Andrey Kryukov 2022-4-5

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1689480-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

O(O == 0) = [];

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

sup_ver = [sup_ver;vi];

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)];