时间戳

首页 > 解决方案 > 如何在matlab中将二维形状划分为大约相等大小的块？

matlab - 如何在matlab中将二维形状划分为大约相等大小的块？

问题描述

我有一个由零和一组成的二维矩阵，其中的表示一个凸图

我的起始图

我现在想将这个数字（即值为 1 的元素）划分为大小相同的非重叠块，如图所示

我所追求的划分类型

你有什么建议吗？我可以mat2cell只使用矩形，并保留其中至少一个值为 1 的矩形，但我更喜欢更平等的划分。

标签： matlab

解决方案

对于类似的问题，我经常使用一种叫做“正交递归二分法”的方法。图片中就是它对你的圈子所做的一个例子。

顾名思义，该方法将子域划分为两个较小的子域，直到子域的总数达到所需值。

我对您的案例的实施是

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)

这需要功能拆分：

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

推荐阅读