如何从连续单元格的外部单元格中创建多边形 [英] How to create a polygon out of the outer cells of a contiguous patch of cells

问题描述

我在 Matlab 中绘制了一块连续的单元格.

I have below a contiguous patch of cells plotted in Matlab.

必须确定红色补丁的外部单元格，然后连接这些单元格中心的多边形将为我提供一个多边形.如何计算连续补丁的外部单元格?

The outer cells of the red patch have to be determined and then a polygon joining the centers of these cells will give me a polygon. How do i compute the outer cells of the contiguous patch?

我有一个整数数组，其元素表示红色补丁中的单元格，例如，

I have an array of integers whose elements denote the cell in the red patch, for example,

a=[1;64;23;456;345];

每个元素，比如64，对应图像中的一个单元格，它是属于红色补丁的单元格.

Each element , say 64 corresponds to a cell in the image, and it is the cell belonging to the red patch.

解决这个问题的动机是处理一个边数最少的多边形，而不是这么多像元.它减慢了计算速度.凸壳不够好.我根本不希望生成的多边形与棕色区域重叠.

The motivation to solve the problem is to deal with a polygon with minimal number of edges rather than so many cells. it slows down computation. Convex hull is not good enough. I don't want the resulting polygon to overlap with the brown area at all.

我建议的是下图中左侧的情况，但它看起来很难看.因此，更好的方法是跳过仅与外部棕色区域共享一个点的单元格.我希望我的外部单元格只与外部棕色区域共享一个以上的点.

What i am suggesting is the case on the left in image below but it seems ugly. So a better way would be as in right to just skip the cells only sharing a single point with the outer brown area. I would like my outer cells to then be only those that share more than just a single point with the outer brown area.

但我们希望避免生成的多边形中出现大量边！

But we want to avoid large number of edges in the resultant polygon!

推荐答案

虽然@rahnema1 的回答真的很酷，但我认为OP 更多的是询问如何根据描述的规则提取边集.

Although the answer by @rahnema1 is really cool, I think the OP is asking more how to extract the set of edges according to the described rules.

这是我识别所有 10 个包含边缘的 2x2 像素模式的方法.假设矩阵 A 的图像具有 1s 和 0s (A = zeros(ny, nx); A(a) = 1):

Here is my approach identifying all the 10 patterns of 2x2 pixels that contain edges. Assuming the matrix A has the image with 1s and 0s (A = zeros(ny, nx); A(a) = 1):

% we identify patterns with edges over 2x2 patches, describing with
% the first 4 binary values what pixels are set, and with the next 2
% the edge with 2 indices over the 2x2 patch
patterns = [
 0,1,0,1,  3,4 % vertical edge at rhe right 
 1,0,1,0,  1,2 % vertical edge at the left
 0,0,1,1,  2,4 % horizontal edge at the bottom
 1,1,0,0,  1,3 % horizontal edge at the top
 1,0,0,1,  1,4 % diagonal edge
 0,1,1,0,  2,3 % diagonal edge
 1,0,1,1,  1,4 % diagonal edge, extra pixel set
 1,1,0,1,  1,4 % diagonal edge, extra pixel set
 1,1,1,0,  2,3 % diagonal edge, extra pixel set
 0,1,1,1,  2,3 % diagonal edge, extra pixel set
];

% 2x2 patches (matrix form)
P00 = A(1:end-1,1:end-1);
P10 = A(2:end,1:end-1);
P01 = A(1:end-1,2:end);
P11 = A(2:end,2:end);

% edge unique identifier using powers of 2
id = @(p00,p01,p10,p11) 1*p00 + 2*p10 + 4*p01 + 8*p11;
P = id(P00,P01,P10,P11); % vectorized pattern identification

% edges
e0 = []; % from (i,j)
e1 = []; % to (i,j)
for i = 1:size(patterns, 1) % small loop over the 10 patterns
  p = patterns(i, :);
  E = (P == id(p(1),p(2),p(3),p(4))); % pattern search, vectorized
  [c,r] = ind2sub(size(E), find(E));
  [c0,r0] = ind2sub([2,2], p(5));
  [c1,r1] = ind2sub([2,2], p(6));
  e0 = [e0; c+c0, r+r0];
  e1 = [e1; c+c1, r+r1];
end

这里将结果应用到您的图像(我使用 GIMP 进行捕获、调整大小和过滤，所以图像可能不完全相同相同):

And here the result applying it to your image (I used GIMP for capture, resize and filter, so maybe the image is not exactly the same):

X = [e0(:,2) e1(:,2)];
Y = size(A,1) - [e0(:,1) e1(:,1)];
plot(X', Y', '.-')

我假设一旦你有了上述集合，获得描述多边形(或多个多边形)的有序边缘序列就不是这里的主要问题.

I am assuming that obtaining an ordered sequence of edges describing the polygon (or polygons) is not the main problem here once you have the aforementioned set.

这篇关于如何从连续单元格的外部单元格中创建多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！