Как разделить 2D фигуру на участки примерно одинакового размера в Matlab?

Question

У меня есть двумерная матрица нулей и единиц, где единицы обозначают выпуклую фигуру

Теперь я хочу разделить эту цифру (то есть элементы значения 1) в неперекрывающихся патчах одинакового размера, как на этом рисунке

Есть ли у вас какие-либо предложения?Я мог бы пойти на mat2cell и иметь только прямоугольники, и сохранить прямоугольники с хотя бы одним значением 1, но я бы предпочел более равное деление.

Answer 1

Для подобных задач я часто использую метод, называемый «ортогональная рекурсивная бисекция». Пример того, что он делает с вашим кругом, показан на картинке.

Как следует из названия, метод делит субдомены на два меньших субдомена, пока общее количество поддоменов не станет желаемым значением.

Моя реализация для вашего случая

function array = ORB(array,nparts)
%
% array = ORB(array,nparts)
%
% Divide the nonzeros of array into nparts equally large,
% approximately square parts.
%

% convert true/false array into 0/1:
ar    = array; array = zeros(size(ar)); array(ar)  = 1;

% initialize subdivision-admin
istart = 1; iend = nparts; values = 1;
last_value = max(values);

% Divide up the parts that need dividing up
while length(values) < nparts
    new_istart = []; new_iend = []; new_values = [];
    for i = 1:length(values)
        if iend(i) > istart(i)
           disp(sprintf('Current values %d should eventually be split into domains %d-%d',values(i),istart(i),iend(i)))
           last_value = last_value + 1;
           new_istart = [new_istart, istart(i),                                    istart(i) + floor((iend(i)-istart(i)+1)/2)];
           new_iend   = [new_iend,   istart(i) + floor((iend(i)-istart(i)+1)/2)-1, iend(i)];
           new_values = [new_values, values(i),                                    last_value];
           n = length(new_values);
           disp(sprintf('Current values %d should now be split into domains %d and %d, in ratio %d:%d\n', ...
                               values(i), new_values(n-1:n),new_iend(n-1:n)-new_istart(n-1:n)+1));
           array = Split(array,new_values(n-1:n),new_iend(n-1:n)-new_istart(n-1:n)+1);
        else
           disp(sprintf('Domain %d is done\n',values(i)))
           new_istart = [new_istart, istart(i)];
           new_iend   = [new_iend,   iend(i)];
           new_values = [new_values, values(i)];
        end
    end
    iend   = new_iend; istart = new_istart; values = new_values;
end
for i = 1:nparts
   disp(sprintf('Part %d has %d points',i,length(find(array==i))))
end
close all
pcolor(array)

, для которой требуется функция Split:

function array = Split(array,parts,sizes)
%
% array = Split(array,parts,sizes)
%
% Change some of the values of array which are now equal to parts(1) into the value parts(2).
% At the end, the ratio
%   length(find(array==parts(1))) : length(find(array==parts(2)))
% should be
%                        sizes(1) : sizes(2)
%

% Calculate sizes of each patch
[i,j] = find(array==parts(1));
npoints = size(i,1); sizes = npoints * sizes/(sizes(1)+sizes(2));


imin = min(i); imax = max(i); jmin = min(j); jmax = max(j);
nmin = 0; nmax = npoints;
if jmax-jmin>imax-imin
   % divide domain in (j < jmid) and (jmid <= j)
   while jmax > jmin + 1
      jmid = (jmax + jmin)/2; n_this = size(find(j<jmid));
      if n_this < sizes(1)
         jmin = jmid; nmin = n_this;
      else
         jmax = jmid; nmax = n_this;
      end
   end
   i = i(j>=jmid); j = j(j>=jmid);
else
   % divide domain in (i < imid) and (imid <= i)
   while imax > imin + 1
      imid = (imax + imin)/2; n_this = size(find(i<imid));
      if n_this < sizes(1)
         imin = imid; nmin = n_this;
      else
         imax = imid; nmax = n_this;
      end
   end
   j = j(i>=imid); i = i(i>=imid);
end

% Change the values in array
array(sub2ind(size(array),i,j)) = parts(2);